[
Lists Home |
Date Index |
Thread Index
]
Dare, I do not know why you say tree matching, tree pattern matching is a
very different concept.
For your example, RELAX NG with subtyping will again return false. Again
you are combining two orthogonal features as if one implies the other. The
two features you are combining are -- regular tree grammars and implicit
(unnamed) subtyping. This is not true.
You work more closely with standards, however I try to catch up whenever I
get a chance. I know the internal workings of some systems -- some XML ->
relational conversion systems which has people from XQuery working group
etc -- even their system implementation is based on regular tree grammars.
I am quite sure also that the subtyping of XQuery is based purely on
regular tree language inclusion. You can map extension and restriction to
one framework, and this is used to do type casting etc..
Further more, there is thin line between W3C XML Schema and RELAX NG if
you abstract out all the complexities of W3C XML Schema out -- W3C XML
Schema is essentially a single type tree grammar (of course, with a couple
of mistakes here and there :)).. So they will feel like the same -- once
again, I am quite sure there is only one way type inferencing can work --
regular tree grammars, Given the regular tree grammar, you can probably
relax it to get a single type tree grammar from it.. But the underlying
principles are regular tree grammars -- what i mean is even if the user
declares the output is a particular type, you should infer what the
program does and check if the output type specified conforms to the
inferred type.. this inference is based on regular tree grammars.
Implicit subtyping is a very interesting research problem with open
issues, and very interesting approaches can be found from Prof. Dan
Suciu's work.
To talk about tree matching, tree matching as how the automata community
understand is different from the way you use it.. Consider the simple
example of string matching..
given an input string -- aabbcc
and given a pattern aaa_* -- will the input string match the pattern --
no.
There is an equivalent matching when you consider trees and tree patterns
given an input tree
<book>
<author/>
<author/>
</book>
and an input pattern book [author author author]
the input tree will not match the pattern. However, XQuery, XPath
semantics considers the pattern as a set of paths and tries to see if each
path matches the tree..
XQuery as such does not explicitly support tree pattern matching. I have
seen regarding tree pattern matching the following works -- (a) The thesis
by Phil Kilpelainnen in 1992 -- quite popular among the tree pattern
matching community (b) Extended Path expressions for XML (PODS 2002) (c) a
work which was presented at Extreme 2002 by a student -- he had a nice
understanding of the differences, the trade-offs etc between tree pattern
matching and the technique XQuery is based on.
<warning>speaking for himself only</warning>
cheers and regards - murali.
On Fri, 30 Aug 2002, Dare Obasanjo wrote:
>
> > -----Original Message-----
> > From: Murali Mani [mailto:mani@CS.UCLA.EDU]
> > Sent: Friday, August 30, 2002 2:49 PM
> > To: Dare Obasanjo
> > Cc: Maciejewski, Thomas; xml-dev@lists.xml.org
> >
> > This support for named subtyping does not affect in any way
> > the fact that the type inferencing for XQuery is based on
> > regular tree grammars. Type inferencing, regular tree
> > grammars and closure under operations forms the XQuery core,
> > and they go together.
>
> Like I said, the formal semantics is behind the times but [from what
> I've seen] the goal of the working group is too make type inferencing
> based on named W3C XML Schema types not tree matching. I've given sample
> queries in the past on this list that show why named typing makes more
> sense than tree matching[0].
>
> Here's the query again, given the following schema
>
> <xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema";
> elementFormDefault="qualified"
> targetNamespace="http://www.example.com";
> xmlns:myns="http://www.example.com";>
>
> <xs:element name="foo" type="myns:fooType" />
>
> <xs:complexType name="fooType" >
> <xs:element name="bar" minOccurs="3" maxOccurs="6" />
> </xs:complexType>
>
> </xs:schema>
>
> and the query
>
> schema namespace myns="http://www.example.com";; at
> "http:/www.example.com/foo.xsd"
> $foo = <myns:foo>{
> document("http://www.example.org/bar.xml";)//myns:bar }</myns:foo>
> $foo instance of element of type myns:fooType
>
> What is the result?
>
> i) NAMED TYPING ANSWER: False, because the $foo variable has type
> xs:anyType until validation has been performed on it to confirm that it
> matches the schema.
>
> ii) TREE MATCHING ANSWER: True or False depending on contents of
> document at http://www.example.org/bar.xml. Basically the equivalent of
> validation occurs implicitly at runtime any time a type needs to be
> inferred.
>
>
>
> [0] http://lists.xml.org/archives/xml-dev/200207/msg01024.html
>
>
> --
> PITHY WORDS OF WISDOM
> Old cars never die, they just smell that way.
>
> This posting is provided "AS IS" with no warranties, and confers no
> rights.
>
|
