Re: Recursive Arrays 101

On 04/11/2015 17:53, Rob Sargent wrote:
> On 11/04/2015 03:03 AM, Achilleas Mantzios wrote:
>> Sorry for being kind of late to the party (I was in 2015.PgConf.EU !!), and not having read
>> most of the replies, what we have been successfully doing for this problem for our app
>> is do it this way :
>> parents int[] -- where parents stores the path from the node to the root of the tree
>> and then have those indexes :
>> btree (first(parents))
>> btree (level(parents)) -- length
>> btree (last(parents))
>> gin (parents gin__int_ops) -- the most important
>>
>> This has been described as "genealogical tree" approach, and works very good, IMHO much better
>> than nested sets.
>>
> Is there a more complete description of this approach available? By the title one might assume could be applied to populations as opposed to phylogeny (the OP's use case). Does it deal with
> consanguinity? Does it perform well going "up" the tree (which is of course branched at every level)?

From here https://en.wikipedia.org/wiki/Phylogenetic_tree I assume that phylogenetic trees are normal
trees, and I see no reason why not be modeled with the genealogical approach described. The earliest paper
I based my work on was :
https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CCUQFjABahUKEwiR6auUlvnIAhXGvhQKHVyDA-s&url=https%3A%2F%2Fdownload.samba.org%2Fpub%2Funpacked%2Fldb%2Fldb_sqlite3%2Ftrees.ps&usg=AFQjCNEktJsibP435MBki5cdGmO_CzKmwg&sig2=I9yC_tpyeWrEueDJTXbyAA&bvm=bv.106674449,d.d24&cad=rja

Finding the root is O(1). Going "up" the tree or finding common ancestry is reduced to the problem
of finding overlap/intersections/contains/contained between postgresql arrays.

The indexes, functions and operators provided by contrib/intarray were a basic element for the success of this
approach.

--
Achilleas Mantzios
IT DEV Lead
IT DEPT
Dynacom Tankers Mgmt