Lists: | pgsql-general |
---|
From: | Joachim Zobel <jzobel(at)heute-morgen(dot)de> |
---|---|
To: | pgsql-general(at)postgresql(dot)org |
Subject: | Limits of SQL |
Date: | 2005-06-02 06:33:03 |
Message-ID: | 1117693984.4999.13.camel@localhost |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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
From: | Ben <bench(at)silentmedia(dot)com> |
---|---|
To: | Joachim Zobel <jzobel(at)heute-morgen(dot)de> |
Cc: | pgsql-general(at)postgresql(dot)org |
Subject: | Re: Limits of SQL |
Date: | 2005-06-02 19:46:21 |
Message-ID: | Pine.LNX.4.44.0506021244200.5624-100000@localhost.localdomain |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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
>
From: | Oleg Bartunov <oleg(at)sai(dot)msu(dot)su> |
---|---|
To: | Joachim Zobel <jzobel(at)heute-morgen(dot)de> |
Cc: | pgsql-general(at)postgresql(dot)org |
Subject: | Re: Limits of SQL |
Date: | 2005-06-02 19:49:03 |
Message-ID: | Pine.GSO.4.62.0506022348020.3882@ra.sai.msu.su |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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
From: | Sean Davis <sdavis2(at)mail(dot)nih(dot)gov> |
---|---|
To: | jzobel(at)heute-morgen(dot)de |
Cc: | pgsql-general(at)postgresql(dot)org |
Subject: | Re: Limits of SQL |
Date: | 2005-06-02 20:04:10 |
Message-ID: | 4cc4a1618669015e512eafdffc110c60@mail.nih.gov |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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
>
From: | Scott Ribe <scott_ribe(at)killerbytes(dot)com> |
---|---|
To: | <jzobel(at)heute-morgen(dot)de>, Postgres General <pgsql-general(at)postgresql(dot)org> |
Subject: | Re: Limits of SQL |
Date: | 2005-06-03 17:44:05 |
Message-ID: | BEC5F305.269BC%scott_ribe@killerbytes.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
> 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
From: | Philip Hallstrom <postgresql(at)philip(dot)pjkh(dot)com> |
---|---|
To: | Scott Ribe <scott_ribe(at)killerbytes(dot)com> |
Cc: | jzobel(at)heute-morgen(dot)de, Postgres General <pgsql-general(at)postgresql(dot)org> |
Subject: | Re: Limits of SQL |
Date: | 2005-06-03 19:45:01 |
Message-ID: | 20050603124442.J23383@wolf.pjkh.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
>> 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
From: | Joachim Zobel <jzobel(at)heute-morgen(dot)de> |
---|---|
To: | Ben <bench(at)silentmedia(dot)com> |
Cc: | pgsql-general(at)postgresql(dot)org |
Subject: | Re: Limits of SQL |
Date: | 2005-06-04 09:31:02 |
Message-ID: | 1117877463.4405.9.camel@localhost |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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
From: | Bruno Wolff III <bruno(at)wolff(dot)to> |
---|---|
To: | Joachim Zobel <jzobel(at)heute-morgen(dot)de> |
Cc: | Ben <bench(at)silentmedia(dot)com>, pgsql-general(at)postgresql(dot)org |
Subject: | Re: Limits of SQL |
Date: | 2005-06-04 12:38:01 |
Message-ID: | 20050604123801.GA28552@wolff.to |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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.
From: | Joachim Zobel <jzobel(at)heute-morgen(dot)de> |
---|---|
To: | Bruno Wolff III <bruno(at)wolff(dot)to> |
Cc: | pgsql-general(at)postgresql(dot)org |
Subject: | Re: Limits of SQL |
Date: | 2005-06-04 19:53:24 |
Message-ID: | 1117914805.4405.16.camel@localhost |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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
From: | Bruno Wolff III <bruno(at)wolff(dot)to> |
---|---|
To: | Joachim Zobel <jzobel(at)heute-morgen(dot)de> |
Cc: | pgsql-general(at)postgresql(dot)org |
Subject: | Re: Limits of SQL |
Date: | 2005-06-04 20:22:13 |
Message-ID: | 20050604202213.GA20567@wolff.to |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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.
From: | Joachim Zobel <jzobel(at)heute-morgen(dot)de> |
---|---|
To: | Bruno Wolff III <bruno(at)wolff(dot)to> |
Cc: | pgsql-general(at)postgresql(dot)org |
Subject: | Re: Limits of SQL |
Date: | 2005-06-05 18:53:30 |
Message-ID: | 1117997610.4455.14.camel@localhost |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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
From: | Andreas Seltenreich <seltenreich(at)gmx(dot)de> |
---|---|
To: | Joachim Zobel <jzobel(at)heute-morgen(dot)de> |
Cc: | Bruno Wolff III <bruno(at)wolff(dot)to>, pgsql-general(at)postgresql(dot)org |
Subject: | Re: Limits of SQL |
Date: | 2005-06-05 21:35:05 |
Message-ID: | 87ll5osd12.fsf@gate450.dyndns.org |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Lists: | pgsql-general |
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