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:
Show quoted text
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?
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?
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:
Show quoted text
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?
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