Re: XQuery question

From: Costin Cozianu <c_cozianu_at_hotmail.com>
Date: Thu, 15 May 2003 12:11:05 -0700
Message-ID: <ba0ocp$o17ol$1@ID-152540.news.dfncis.de>

>> 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.

Yep, I didn't claim that SQL is perfectly designed either, still the WITH RECURSIVE expressions are not *that* difficult to grasp.

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

Or is the argument of either the puzzled or the bored.

>>> 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").
>

When you bind the variables (free terms) of a predicate you get a proposition. Let's stop quibbling over terms. Let me reiterate again, the predicate correspond to the "header" (by Date's terminology)/schema of a relation. Each individual tuple is a proposition.

And I think you are definitely wrong here: the values in the columns can be as complex as you like. Relational model can't care less of what kind of domains you use for the columns.

>>
>>
>> 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.
>

Well, for what is worth I don't see how you express the above in XML either, although you can express that in standard SQL 99 as a constraint to be verified against data rather than data. I know how to express that in Prolog, however efforts to make the DBMSes a general purpose inference engine either failed or went out of steam (funding ?).

>> 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".

Wait a second doc. A graph (directed and simple which is what most people use for practical purposes, but other cases can be ahndled relationally as well) is the pair G=(V, E) with E <= VxV, since V is already implied by E we can cut out the redundancy and just say E <= VxV which is a binary relation.

I don't know for the life of me what you mean by the "shape" of the graph. If you mean the picture you draw on a paper, only *that* is at a different level of abstraction.

I don't want to operate on the "picture" or the "shape" or the physical encoding, I want to operate as much as possible close to the mathematical definition of a mathematical concept.

>
> 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.
>

I find this assertion gratuituous. Let me reiterate, I can logically equate a graph with a binary relation - it is most definitely not an encoding/translation kind of thingie. Using relations I can also represent graphs which allow several edges between 2 nodes, and I can also represent hypergraphs.

Just show me how you do that "conveniently", "intuitively" and declaratively with your imbricated pairs of tags !

>>
>> 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.:-)
>

Well, maybe you have a paper or present here a brief summary so that I can "get" it what you mean by "XML data model".

>> 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.
>

When solving the same use case takes a handful of lines of code using relational algebra extended with transitive closure, while it may take screens of code using XQuery / XPATH / DOM API/ SAX APi whatever, that's where I can justifiably say that XML as a data model is unintuitive to unworkable.

>>> 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)?

No, that's just implementation details. Transitive closure is a concept with a very simple definition which I already posted in this thread. As far as I have been tought defining concepts in terms of how you compute them is not the best way to do mathematics, and definitely it is not the declarative way that you claim.

Delarative means the "what" not the "how". The standard definiton of transitive closure is the what it is not the "how you calculate it", I refer you to any elementary introduction to algebra.

> 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).
>

Just post here a better encoding for a graph, together with the query. You're not going to kid me that trees are a good encoding for a graph while relations are not. The fact that you refuse to post anything at all concrete and come up with excuses is kind of telling, don't you think ?

>> 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:

Maybe you can speculate on the utility of relational algebra (plus the transitive closure) in solving real use cases for real users. If your data model is going to support those use cases than it automatically means that it will be relationally complete. Or else, you can speculate what relational operators are unuseful and we don't need to support them.

I thought it was elementary that any new data model/query language proposal ought to be reltaionally complete (and in auseful sense of the word, not in the sense that for example "COBOL is turing complete").

Or if you want to set aside let's say relational division, you ought to justify why you want to do that. Don't you agree ?

> - 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)
>
> 7
> 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.

If you said "sometimes superior", I might give you a pass. And second, you have to come first with those data models so that we have something we can talk about and compare.

> 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.
>

Sure, COBOL was standardizzed and had a broad user community, it was the kid on the block in its days. CORBA was the same, what else ?

In the end all you have is vague promises , you have no coherent data model to show for it. And when pressed for concrete examples you back away saying that when you will have such and such.

The thread was about XQuery and XML in particular not about what's your dream data model.

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

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

It's not an argument I express what I see, and it is a value judgement with regards to your contribution to this thread.

If you have a better data model proposed somewhere, I'll be happy to learn about. Otherwise just claiming that relational model is not good at representing graphs is hand waving to me (ok, it may be to you a subjective interpretation of "intuitivity" or other ethereal properties).

Best regards,
Costin Received on Thu May 15 2003 - 14:11:05 CDT