Paper Info
Title
Static Analysis and Query Answering for Incomplete Data Trees with Constraints.
Abstract
Data trees serve as an abstraction of XML documents: in such trees, every node comes with a label from a finite alphabet, as well as a data value from an infinite set. Incomplete data trees model XML documents with incomplete information; they may include both structural incompleteness and incompleteness of data. Here we study two basic problems for incomplete data trees under typical constraints such as keys and foreign keys. The first problem is consistency of specifications of incomplete data trees. We show that many of recently established results on consistency of constraints and schema descriptions can be transferred to the consistency of incomplete tree specifications without any increase in complexity. After that we examine query answering over incomplete data trees under constraints, and show that tractable bounds can be recovered under key constraints, but are lost under foreign keys.
Year
DOI
Venue
2013
10.1007/978-3-642-41660-6_15
In Search of Elegance in the Theory and Practice of Computation
Field
DocType
Citations 
Query optimization,Conjunctive query,XML,Information retrieval,Computer science,Infinite set,Foreign key,Data integrity,Tree automaton,Complete information
Conference
0
PageRank 
References 
Authors
0.34
16
3
Name
Order
Citations
PageRank
Amélie Gheerbrant11318.53
Leonid Libkin23446764.02
Juan L. Reutter339034.15