Title: Completeness of Queries over Incomplete Databases
By: Werner Nutt (Free University of Bozen-Bolzano)
Abstract:
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.
Short-bio:
Werner Nutt is a professor at the Faculty of Computer Science at the University of Bozen since 2005. Prior to this, he was reader at Heriot-Watt University, Edinburgh (2000-2005), visiting professor at the Hebrew University of Jerusalem, and research scientist at the German Research Center for Artificial Intelligence (DFKI) in Saarbruecken (1992-2000). His research interests are in knowledge representation and databases.