Reasoning about keys for XML

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

Reasoning about keys for XML

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

Research output: Working paper

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.

Original language	English
Publisher	Springer Berlin Heidelberg
Number of pages	16
Volume	2397
ISBN (Electronic)	978-3-540-46093-0
ISBN (Print)	978-3-540-44080-2
Publication status	Published - 2000

Keywords

bibtex-import

Cite this

@techreport{5cf4b6f63f2240d591a5fc018de3f6dd,

title = "Reasoning about keys for XML",

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.",

keywords = "bibtex-import",

author = "Peter Buneman and Susan Davidson and Wenfei Fan and Carmem Hara and Wangchiew Tan",

year = "2000",

language = "English",

isbn = "978-3-540-44080-2",

volume = "2397",

publisher = "Springer Berlin Heidelberg",

type = "WorkingPaper",

institution = "Springer Berlin Heidelberg",

}

TY - UNPB

T1 - Reasoning about keys for XML

AU - Buneman, Peter

AU - Davidson, Susan

AU - Fan, Wenfei

AU - Hara, Carmem

AU - Tan, Wangchiew

PY - 2000

Y1 - 2000

N2 - 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.

AB - 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.

KW - bibtex-import

M3 - Working paper

SN - 978-3-540-44080-2

VL - 2397

BT - Reasoning about keys for XML

PB - Springer Berlin Heidelberg

ER -