Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!samsung!usc!ucsd!ucbvax!agate!agate!hughes
From: hughes@tsunami.Berkeley.EDU (Eric Hughes)
Newsgroups: comp.databases
Subject: Re: SQL query
Message-ID: <HUGHES.90Mar16200143@tsunami.Berkeley.EDU>
Date: 17 Mar 90 04:01:43 GMT
References: <9349@stiatl.UUCP>
Sender: usenet@agate.berkeley.edu (USENET Administrator;;;;ZU44)
Distribution: usa
Organization: ucb
Lines: 21
In-reply-to: rk@stiatl.UUCP's message of 14 Mar 90 14:50:24 GMT

In article <9349@stiatl.UUCP> rk@stiatl.UUCP (Rajeev Kumar) writes:

>I have a table with two fields: SuperGrp and SubGrp, with the
>characteristics that a SubGrp can be a SuperGrp for other SubGrps.

In other words, a directed graph.

>"Retrieve all the SubGrps of @US".
>By "all SubGrps" I mean if @US has a SubGrp which
>also happens to be a SuperGrp, then retrieve the
>SubGrps of that SubGrp and so on.

This query is a form of a "transitive closure."  In graph language, it
means that you take a node, and come up with the set of all nodes
which can be reached from the original.

This can't be done in SQL.  Date has a paper on this in his book
_Selected Writings_.  BTW, he thinks it is a deficiency.

Eric Hughes
hughes@ocf.berkeley.edu