A Study of a Positive Fragment of Path Queries: Expressiveness, Normal Form and Minimization

作者：Wu Yuqing; Van Gucht Dirk; Gyssens Marc^*; Paredaens Jan

来源：Computer Journal, 2011, 54(7): 1091-1118.

DOI：10.1093/comjnl/bxq055

• XML
• path query
• normal form
• expressiveness
• minimization

We study the expressiveness of a positive fragment of path queries, denoted Path(+), on documents that can be represented as node-labeled trees. The expressiveness of Path(+) is studied from two angles. First, we establish that Path(+) is equivalent in expressive power to two particular subfragments, as well as to the class of tree queries, a subclass of the first-order conjunctive queries defined over the label, parent-child and child-parent predicates. The translation algorithm from tree queries to Path(+) yields a normal form for Path(+) queries. Using this normal form, we can decompose a Path(+) query into subqueries that can be expressed in a very small fragment of Path(+) for which efficient evaluation strategies are available. Second, we characterize the expressiveness of Path(+) in terms of its ability to resolve nodes in a This result is used to show that each tree query can be translated to a unique, equivalent and minimal tree query. The combination of these results yields an effective strategy to evaluate a large class of path queries on documents.

• 出版日期2011-7