Thread: Limits of SQL
Hi. I am looking for a way to write a SELECT that finds connectivity components of a graph or at least for one that given two nodes determines if there is a path between them. It seems that this is not possible, no matter what graph representation I choose. Which constructs from set theory are missing in SQL? Set of all subsets is one I am missing, or can it be done somehow? Is anybody else thinking about the limits of SQL? As often I am probably not the first to ask these questions. Any pointers? Sincerely, Joachim
You mean, you want to be able to say something like: select isConnected(a,b) and get back a true/false, or maybe the path? That seems quite doable in SQL, assuming you either store those results and simply use sql to retrieve them, or use a stored proc to compute the result each time. On Thu, 2 Jun 2005, Joachim Zobel wrote: > Hi. > > I am looking for a way to write a SELECT that finds connectivity > components of a graph or at least for one that given two nodes > determines if there is a path between them. It seems that this is not > possible, no matter what graph representation I choose. Which constructs > from set theory are missing in SQL? Set of all subsets is one I am > missing, or can it be done somehow? > > Is anybody else thinking about the limits of SQL? As often I am probably > not the first to ask these questions. Any pointers? > > Sincerely, > Joachim > > > > ---------------------------(end of broadcast)--------------------------- > TIP 6: Have you searched our list archives? > > http://archives.postgresql.org >
I'm not sure if it's relevant to your question http://www-2.cs.cmu.edu/~cache/pg_graph/ pg_graph provides a way of handling graph-based data structures within the relational database PostgreSQL. In particular, it provides a convenient means of inserting graphs as BLOB-like objects in the RDBMS. Primarily, however, it provides a mechanism for indexing the graphs to provide efficient means to perform nearest-neighbor queries over collections of graphs. On Thu, 2 Jun 2005, Joachim Zobel wrote: > Hi. > > I am looking for a way to write a SELECT that finds connectivity > components of a graph or at least for one that given two nodes > determines if there is a path between them. It seems that this is not > possible, no matter what graph representation I choose. Which constructs > from set theory are missing in SQL? Set of all subsets is one I am > missing, or can it be done somehow? > > Is anybody else thinking about the limits of SQL? As often I am probably > not the first to ask these questions. Any pointers? > > Sincerely, > Joachim > > > > ---------------------------(end of broadcast)--------------------------- > TIP 6: Have you searched our list archives? > > http://archives.postgresql.org > Regards, Oleg _____________________________________________________________ Oleg Bartunov, sci.researcher, hostmaster of AstroNet, Sternberg Astronomical Institute, Moscow University (Russia) Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/ phone: +007(095)939-16-83, +007(095)939-23-83
A couple of links: http://www.dbazine.com/ofinterest/oi-articles/celko24 http://www.dbmsmag.com/9603d06.html On Jun 2, 2005, at 2:33 AM, Joachim Zobel wrote: > Hi. > > I am looking for a way to write a SELECT that finds connectivity > components of a graph or at least for one that given two nodes > determines if there is a path between them. It seems that this is not > possible, no matter what graph representation I choose. Which > constructs > from set theory are missing in SQL? Set of all subsets is one I am > missing, or can it be done somehow? > > Is anybody else thinking about the limits of SQL? As often I am > probably > not the first to ask these questions. Any pointers? > > Sincerely, > Joachim > > > > ---------------------------(end of > broadcast)--------------------------- > TIP 6: Have you searched our list archives? > > http://archives.postgresql.org >
> Is anybody else thinking about the limits of SQL? As often I am probably > not the first to ask these questions. Any pointers? Joe Celko (sp?) has a couple of books on this subject, SQL for Smarties. I don't recall if he talks about graphs, but does discuss queries on tree relationships. -- Scott Ribe scott_ribe@killerbytes.com http://www.killerbytes.com/ (303) 665-7007 voice
>> Is anybody else thinking about the limits of SQL? As often I am probably >> not the first to ask these questions. Any pointers? > > Joe Celko (sp?) has a couple of books on this subject, SQL for Smarties. I > don't recall if he talks about graphs, but does discuss queries on tree > relationships. I've got the 2nd edition and while I haven't made it that far, Ch 30 is on graphs. -philip
Am Donnerstag, den 02.06.2005, 12:46 -0700 schrieb Ben: > You mean, you want to be able to say something like: > > select isConnected(a,b) > > and get back a true/false, or maybe the path? > > That seems quite doable in SQL, assuming you either store those results > and simply use sql to retrieve them, or use a stored proc to compute the > result each time. These are both things I want to avoid. I am not trying to solve a real world problem, I want to understand the limits of SQL. And it seems that a plain SELECT that tells me if a path exists is not possible. However I just read nested sets (thx for the link, Sean). Maybe a tricky representation does it. Sincerely, Joachim
On Sat, Jun 04, 2005 at 11:31:02 +0200, Joachim Zobel <jzobel@heute-morgen.de> wrote: > > These are both things I want to avoid. I am not trying to solve a real > world problem, I want to understand the limits of SQL. And it seems that > a plain SELECT that tells me if a path exists is not possible. However I > just read nested sets (thx for the link, Sean). Maybe a tricky > representation does it. When 'WITH' gets implemented then you should be able to do this. I think there was some recent talk about that, but I don't know if it is going to make it in to 8.1. We'll know in about a month though.
Am Samstag, den 04.06.2005, 07:38 -0500 schrieb Bruno Wolff III: > On Sat, Jun 04, 2005 at 11:31:02 +0200, > Joachim Zobel <jzobel@heute-morgen.de> wrote: > > > > ... And it seems that > > a plain SELECT that tells me if a path exists is not possible... > > When 'WITH' gets implemented then you should be able to do this. I think > there was some recent talk about that, but I don't know if it is going to > make it in to 8.1. We'll know in about a month though. So WITH will allow recursion so I can walk the graph, right? Does this mean I can recursively join until a terminating condition is reached? Sincerely, Joachim
On Sat, Jun 04, 2005 at 21:53:24 +0200, Joachim Zobel <jzobel@heute-morgen.de> wrote: > Am Samstag, den 04.06.2005, 07:38 -0500 schrieb Bruno Wolff III: > > On Sat, Jun 04, 2005 at 11:31:02 +0200, > > Joachim Zobel <jzobel@heute-morgen.de> wrote: > > > > > > ... And it seems that > > > a plain SELECT that tells me if a path exists is not possible... > > > > When 'WITH' gets implemented then you should be able to do this. I think > > there was some recent talk about that, but I don't know if it is going to > > make it in to 8.1. We'll know in about a month though. > > So WITH will allow recursion so I can walk the graph, right? Does this > mean I can recursively join until a terminating condition is reached? It can be used to compute transitive closures, which I think is what you are really looking for. If you look at the TODO page (http://www.postgresql.org/docs/faqs.TODO.html) you will see two entries for WITH under Exotic Features: Add SQL99 WITH clause to SELECT Add SQL99 WITH RECURSIVE to SELECT There is a short example of this on pages 439-440 of "SQL for Smarties" second edition.
Am Samstag, den 04.06.2005, 15:22 -0500 schrieb Bruno Wolff III: > On Sat, Jun 04, 2005 at 21:53:24 +0200, > Joachim Zobel <jzobel@heute-morgen.de> wrote: > > So WITH will allow recursion so I can walk the graph, right? Does this > > mean I can recursively join until a terminating condition is reached? > > It can be used to compute transitive closures, which I think is what > you are really looking for. There aren't any plans to implement grouping by a user defined equivalence relation? This is the other thing I am missing. But OK, WITH will keep me happy for some time :) Sincerely, Joachim
Joachim Zobel schrob: > Am Samstag, den 04.06.2005, 15:22 -0500 schrieb Bruno Wolff III: >> On Sat, Jun 04, 2005 at 21:53:24 +0200, >> Joachim Zobel <jzobel@heute-morgen.de> wrote: >> > So WITH will allow recursion so I can walk the graph, right? Does this >> > mean I can recursively join until a terminating condition is reached? >> >> It can be used to compute transitive closures, which I think is what >> you are really looking for. > > There aren't any plans to implement grouping by a user defined > equivalence relation? This is the other thing I am missing. But OK, WITH Isn't this already possible by representing the relation through its canonical mapping (i.e. f(a)=f(b) <=> a relates to b)? You could then use GROUP BY f(x) to group data into its equivalence classes. regards, Andreas