Re: XQuery question

Costin Cozianu wrote:

> Sebastian Schaffert wrote:
>
>> Costin Cozianu wrote:
>>
>> [transitive relations]
>>
>>>
>>> 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.
>>
>>
>> Now, just tell me in which way this is *declarative*, and why SQL is
>> less complex than XML query languages...<g>
>>
> The fact that is declarative is obvious, and if you want me to explain
> that yo you, I'm at a loss. Either get over it, or else stop the
> discussion.

The point is, the expression you provide above is not obvious without digging deeper into it's semantics. The fact that you would need to explain it to me shows that it is not declarative, since I am quite familiar with SQL and the relational database model.

The "either get over it, or else stop discussion" is the argument of the weak who is not able to support his point differently.

>>>>> 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).
>>>>
>>>>
>>>>
>>
>> Whether XQuery is relationally complete or not is of no relevance,
>> since it is not intended to be so, as the underlying data is not
>> relational, it is tree-shaped.
>>
>
> That's non-sense. Data is data. It comes from the plural of the latin
> "datum" which means a "given", therefore data is a collection of (given)
> facts . "Given facts" are proposition that are true. Relational
> databases hold a collection of facts and those have no "relational"
> shape. That's just non-sense good only for marketing brochures.

What you call a proposition is really considered a n-ary predicate over atomic terms in logics. In the case of relational databases, these terms are always constants and thus flat, while in general (first order logic), the predicates may also range over complex terms (i.e. "trees").

>
>
> If you're willing to show me a useful "tree-shaped" logic, I'd be very
> curious to find out more about that.

Ok, take first order logic. It's data is tree shaped (terms made up of functors and constant symbols). In contrast, "datalog" (or the relational theory) is merely a subset of FOL with no functors, only constants.

FOL:
forall X. person(X) => person(father(X))

Obviously, father('John') is a (simple) tree shaped data item.

You cannot express such terms conveniently in datalog.

>>
>> I prefer encoding my data model as a tree in my data model than
>> encoding it in completely ridiculous SQL queries (see above). If
>> the data is
>> inherently graph-structured it is much more intuitive to represent it
>> graph structured and provide appropriate query languages for it
>> (note: I don't think XQuery is appropriate, but this is not the fault
>> of the XML data model).
>>
>
> You are confused. Graphs and relations are almost indistigusihable from
> a logical point of view. A tree is a binary relation with certain
> properties.

I think that rather you are confusing the different levels of abstraction. Obviously, I can represent a graph structure as a binary relation. On the other hand, this is merely an encoding of the "picture" (or "shape") of the graph, where the latter can immediately be grasped while it is almost impossible to even partially imagine the shape of the graph when encoded as a binary relation. That's what I mean with "declarativity".

Relational databases are very declarative for *certain* kinds of data, i.e. such data that is inherently relational (addressbooks, booking system). On the other hand, while you are still able to represent graph-structured data in a relational database, this representation is always very "inconvenient" (if you like that better than "undeclarative") to use since the represented data is not immediately obvious.

>>
>>
>> In fact, XML is all about "logical data structure" and none about
>> physical encoding.
>
>
> This opinion puts you at odds with the honourable XML committee who
> specified first the encoding, than an inadequate way of representing
> schema (DTD), later came with XML Schema which is half way to
> acceptable, as for the XML Infoset which is the abstract "data model"
> behind XML it is really way behind and probably not official standard at
> this time.

>
> In any case people when you say XML think about the <xml> </xml> data
> encoding no matter what you'd like them to think.
>
Well, if you ask my students, they will tell you.:-)

>
>> XML is merely a form of tree structured data representation which is
>> IMO rather intuitive for the user. How the data is stored is a
>> completely different matter. It could be an XML view on a relational
>> database. It could also be an XML view on an XML document. And it can
>> be a mixture of both (i.e. combined XML view onto multiple,
>> heterogeneous databases).
>>
>
> Your opinion does not count as long as it is not backed by arguments.

One cannot back subjectivity by arguments, and when one talks about "intuitivity", it is inherently subjective. Your answer again shows that you try to be insulting when you don't have arguments left.

>>> This leads in my opinion to way unnecessary complexity.
>>
>>
>>
>> As for unnecessary complexity, I'd like again to refer to your SQL
>> example above.
>>
>
> For which you haven't provide a counter example. Show me a general
> transitive closure (not just recursive descent down the bracnches of a
> tree) over a binary relation and let's talk after that.

Recursive descent is per definition the way to do transitive closure over a graph, isn't it (take your favorite book on graph theory and you'll see)? It's just a matter of how I encode the graph. Your example XML document is not the appropriate representation of graph structures in a graph language, it is trying to "port" the insufficiencies of relational databases to XML. In XML, I don't need to encode the graph as binary relation, I can encode it as graph (under the assumption of a reasonable link mechanism).

> And you also refuse to address the issue whether XQuery is relationally
> complete and at what cost (viz. query complexity, and runtime
> performance).

I refuse to speculate about relational completeness of XQuery because: - I never claimed that XQuery was relationally complete - nor is it relevant, because XML is not relational (as I already stated), instead it is a set of
  terms
- nor do I particularly like XQuery; in fact I am working on *replacing* XQuery with something

   better

As to cost:
- XQuery is merely a language specification which says nothing about implementation. There are
  very inefficient implementations, and also some which are better - XQuery and XML Querying is a very new issue, so optimization is currently just beginning to
  become an issue
- XQuery, as a rather control-flow oriented language, does not leave much room for automatic

   query optimization (which is why we are working on a different language)

I repeat it, I am NOT claiming that XQuery is good. I am claiming that an inherently tree or graph-shaped data representation language is often superior to flat relational tuples. I do NOT say that XML is a particularly good representation for tree- or graph-shaped data (Lisp S-expressions would achieve the same). However, XML is well standardized, it has a broad community and despite its deficiencies (like DTD, processing instructions, unfortunate link mechanisms, etc) is a reasonably good representation for such data.

> This leaves you currently quite short of any serious arguments other
> than hand waving.

Such statements actually don't improve your arguments, either.

-- 
Sebastian

| Dipl.-Inform. Sebastian Schaffert                    LFE Programmier-/
| schaffert_at_informatik.uni-muenchen.de             Modellierungssprachen
| LMU München - Institut für Informatik - Zimmer C8 - Tel: 089/2180-9781

PGP Key fingerprint =  
       13 1D 2E 4F 20 3E C9 1F  4C 57 52 87 8A 80 48 4D  F5 E9 97 EC