[
Lists Home |
Date Index |
Thread Index
]
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
|
