Edinburgh Research Explorer

Reasoning about Keys for XML

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

Original languageEnglish
Title of host publicationDatabase Programming Languages
Subtitle of host publication8th International Workshop, DBPL 2001 Frascati, Italy, September 8–10, 2001 Revised Papers
EditorsGiorgio Ghelli, Gösta Grahne
PublisherSpringer Berlin Heidelberg
Pages133-148
Number of pages16
Volume2397
ISBN (Electronic)978-3-540-46093-0
ISBN (Print)978-3-540-44080-2
DOIs
Publication statusPublished - 2002

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume2397

Abstract

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.

ID: 16502928