[xquery-talk] XQuery static typing algorithms?

[Jens Teubner]

On Mon, Nov 24, 2008 at 09:44:38AM +0100, Bas de Bakker wrote:

> Maybe you can find something useful here:
> 
> http://www-db.informatik.uni-tuebingen.de/research/pathfinder/publications
> 
> In particular the article "Subtyping For Regular Tree Types : a
> JAVA-based Implementation".

The algorithm in that Master's thesis is essentially based on the
dissertation of Martin Kempa at the University of Lübeck, Germany.  The
dissertation itself is in German ("Programmierung von XML-basierten
Anwendungen unter Berücksichtigung der Sprachbeschreibung"), but you
find some English papers authored by Martin at

    http://www.ifis.uni-luebeck.de/~ifis/public/ .

The Pathfinder XQuery compiler uses a similar algorithm internally.  It
is very fast and powerful.

However, this is an algorithm for structural subtyping.  In many
details, the behavior of this algorithm is different to what the XQuery
specs describe (and it is not always trivial to fix that).  Not sure
whether the algorithms in the TATA book have the same problems.  My
personal impression is that, if you want to be standards-compliant, the
best way to start is to literally implement all the judgments in the W3C
Formal Semantics.

Static typing is closely related to (a) XML validation and (b) type
matching (i.e., "dynamic typing").  There are two papers on the
Pathfinder publications page (XIME-P and EDBT, respectively), that talk
about these two aspects.  Both of them seem to be better aligned with
the official W3C specs than the mentioned subtyping algorithm does.

Best regards,

Jens

-- 
Jens Teubner
ETH Zurich, Systems Group
Haldeneggsteig 4 / IFW B 48.3
8092 Zurich, Switzerland

Science is what we understand well enough to explain
to a computer. Art is everything else we do.
                         -- Donald Knuth