Search Postgresql Archives

Re: Recursive Arrays 101

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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


--
Sent via pgsql-general mailing list (pgsql-general@xxxxxxxxxxxxxx)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general



[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Index of Archives]     [Postgresql Jobs]     [Postgresql Admin]     [Postgresql Performance]     [Linux Clusters]     [PHP Home]     [PHP on Windows]     [Kernel Newbies]     [PHP Classes]     [PHP Books]     [PHP Databases]     [Postgresql & PHP]     [Yosemite]
  Powered by Linux