Keys with Upward Wildcards for XML

Wenfei Fan, Peter Schwenzer, Kun Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The paper proposes a key constraint language for XML and investigates its associated decision problems. The language is defined in terms of regular path expressions extended with downward and upward wildcards, which can not only move down XML document trees, but also upwards. In a uniform syntax it is capable of expressing both absolute keys and relative keys, which are important to hierarchically structured data. In addition, keys defined in the language can be reasoned about efficiently. The paper provides a sound and complete set of inference rules and a cubic time algorithm for determining implication of the keys.
Original languageEnglish
Title of host publicationDatabase and Expert Systems Applications
Subtitle of host publication12th International Conference, DEXA 2001 Munich, Germany, September 3-5, 2001, Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages11
ISBN (Electronic)978-3-540-44759-7
ISBN (Print)978-3-540-42527-4
Publication statusPublished - 2001


Dive into the research topics of 'Keys with Upward Wildcards for XML'. Together they form a unique fingerprint.

Cite this