Re: 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(at)sai(dot)msu(dot)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(at)killerbytes(dot)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(at)heute-morgen(dot)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(at)heute-morgen(dot)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(at)heute-morgen(dot)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(at)heute-morgen(dot)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(at)heute-morgen(dot)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(at)heute-morgen(dot)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