Edinburgh Research Explorer

Static Analysis and Query Answering for Incomplete Data Trees with Constraints

Research output: Chapter in Book/Report/Conference proceedingChapter

Original languageEnglish
Title of host publicationIn Search of Elegance in the Theory and Practice of Computation - Essays Dedicated to Peter Buneman
PublisherSpringer-Verlag GmbH
Pages273-290
Number of pages18
ISBN (Electronic)978-3-642-41660-6
ISBN (Print)978-3-642-41659-0
DOIs
Publication statusPublished - 2013

Publication series

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

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.

Download statistics

No data available

ID: 13657552