Thread: recursive queries?

Now and again, I find myself wanting to store data in some kind of
variable-level hierarchy.  To take a familiar example, let's say the
directory structure on my computer.

So I start to do something like:

CREATE SEQUENCE directory_id_seq;
CREATE TABLE directory {
    parent    INTEGER,
    name    TEXT,
    id    INTEGER
        DEFAULT nextval('directory_id_seq')
        PRIMARY KEY
};

INSERT INTO directory
VALUES (1, '\.');

ALTER TABLE directory
ADD FORIEGN KEY (parent)
REFERENCES directory(id)
ON DELETE CASCADE
ON UPDATE CASCADE;

Happy, happy.  The problem is, while it's easy enough to define such a
data structure, support for recursive queries is rather lacking.  To
unroll a directory tree, you basically have to resort to programming in
<insert your favorite language>.

Not that I really know what I'm talking about when I say 'unroll'.  This
data structure is general enough to support cyclic directed graphs.  So
what does it mean to 'unroll' such a beasty?

So what's my question then?  Well, it seems like maybe there _should_,
or at least _could_ be support for some kinds of common problems.  For
example, I would like to constrain my data structure to really be a
tree, and not a potentially cyclical graph.

Does anyone know whether there has been, or ever will be, movement in
this direction among the SQL literati?  Am I asking a completely
inappropriate question?

Perhaps these types of problems are what OODB adherents are attempting
to address.

So, to sum, my question:  Who plays in this space?  Will the SQL
standard itself ever play in this space?

Personally, I'm really only interested in something elegant.  Meaning I
don't want to mess around with a solution where this broker communicates
with that broker via an n-way blah blah blah.  I can maintain literacy
in several tools at once, but not several dozen.  Is my best bet simply
to accept SQL's limitations and program around them in C++ (or C, or
Python, or Perl, etc.)?

Ron Peterson
rpeterson@yellowbank.com

> Personally, I'm really only interested in something elegant.  Meaning I
> don't want to mess around with a solution where this broker communicates
> with that broker via an n-way blah blah blah.  I can maintain literacy
> in several tools at once, but not several dozen.  Is my best bet simply
> to accept SQL's limitations and program around them in C++ (or C, or
> Python, or Perl, etc.)?

Good question!  I have certainly given this one some thought before.  One of my
projects involved a directory structure of sorts which allowed non-cyclic
symlinking.  My solution in this case was to create a seperate table that was a
'map' -- the map was a pre-calculated, flattened version of the entire graph.
Thus, a single query of the map table for "/blah/blah2/etc/" returned
immediately correct subdirectory.  Each time the linking tables are updated,
the map table must be re-calculated.  This solution will not work for the
general cyclic graph, of course...  and it may be inappropriate for the
situation where the link tables are update frequently since each update forces
a large recursive caluculation of the map -- the primary advantage is the speed
and easy of querying.

I am not aware of any SQL constructs of 'for' loops or 'while' loops, so I am
not sure how one could solve the problem in pure SQL -- actually, you probably
could using a recursive stored procedure.


Andy

Ron Peterson writes:

> The problem is, while it's easy enough to define such a data
> structure, support for recursive queries is rather lacking.  To unroll
> a directory tree, you basically have to resort to programming in
> <insert your favorite language>.

Well, nothing is perfect, and this is exactly the point where relational
databases aren't. A lot of people that are a lot more educated than me on
the matter have commented on just this in detail for years and decades so
you should be able to find enough material out there if you're interested.
Apparently, this sort of thing worked in network and/or hierarchical
databases (which came before relational) and object oriented databases are
supposes to fix it again, but the fact that all the world uses relational
databases shows that either recursion (infinite joins) isn't widely useful
or that the other advantages outweigh this problem. Not sure.


--
Peter Eisentraut                  Sernanders väg 10:115
peter_e@gmx.net                   75262 Uppsala
http://yi.org/peter-e/            Sweden

Peter Eisentraut wrote:
>
> Ron Peterson writes:
>
> > The problem is, while it's easy enough to define such a data
> > structure, support for recursive queries is rather lacking.  To unroll
> > a directory tree, you basically have to resort to programming in
> > <insert your favorite language>.
>
> Well, nothing is perfect, and this is exactly the point where relational
> databases aren't. A lot of people that are a lot more educated than me on
> the matter have commented on just this in detail for years and decades so
> you should be able to find enough material out there if you're interested.
> Apparently, this sort of thing worked in network and/or hierarchical
> databases (which came before relational) and object oriented databases are
> supposes to fix it again, but the fact that all the world uses relational
> databases shows that either recursion (infinite joins) isn't widely useful
> or that the other advantages outweigh this problem. Not sure.

Don't get me wrong, I think SQL is wonderful.  That's why this problem
is so fustrating.  What I want to do seems _almost_ in reach, but not
quite.  Defining recursive data structures is certainly possible in SQL,
but that's as far as it goes.  There's no standard way to define
validation rules, or recursive queries.

I have read various mail threads and whatnot that have alluded to sQL
standards committees looking at the possibility of remedying these
deficiencies.  But I haven't been able to find any evidence that these
efforts are actually underway.  Does anyone know what direction the
evolution of the SQL standard is headed?

I keep struggling along with SQL not because I don't think recursive
data structures are useful, but as you say, "the other advantages
outweigh this problem".  How would they be useful?  It's not hard to
come up with some examples of useful problems where SQL falls short.
How about a genealogical database?  Threaded mail or news discussions?
Web site layouts.  Etc.  I think all of these examples could benifit
from being implemented in a system that support transactions and
relational calculus.

I suppose I'm just another lazy activist - "Somebody should do
something!"  I can suffer along for now, but what I'm really wondering
is if the investment I make now in SQL will be rewarded later when SQL
adds new and better features.  Should I just hold my horses because
something better is coming along, or look elsewhere?

Ron Peterson
rpeterson@yellowbank.com