Paper Info
Title
Expressive, yet tractable XML keys
Abstract
Constraints are important for a variety of XML recommendations and applications. Consequently, there are numerous opportunities for advancing the treatment of XML semantics. In particular, suitable notions of keys will enhance XML's capabilities of modeling, managing and processing native XML data. However, the different ways of accessing and comparing XML elements make it challenging to balance expressiveness and tractability. We investigate XML keys which uniquely identify XML elements based on a very general notion of value-equality: isomorphic subtrees with the identity on data values. Previously, an XML key fragment has been recognised that is robust in the sense that its implication problem can be expressed as the reachability problem in a suitable digraph. We analyse the impact of extending this fragment by structural keys that uniquely identify XML elements independently of any data. We establish a sound and complete set of inference rules for this expressive fragment of XML keys, and encode these rules in an algorithm that decides the associated implication problem in time quadratic in the size of the input keys. Consequently, we gain significant expressiveness without any loss of efficiency in comparison to less expressive XML key fragments.
Year
DOI
Venue
2009
10.1145/1516360.1516402
EDBT
Keywords
Field
DocType
expressive xml key fragment,tractable xml key,xml element,associated implication problem,xml semantics,xml recommendation,native xml data,xml key fragment,data value,expressive fragment,xml key,data privacy,inference rule
Data mining,XML Encryption,Efficient XML Interchange,XML validation,Computer science,Document Structure Description,XML database,XML schema,Database,XML Schema Editor,XML Signature
Conference
Citations 
PageRank 
References 
13
0.54
24
Authors
2
Name
Order
Citations
PageRank
Sven Hartmann140942.86
Sebastian Link218512.50