Edinburgh Research Explorer

Capturing Missing Tuples and Missing Values

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Documents

Original languageEnglish
Title of host publicationPODS 2010: PROCEEDINGS OF THE TWENTY-NINTH ACM SIGMOD-SIGACT-SIGART SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS
Place of PublicationNEW YORK
PublisherASSOC COMPUTING MACHINERY
Pages169-178
Number of pages10
ISBN (Print)978-1-4503-0033-9
Publication statusPublished - 2010
Event29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems - Indianapolis
Duration: 6 Jun 201011 Jun 2010

Conference

Conference29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems
CityIndianapolis
Period6/06/1011/06/10

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 enter prise in certain aspects 121]. 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 mikes may be missing. We specify such a database in terms of conditional tables constrained by master data, referred tc as c-instances. We first propose three models to characterize whether a c-instance 7 is complete for a query Q relative to master data. That is, depending on how missing values in 7 are instantiated, the answer to Q in 7 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.

Event

29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems

6/06/1011/06/10

Indianapolis

Event: Conference

Download statistics

No data available

ID: 3169256