Static Analysis and Query Answering for Incomplete Data Trees with Constraints

Amelie Gheerbrant, Leonid Libkin, Juan Reutter

Research output: Chapter in Book/Report/Conference proceedingChapter


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.
Original languageEnglish
Title of host publicationIn Search of Elegance in the Theory and Practice of Computation - Essays Dedicated to Peter Buneman
PublisherSpringer-Verlag GmbH
Number of pages18
ISBN (Electronic)978-3-642-41660-6
ISBN (Print)978-3-642-41659-0
Publication statusPublished - 2013

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Dive into the research topics of 'Static Analysis and Query Answering for Incomplete Data Trees with Constraints'. Together they form a unique fingerprint.

Cite this