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 S of dependencies. The problem CERTAINTY(q,S) 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,S) when q is an acyclic conjunctive query without self-join, and S is a set of functional dependencies and join dependencies, the latter of a particular form. We provide an algorithm that, given q and S, decides whether CERTAINTY(q,S) is first-order expressible. Moreover, we show how to effectively construct a first-order definition of CERTAINTY(q,S) if it exists.

Certain Query Answering in Partially Consistent Databases

GRECO, Sergio;
2014

Abstract

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 S of dependencies. The problem CERTAINTY(q,S) 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,S) when q is an acyclic conjunctive query without self-join, and S is a set of functional dependencies and join dependencies, the latter of a particular form. We provide an algorithm that, given q and S, decides whether CERTAINTY(q,S) is first-order expressible. Moreover, we show how to effectively construct a first-order definition of CERTAINTY(q,S) if it exists.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.11770/136275
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? ND
social impact