W3C home > Mailing lists > Public > www-ql@w3.org > January to March 2001

Re: [www-ql] <none>

From: Michael Kifer <kifer@cs.sunysb.edu>
Date: Sun, 04 Mar 2001 15:50:57 -0500
Message-Id: <200103042050.PAA15153@sbcs.cs.sunysb.edu>
To: Michael Dyck <MichaelDyck@home.com>
cc: www-ql@w3.org

> > database languages are designed so that certain queries would be
> > expressible *and most queries would not be*. The latter is important so
> > that query processors would be able to perform non-trivial optimizations.
> Could you give an example of a query that would not be expressible in a
> database language?

This depends on which database query language you have in mind.  For
instance, SQL (pre-1999) couldn't express transitive closure (e.g., bill of
materials), but even after the addition of recursion its expressive power
is limited to polynomial time queries. This is why you have embedded sql,
CLI, PSM, and all that.

> > An algebra is a procedural language that exists in order to provide
> > an intermediate, relatively high language to which you translate a
> > declarative language.
> So XQuery
>     (e.g., FOR $b IN $bib/book WHERE $b/year = 1998 RETURN $b/title)
> is declarative, but XML Query Algebra
>     (e.g., for b in bib0/book do where b/@year/data() = 1998 do b/title)
> is procedural?
> I'd say, as far as declarative/procedural "feel" is concerned, they're quite
> similar. Specifically, their informal semantics (as given in prose in the
> respective WDs) are both phrased in fairly procedural terms (in my opinion,
> anyhow).
> What is it that makes XQuery declarative but the Algebra procedural?

I preceded this with a statement saying that I am not referring to XQuery
or XML Algebra in particular. These were general remarks on the
relationship of a database query language to a query algebra.

Regarding XML Algebra specifically, it is a rather general language that
has recursive functions, where clauses and all that stuff. It doesn't look
like an algebra at all (no more than PSM does). To me it looks like a
fairly high-level query language.

I must confess that XML Algebra wasn't fresh in my mind. I read about it
in the Fernandes/Simeon/Wadler paper many months ago (maybe 1 year ago),
and I didn't remember all these high-level features.

This leads back to your original question: why two languages?
One answer might be that they have somewhat different style and the choice
can be a matter of preference.

The interesting question is whether the algebra people themselves view it
as a QL or an algebra...

Received on Sunday, 4 March 2001 15:51:43 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 20:17:15 UTC