Re: Recursive Arrays 101 - Mailing list pgsql-general

On 06/11/15 04:33, Rob Sargent wrote:
> On 11/05/2015 04:56 AM, Achilleas Mantzios wrote:
>> 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.
>>
> Going "up" a genealogy to me means getting two parents, four
> grandparents, 8 great grandparents etc.  On a good day, at least when
> there are no loops.  This isn't, to my understanding, how phylogeny
> works (but my genetics degree was thirty year ago) so perhaps I'm
> still confused by the titles used.  And certainly not to say that your
> approach isn't what the OP really needs!
>
>
You're actually going 'DOWN' the tree, in terms of how trees are used in
computer science & graph theory!

See http://www.mathcove.net/petersen/lessons/get-lesson?les=32


Cheers,
Gavin