[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: The use of XML syntax in XML Query

• To: www-xml-query-comments@w..., xml-dev@l...
• Subject: Re: The use of XML syntax in XML Query
• From: Joe English <jenglish@f...>
• Date: Thu, 03 Jan 2002 19:21:23 -0800
• In-reply-to: <200201040128.RAA30467@d...>
• References: <200201040128.RAA30467@d...> <027101c1952b$d87149c0$0500a8c0@carnage> <9A4FC925410C024792B85198DF1E97E4021BDE54@u...>

I 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
> [...]
> 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.
>

Having taken a look at the paper where Dan actually *proves*
this to be the case [1], I take that back :-)

But this paper appears to be using a stronger than usual
definition of the typechecking problem:

    "Given an input DTD tau_1, an output DTD tau_2 [...],
    and a query q, we say that q _typechecks_ (wrt. tau_1 and tau_2)
    iff q(inst(tau_1)) [is a proper subset of] inst(tau_2)"

That is, it demands that the algorithm be both sound *and*
complete.  The paper then presents some (impressive!) results
showing that this problem is decidable for certain restricted
classes of query languages and DTDs [2], but for "specialized DTDs" 
(roughly speaking: something at the level of RELAX-NG) or full XQuery,
the typechecking problem as stated is undecidable.

On the other hand, in practice a weaker definition of typechecking
is often satisfactory: "if a query q typechecks wrt. L1 and L2,
then for all s in L1, q(s) is in L2".  A guarantee from a type
checker that a program never produces bad output from good input is
a useful thing to have, even if the typechecker rejects some
correct programs.


[1] "XML with Data Values: Typechecking Revisited",
    <URL: http://www.cs.washington.edu/homes/suciu/files/_F1359680672.ps >

[2] the term "DTD" is used in the paper as a generic term for 
    grammar-based schema languages, not XML DTDs per se.

--Joe English

  jenglish@f...

• References:
  • Re: The use of XML syntax in XML Query
    • From: Joe English <jenglish@f...>
  • Re: The use of XML syntax in XML Query
    • From: "Dare Obasanjo" <kpako@y...>
  • RE: The use of XML syntax in XML Query
    • From: "Champion, Mike" <Mike.Champion@S...>

• Prev by Date: Re: The use of XML syntax in XML Query
• Next by Date: Question on using xs:pattern to restrict xs:dateTime
• Previous by thread: Re: The use of XML syntax in XML Query
• Next by thread: RE: The use of XML syntax in XML Query
• Index(es):
  • Date
  • Thread