|
Title
|
|
|
|
Capturing missing tuples and missing values
| |
|
Author
|
|
|
|
| |
|
Abstract
|
|
|
|
| Databases in real life are often neither entirely closed-world nor entirely open-world. Indeed, databases in an enterprise are typically partially closed, in which a part of the data is constrained by master data that contains complete information about the enterprise in certain aspects [21]. It has been shown that despite missing tuples, such a database may turn out to have complete information for answering a query [9]. This paper studies partially closed databases from which both tuples and values may be missing. We specify such a database in terms of conditional tables constrained by master data, referred to as c-instances. We first propose three models to characterize whether a c-instance T is complete for a query Q relative to master data. That is, depending on how missing values in T are instantiated, the answer to Q in T remains unchanged when new tuples are added. We then investigate four problems, to determine (a) whether a given c-instance is complete for a query Q, (b) whether there exists a c-instance that is complete for Q relative to master data available, (c) whether a c-instance is a minimal-size database that is complete for Q, and (d) whether there exists a c-instance of a bounded size that is complete for Q. We establish matching lower and upper bounds on these problems for queries expressed in a variety of languages, in each of the three models for specifying relative completeness. |
| |
|
Language
|
|
|
|
English
| |
|
Source (book)
|
|
|
|
Proceedings of the 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2010), Indianapolis, Indiana, USA, June 6-11, 2010 / Paredaens, Jan [edit.]; et al.
| |
|
Publication
|
|
|
|
S.l.
:
ACM
,
2010
| |
|
ISBN
|
|
|
|
978-1-4503-0033-9
| |
|
DOI
|
|
|
|
10.1145/1807085.1807109
| |
|
Volume/pages
|
|
|
|
p. 169-178
| |
|
ISI
|
|
|
|
000286908000017
| |
|
Full text (Publisher's DOI)
|
|
|
|
| |
|