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
