Detail

Completeness of Queries over Incomplete Databases

Data completeness is an important aspect of data quality, which lacks formal foundations. We present techniques to infer the completeness of query answers from information about the completeness of parts of a generally incomplete database. In our framework, completeness of a database can be described in two ways: by table completeness (TC) statements, which say that certain parts of a relation are complete, and by query completeness (QC) statements, which say that the set of answers of a query is complete. We identify as core problem to decide whether table completeness entails query completeness (TC-QC). We develop decision procedures and assess the complexity of TC-QC inferences depending on the languages of the TC and QC statements. With a prototypical implementation we show how completeness reasoning can be realized using answer set programming engines. We conclude by discussing applications of our techniques to RDF data and how knowledge about business processes can yield information about data completeness.