Edinburgh Research Explorer

Keys with Upward Wildcards for XML

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

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


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.

ID: 19849735