Re: Recursive Arrays 101
От | Rob Sargent |
---|---|
Тема | Re: Recursive Arrays 101 |
Дата | |
Msg-id | 563B9FB8.60904@gmail.com обсуждение исходный текст |
Ответ на | Re: Recursive Arrays 101 (Gavin Flower <GavinFlower@archidevsys.co.nz>) |
Список | pgsql-general |
On 11/05/2015 11:08 AM, Gavin Flower wrote: > 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 > > Fine. Be that way :) Still the question of loops/consanguinity?
В списке pgsql-general по дате отправления:
Следующее
От: bock@openit.de (Julian v. Bock)Дата:
Сообщение: Lock contention in TransactionIdIsInProgress()