Thread: DAGs and recursive queries
Hi everyone, I would like to know the best way to implement a DAG in PostgreSQL. I understand there has been some talk of recursive queries, and I'm wondering if there has been much progress on this. Are there any complete examples of DAGs which work with PostgreSQL? I would like to be able to do the following operations for a categorization system: 1. Given a node, get one or more field values out of every parent node 2. Given a parent node, get one or more field values out of every child node 3. Given two or more parent nodes, identify any common children. I do not need to determine shortest paths between parents and children, only to be able to iterate over them as efficiently as possible. I'd like to keep things dynamic so changes up the hierarchy don't require changes to any of the children (unless their direct parents are changed). I'd also like to keep as much processing as possible in the database to minimize the traffic between my application and the DB, so I think I'm looking for SQL and stored procedure solutions. Any pointers would be great, as I'm not a DBA and do not have the experience to make judgments about the best possible approach. Regards, Paul Dorman
"paul.dorman" <paul.dorman@gmail.com> writes: > Hi everyone, > > I would like to know the best way to implement a DAG in PostgreSQL. I > understand there has been some talk of recursive queries, and I'm > wondering if there has been much progress on this. The ANSI recursive queries didn't make it into 8.3. I still hope it makes 8.4. You could check out the tablefunc contrib which includes a function called connectby() which implements a kind of recursive query. Alternatively you might look at the ltree contrib module but that doesn't work the way you describe. It denormalizes the data for very fast but less flexible operations. -- Gregory Stark EnterpriseDB http://www.enterprisedb.com
take a look on contrib/ltree On Wed, 26 Sep 2007, paul.dorman wrote: > Hi everyone, > > I would like to know the best way to implement a DAG in PostgreSQL. I > understand there has been some talk of recursive queries, and I'm > wondering if there has been much progress on this. > > Are there any complete examples of DAGs which work with PostgreSQL? I > would like to be able to do the following operations for a > categorization system: > > 1. Given a node, get one or more field values out of every parent node > 2. Given a parent node, get one or more field values out of every > child node > 3. Given two or more parent nodes, identify any common children. > > I do not need to determine shortest paths between parents and > children, only to be able to iterate over them as efficiently as > possible. > > I'd like to keep things dynamic so changes up the hierarchy don't > require changes to any of the children (unless their direct parents > are changed). I'd also like to keep as much processing as possible in > the database to minimize the traffic between my application and the > DB, so I think I'm looking for SQL and stored procedure solutions. > > Any pointers would be great, as I'm not a DBA and do not have the > experience to make judgments about the best possible approach. > > Regards, > Paul Dorman > > > ---------------------------(end of broadcast)--------------------------- > TIP 3: Have you checked our extensive FAQ? > > http://www.postgresql.org/docs/faq > Regards, Oleg _____________________________________________________________ Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru), Sternberg Astronomical Institute, Moscow University, Russia Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/ phone: +007(495)939-16-83, +007(495)939-23-83
On Wed, 2007-09-26 at 16:54 +0100, Gregory Stark wrote:
> "paul.dorman" <paul.dorman@gmail.com> writes:
>
> > Hi everyone,
> >
> > I would like to know the best way to implement a DAG in PostgreSQL. I
> > understand there has been some talk of recursive queries, and I'm
> > wondering if there has been much progress on this.
>
> The ANSI recursive queries didn't make it into 8.3. I still hope it makes 8.4.
>
> You could check out the tablefunc contrib which includes a function called
> connectby() which implements a kind of recursive query.
>
> Alternatively you might look at the ltree contrib module but that doesn't work
> the way you describe. It denormalizes the data for very fast but less flexible
Ltree seems like it might be a good option for him. What doesn't it do
that he needs?
I am also interested in graphs and trees in relational databases. Can
you recommend any good books? I particularly like CJ Date as an author,
but I can't find anything by him that specifically addresses this topic.
Also, how exactly is the database denormalized by using ltree?
Regards,
Jeff Davis
"Jeff Davis" <pgsql@j-davis.com> writes: > On Wed, 2007-09-26 at 16:54 +0100, Gregory Stark wrote: > >> You could check out the tablefunc contrib which includes a function called >> connectby() which implements a kind of recursive query. >> >> Alternatively you might look at the ltree contrib module but that doesn't work >> the way you describe. It denormalizes the data for very fast but less flexible > > Ltree seems like it might be a good option for him. What doesn't it do > that he needs? ... > Also, how exactly is the database denormalized by using ltree? It keeps the same information in more than one place. Consider: 1 1.1 1.1.1 Note that all three records contain the root's id of "1". If you want to reparent 1.1 to be 2.1 you have to know that all its children also need to be reparented as well. That's what he said he wanted to be able to do. In general if you have a relatively static hierarchy something like ltree works very well but if you have a very dynamic hierarchy where nodes move around freely it's not a very good fit. -- Gregory Stark EnterpriseDB http://www.enterprisedb.com
On Thu, 2007-09-27 at 23:58 +0100, Gregory Stark wrote:
> It keeps the same information in more than one place. Consider:
>
> 1
> 1.1
> 1.1.1
>
> Note that all three records contain the root's id of "1". If you want to
> reparent 1.1 to be 2.1 you have to know that all its children also need to be
> reparented as well.
Aren't there still some update anomolies with any schema representing a
DAG?
Regards,
Jeff Davis
Thanks for your answers guys. I've got a cold right now and my brain is mush, so I can't comment intelligently on your suggestions just yet. I just wanted to express my thanks for your time. Jeff, one book you might want to look at is Joe Celko's Trees and Hierarchies in SQL for Smarties. http://www.amazon.com/Hierarchies-Smarties-Kaufmann-Management-Systems/dp/1558609202 If the connectby() function is like the Oracle connectby function, then perhaps it will suit my needs. The categorization scheme will nearly always have multiple parents for all but the topmost node. Each category stores serialized method calls for CRUD operations on objects within the category, which are requested by the application for all interactions with stored objects (though I'd like to be able to cache them too, but that's in the application domain). Each object stored in the database will belong to at least one category, but I expect they will normally belong to many categories. When I create a new object of categoryD, which is a child of categoryC and categoryB, which are children of categoryA, then my application will need the CREATE method calls from all parents, as well as the object category itself. I'd like them all returned from one query, possibly ordered according to the distance from the child node. Oops, I'm trying to comment intelligently. Better stop now. Cheers, Paul