W3C home > Mailing lists > Public > www-ql@w3.org > January to March 2004

Re: Query on the XML graph

From: Michael Brundage <xquery@comcast.net>
Date: Sun, 08 Feb 2004 20:20:25 -0800
To: Jim Tivy <jimt@bluestream.com>, Jiang Ming Fei <mfjiang@cse.cuhk.edu.hk>, "www-ql@w3.org 2" <www-ql@w3.org>
Message-ID: <BC4C4A89.100C%xquery@comcast.net>

XPath can follow ID/IDREF edges (in one direction) using the id() function.

Also, XPath can do self-joins, and when extended with the document() (or
doc()) function, it can do cross-document joins.  The kinds of joins that
can be expressed are limited by XPath's inability to introduce variables
(aliases).

Some joins are built-in to the semantics of XPath.  For example,
//A[B/C > B/D]
Iterates over the B children of A twice (independently, as a cross-product).


Other joins are possible using absolute paths in predicates to achieve
independence.

For example, given a structure containing Employee elements with ID and
ReportsTo attributes (typed as ID, IDREF, respectively), here are some joins
expressed using XPath 1.0:

(: the manager of a particular employee :)
Id(//Employee[@ID='X1']/@ReportsTo)

(: all managers - i.e., all employees with at least one direct report :)
//Employee[//Employee/@ReportsTo = @ID]

(: employees who report to people not in the organization, or report to no
one :)
//Employee[not(@ReportsTo = //Employee/@ID)]

(: their direct reports :)
//Employee[@ReportsTo = //Employee[not(@ReportsTo = //Employee/@ID)]/@ID]

etc.

Other joins are difficult to express, require unnatural syntax, or are
outright inexpressible using XPath 1.0:

(: all employees with at least two direct reports
  You'd like to do: :)
//Employee[count(//Employee[@ReportsTo = $outer/@ID]) >= 2]
(: or :)
//Employee[count(id(//Employee/@ReportsTo)[@ID = $outer/@ID]) >= 2]
(: but you have no way to introduce an alias to the outer Employee.
If XPath had an idref() function, you could do something like: :)
//Employee[count(idref(@ID)) >= 2]


(: managers whose entire organization is a certain size
 - there's no way to count subtrees unless the hierarchy already represents
the relationship.  For example, :)
//Employee[count(.//Employee)]
(: is trivial, but there's no way to recursively follow ID/IDREF edges :)

etc.



Hope this helps,
 
Michael Brundage
xquery@comcast.net

Writing as
Author, XQuery: The XML Query Language (Addison-Wesley, 2004)
Co-author, Professional XML Databases (Wrox Press, 2000)

not as
Technical Lead
Common Query Runtime/XML Query Processing
WebData XML Team
Microsoft



On 2/8/04 7:16 PM, "Jim Tivy" <jimt@bluestream.com> wrote:
> One way to accomplish cross document links is use foreignkey/primary key
> relationships and then do joins using XQuery.
> 
>> -----Original Message-----
>> From: www-ql-request@w3.org [mailto:www-ql-request@w3.org]On Behalf Of
>> Jiang Ming Fei
>> Sent: Sunday, February 08, 2004 6:48 PM
>> To: www-ql@w3.org
>> Cc: mfjiang@cse.cuhk.edu.hk
>> Subject: Query on the XML graph
>> 
>> 
>> 
>> I am now doing the research on the XML graph. What I am wondering about is
>> that how the nowaday query engines cope with the XML files that have idref
>> attributes, or XML graph? Since XPath have no notation for the idref/id
>> edge. Or I miss some details?  So can I always treat the XML document as
>> a tree with the special node, i.e. idref node?
>> 
>> Thank you in advance for your suggestion.
>> 
>> Regards,
>> Fianny
>> 
>> 
> 
Received on Sunday, 8 February 2004 23:20:28 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Saturday, 22 July 2006 00:10:19 GMT