Re: [xml-dev] The use of XML syntax in XML Query

At 06:26 AM 1/4/2002 -0800, Dare Obasanjo wrote:
>I'm still waiting for someone with a theoretical background to debunk the
>statements in the paper "On Database Theory and XML"[0] that it is is an
>unsolvable problem to guarantee that one can create a query that for any given
>XML input will generate output that conforms to a specified XML schema.
>
>[0] http://www.cs.washington.edu/homes/suciu/files/_F2066943700.ps

I do not claim to be a hard-core theorist, but here is my reading of the 
relevant portion of the paper. To play it safe, I am copying Dan on this 
message, so he can correct me if I got it wrong.

1. Dan says that static XML typechecking is undecidable if an arbitrary C++ 
or Java program is generating XML documents, due to Rice's theorem. He says 
that XML typechecking may be possible for more restricted languages such as 
XQuery or XSLT.

2. Typechecking without type inference can work fine as long as you do not 
have joins. If joins are involved, typechecking becomes undecidable.

3. Type inference is the most promising approach, but it does lead to some 
false negatives. He gives an example using a content model involving equal 
cardinality among three different elements in sequence. The schema for this 
can not be expressed in DTDs or in XML Schema, so it is not clear to me 
that this is a real limitation, but I just read this, and I need to do some 
thinking before I would want to draw a strong conclusion based on his 
examples.

4. Dan concludes that type inference is still the most promising approach 
to static typechecking, but that further work needs to be done on its 
applicability and limitations.

My own take on this is that static type checking using type inference is 
very promising, and seems to work well in theory for the kinds of queries I 
have looked at. An implementation using the current type system did catch 
interesting errors for me. I think our type system needs further work, and 
we need more practical experience using implementations that do static type 
checking. This is one of the highest priorities for me personally.

Jonathan

Received on Thursday, 3 January 2002 19:27:12 UTC