Re: XQuery question

From: Costin Cozianu <c_cozianu_at_hotmail.com>
Date: Thu, 08 May 2003 11:43:59 -0700
Message-ID: <b9e86v$ie0us$1@ID-152540.news.dfncis.de>

Bob Foster wrote:
> "Costin Cozianu" <c_cozianu_at_hotmail.com> wrote in message
> news:b9banv$hf3ud$2_at_ID-152540.news.dfncis.de...
>

>>As for the SQL, for all its faults, it supported recursive queries for 4
>>years already. The idea was even implemented in DB2. Of course, Oracle
>>had support for hierarchical queries with CONNECT BY for as long as I
>>can remember working with Oracle (I guess it was Oracle 7.3 in 96 ?).

>
>
> It? What version of the standard was that?
>

SQL '99 it's called WITH RECURSIVE. IBM db2 decided that recursive is superfluous and didn't implement the full options (which are probably more powerfuil than you need for transitive closure)

Here's a DB2 Example:

CREATE TABLE Rel (ID integer, Parent integer );

WITH MyView ( ID Integer, Ancestor integer) AS ( SELECT ID , Parent as Ancestor FROM Rel

	UNION ALL
      SELECT r1.ID, r2.Parent AS Ancestor
      FROM Myview r1, Rel r2
			WHERE r1.Parent= r2.ID )

SELECT * from MyView

As you can see MyView is joined recursively with otsel;f in its definition so that we get the transitive closure.

>

>>But in order to do a fair and unbiased comparison I'd like to know if
>>XQuery is relationally complete (including the transitive closure of a
>>binary relation).
>>
>>So can you provide a good reference (google was kind of fuzzy on this
>>subject)

>
>
> I would love to provide one, but I don't have it, except the basic
> "standard" which is a work in progress. XQuery is Turing complete so of
> course it is relationally complete, but it does not directly support the
> relational operators. Nor does SQL, but I admit SQL is closer. During the
> delay between your posting and my reply a new draft of XQuery has been
> published, so you can appreciate that pointing to a large body of XQuery
> examples is not an option!
>
> But I don't mean to brush off your question. I actually took a stab at
> defining the relational primitives you cite. I didn't have much of a
> problem; cartesian product, intersection, union, set difference (called
> except), projection and selection are implemented directly in terms of
> sequences, which resemble sets well enough given certain constraints. I
> think you would appreciate how easy it is to understand XQuery FLOWR (for,
> let, order by, where, return) expressions given your SQL background.

No, I don't really appreciate that :) Although the rule of XQuery are quite simple and intuitive, the fact that I have to "encode" my data model by hanging all data items in a chrsitmas tree, makes me have very little appreciation if any to XML as a data model (you call that XML "infoset" or something, I beleive).

Plus I don't really see how mixing orthogonal concerns like logical data structure and physical data encoding (representaition, viz. the bloody tags) is going to help me in any way shape or form. Dijkstra told us we can do better decades ago, viz. separtion of concerns, and Codd was of the same opinion.

This leads in my opinion to way unnecessary complexity.

> But I
> came to an annoying impasse while trying to define a general version of
> relational division. I don't mean to say that a clever person can't define a
> division function in XQuery that would work as an analog of relational
> division, given a suitable analog of a relation/table. I am sure even I can,
> given enough time. But something about the problem brought home the
> difficulty of comparing sequence operations with set operations. It seemed
> to me one has to work extra hard to model a tuple in XQuery, as tuples are
> usually represented as a two-level hierarchy of elements in XML. I don't
> like to work extra hard writing queries, so I regretfully dropped the
> project. I invite quicker minds to pick it up.
>
> As to transitive closure, XQuery can do these with no problem, as I have
> tried to illustrate elsewhere in this thread. But here _I_ need a reference.
> What is the definition of transitive closure in relational terms?

Transitive closure is not a relational term, I knew that from my first introductory course in algebra, before I knew what a dataabse was.

Given a binary relation on A, R included in AxA we saythat the transitive closure on R is the smallest binary relation R1 included in AxA so that R included in R1 and R1 is transitive: for any elements a, b, c

    aRb and bRc implies aRc

Incidentally this is the same with the infinte union of all powers of R R1= R union R^2 union R^3 union ....

In layman's term consider that a binary relation defines a directed graph, you have an edge from a to b iff aRb, now we define the transitive relation the relation R1 so that aR1b if and only if there exists a path in the graph from A to B.

Or even more intuitive consider applying the rule the friends of my friends are also my friends.

It's strictly related to binary relations, and it means strictly a bit more than recursive descent on trees (it is generalized for any kind of graph), which I think is what you presented.

> It seems
> to me the operation needs a function argument, and I believe this is a step
> beyond the relational algebra. No doubt this is pure ignorance on my part,
> but I am willing to be educated.
>

Now you are right that the classic relational algebra as defined by Dr. Codd didn't include transitive closure, and the classical relational algebra cannot support transitive closure as a composed operation.

But the fatc is that it's been proposed for quite a while that the relational model should icnlude all the classic relational operators + transitive closure. See for example Chris Date An Introduction to Database Systems (2000).

Given the fact that it's already supported one way or the other in actual SQL products, I would see no problem in considering transitve closure as an integral part odf relational model both theoretically and practically.

> Bob
> PS My stupid newsreader could not resolve comp.database.theory, so I have
> removed this from the cross-posting list. I do not quite understand why
> comp.object is cross-posted, but I have left it. Much to the annoyance, I am
> sure, of people who realize that XML and relational database have little to
> do with objects.

It was my mistake the gorup name was comp.databases.theory
>

Best,
Costin Received on Thu May 08 2003 - 13:43:59 CDT