Welcome to DiSC 2002
SIGMOD 2001
PODS 2001
= PODS'01 Website
= SIGMOD/PODS'01 Plena
<<< = PODS'01 Papers>>>
= Invited Talks
= Award Talks
= Tutorials
SIGMOD RECORD 2001
CIKM 2001
CoopIS 2001
DASFAA 2001
DASFAA 2000
DBPL 2001
Data Engineering Bul
DEXA_EC-WEB 2001
DMKD 2001
DPDJ 2001
HYPERTEXT 2001
ICDE 2001
ICDM 2001
ICDT 2001
JCDL 2001
KDD 2001
KDD_EXPLORATIONS 20
KRDB 2001
MDM 2001
MIR 2001
MIS 2001
RIDE 2001
SBBD 2001
SIGIR 2001
SIGIR FORUM 2001
SSDBM 2001
SSTD 2001
TODS 2001
TIME 2001
VLDB 2001
VLDBJ 2001

Extended Path Expressions for XML


Makoto Murata

  View Paper (PDF)  

Return to XML


Abstract

Query languages for XML often use path expressions to locate elements in XML documents. Path expressions are regular expressions such that underlying alphabets represent conditions on nodes. Path expressions represent conditions on paths from the root, but do not represent conditions on siblings, siblings of ancestors, and descendants of such siblings. In order to capture such conditions, we propose to extend underlying alphabets. Each symbol in an extended alphabet is a triplet (e1; a;e2), where a is a condition on nodes, and e1 (e2) is a condition on elder (resp. younger) siblings and their descendants; e1 and e2 are represented by hedge regular expressions, which are as expressive as hedge automata (hedges are ordered sequences of trees). Nodes matching such an extended path expression can be located by traversing the XML document twice. Furthermore, given an input schema and a query operation controlled by anex-tended path expression, it is possible to construct an output schema. This is done by identifying where in the input schema the given extended path expression is satisfied.


DiSC'02 © 2003 Association for Computing Machinery