[
Lists Home |
Date Index |
Thread Index
]
This is what I understand from reading the papers (I have merely glanced at
the second one that Joe English found):
Given an input document that will always be of the form
root_elem ( a^n , b^ n)
which by the way can't be expressed in any schema language
(I wonder why not? This puzzles me as much as the one token
of lookahead issue with XML schema parsers. Is it that people
have never felt the need to write documents with such structure?)
and a query of the form doc//(a | b), the best a type inferencing algorithm
can assume is that the DTD for the output XML is
(a* , b*) - iT [infered type]
even though we know it is actually
(a^n, b^n). - aT [actual type]
So if our task is to determine whether the query always conforms to the
following form
( ( (a, a)*, (b, b)* ) | ( (a, a)*, a, (b, b)*, b ) ) - oT [output Type]
which is a way of attempting to say either an even number of a's and b's or an
odd number of b's,
Our type inference technique will FAIL because our inferred type [iT] is not a
subset of the required output type [oT] even though we know for a fact that
the actual type [aT] is.
Hope that helps.
--
THINGS TO DO IF I BECOME AN EVIL OVERLORD #16
I will never utter the sentence "But before I kill you, there's just
one thing I want to know."
----- Original Message -----
From: "Murali Mani" <mani@CS.UCLA.EDU>
To: "Joe English" <jenglish@flightlab.com>
Cc: "Champion, Mike" <Mike.Champion@SoftwareAG-USA.com>;
<www-xml-query-comments@w3.org>; <xml-dev@lists.xml.org>
Sent: Thursday, January 03, 2002 10:39 PM
Subject: Re: [xml-dev] The use of XML syntax in XML Query
>
> i am not following this fully -- I am stuck with the previous
> question.. however, consider this example also..
>
> schema --
> Doc -> doc (a, A, b)
> A -> dummy (a, A?, b)
>
> query -- doc//(a | b)
>
> resulting exact type -- (a^n, b^n) -- this cannot be expressed as a
> regular tree grammar or XML Schema whatever.
>
> For those following this, where do you think this fits as opposed to
> element construction example mentioned in Prof. Suciu's analysis, or
> previously by Prof. Vianu?? can we say that the query in the example I
> gave is the outlier of the tree??
>
> note: I have not followed these results closely, but if anyone can tell us
> something, that will be good.
>
> cheers and regards - murali.
>
> On Thu, 3 Jan 2002, Joe English wrote:
>
> >
> > 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
> >
> > That paper has an interesting example. Paraphrasing some,
> > given the input DTD:
> >
> > <!ELEMENT root (elm*)>
> >
> > the query:
> >
> > element result {
> > for $x in //elm RETURN element a { $x/text() },
> > for $x in //elm RETURN element b { $x/text() },
> > for $x in //elm RETURN element c { $x/text() }
> > }
> >
> > and the output DTD:
> >
> > <!ELEMENT result (
> > ( (a,a)*, (b,b)*, (c,c)* )
> > | ( a,(a,a)*, b,(b,b)*, c,(c,c)* ) ) >
> >
> > (which says that the number of a's, b's, and c's all have
> > the same parity, i.e., either an even number of each or an
> > odd number of each), then the query will always produce a
> > valid output given a valid input. However, no type system
> > based on regular grammars will be able to deduce this fact.
> > The best a type inferencing algorithm will be able to come
> > up with given the input DTD and query is:
> >
> > <!ELEMENT result (a*, b*, c*)>
> >
> > which is a proper superset of the output DTD. The *real*
> > language generated by the query is
> >
> > element result { a*n, b*n, c*n : n >= 0 }
> >
> > (where "a*n" means, roughly, <element name="a" minOccurs="n"
> > maxOccurs="n"/>), which is a proper subset of the output DTD
> > (so the query is type-safe) but this language is not expressible
> > in a regular grammar.
> >
> > Basically this means that any type inferencing algorithm
> > for XQuery (or an XQuery-like language) based on DTDs (or a
> > DTD-like type system) cannot be complete: it will always
> > reject some type-safe queries.
> >
> > That doesn't mean that a *sound* type inferencing algorithm
> > isn't possible, i.e., one that produces no false positives
> > but may answer "no", "maybe", or "I don't know" on some
> > correct inputs. Personally I don't think this limitation
> > is much of a problem in practice: ML and Haskell have the
> > same property and their type systems are still tremendously
> > useful.
> >
> > The astute reader will note that the example output DTD is not
> > deterministic. It's not clear whether requiring deterministic
> > content models helps the problem any; my guess is that it doesn't.
> >
> > As for Suciu's claim that "When one adds joins, typechecking
> > becomes undecidable" [p. 5]: I'm not quite up to debunking it,
> > but it sounds bogus to me; regular languages are closed under
> > cartesian product and homomorphisms, which is basically what
> > a join gives you.
> >
> >
> > --Joe English
> >
> > jenglish@flightlab.com
> >
> > -----------------------------------------------------------------
> > The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
> > initiative of OASIS <http://www.oasis-open.org>
> >
> > The list archives are at http://lists.xml.org/archives/xml-dev/
> >
> > To subscribe or unsubscribe from this list use the subscription
> > manager: <http://lists.xml.org/ob/adm.pl>
> >
>
>
> -----------------------------------------------------------------
> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
> initiative of OASIS <http://www.oasis-open.org>
>
> The list archives are at http://lists.xml.org/archives/xml-dev/
>
> To subscribe or unsubscribe from this list use the subscription
> manager: <http://lists.xml.org/ob/adm.pl>
_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com
|
