Reasoning about keys for XML

Peter Buneman, Susan Davidson, Wenfei Fan, Carmem Hara, Wangchiew Tan

Research output: Working paper

Abstract / Description of output

We study absolute and relative keys for XML, and investigate their associated decision problems. We argue that these keys are important to many forms of hierarchically structured data including XML documents. In contrast to other proposals of keys for XML, these keys can be reasoned about efficiently. We show that the (finite) satisfiability problem for these keys is trivial, and their (finite) implication problem is finitely axiomatizable and decidable in PTIME in the size of keys.
Original languageEnglish
PublisherSpringer
Number of pages16
Volume2397
ISBN (Electronic)978-3-540-46093-0
ISBN (Print)978-3-540-44080-2
Publication statusPublished - 2000

Keywords / Materials (for Non-textual outputs)

  • bibtex-import

Fingerprint

Dive into the research topics of 'Reasoning about keys for XML'. Together they form a unique fingerprint.

Cite this