Certain query answering in partially consistent databases
Sergio Greco, Fabian Pijcke, Jef Wijsen · Proceedings of the VLDB Endowment · 2014
A database is called uncertain if two or more tuples of the same relation are allowed to agree on their primary key. Intuitively, such tuples act as alternatives for each other. A repair (or possible world) of such uncertain database is obtained by selecting a maximal number of tuples without ever selecting two tuples of the same relation that agree on their primary key. For a Boolean query q , the problem CERTAINTY( q ) takes as input an uncertain database db and asks whether q evaluates to true on every repair of db. In recent years, the complexity of CERTAINTY( q ) has been studied under different restrictions on q . These complexity studies have assumed no restrictions on the uncertain databases that are input to CERTAINTY( q ). In practice, however, it may be known that these input databases are partially consistent, in the sense that they satisfy some dependencies (e.g., functional dependencies). In this article, we introduce the problem CERTAINTY( q ) in the presence of a set Σ of dependencies. The problem CERTAINTY( q , Σ) takes as input an uncertain database db that satisfies Σ, and asks whether every repair of db satisfies q . We focus on the complexity of CERTAINTY( q , Σ) when q is an acyclic conjunctive query without self-join, and Σ is a set of functional dependencies and join dependencies, the latter of a particular form. We provide an algorithm that, given q and Σ, decides whether CERTAINTY( q , Σ) is first-order expressible. Moreover, we show how to effectively construct a first-order definition of CERTAINTY( q , Σ) if it exists.