Consistent query answering is a generally accepted approach for querying inconsistent knowledge bases. A consistent answer to a query is a tuple entailed by every repair, where a repair is a consistent database that “minimally” differs from the original (possibly inconsistent) one. This is a somewhat coarse-grained classification of tuples into consistent and non-consistent does not provide much information about the non-consistent tuples (e.g., a tuple entailed by 99 out of 100 repairs might be considered “almost consistent”). To overcome this limitation, we propose a probabilistic approach to querying inconsistent knowledge bases, which provides more informative query answers by associating a degree of consistency with each query answer by associating a probability to each repair, depending on the changes needed to obtain it.
There has been a great deal of work on extracting reliable information from inconsistent
data, in both the AI and database communities. To deal with this problem, many
semantics of query answering have been proposed. Most of them are based on the consistent
query answering framework [
Regardless of the specific minimality criterion and repair primitive, all the resulting frameworks share the same drawback, which is a dichotomic classification of tuples in either consistent or non-consistent ones. This can provide very little information to users in many cases, as illustrated in the following example.
Example 1. Consider the knowledge base (D; ), where D contains the following facts: employee bob cs nyc mike cs nyc alice cs paris and is an ontology consisting of the following equality-generating dependency : employee(E1; D; C1); employee(E2; D; C2) ! C1 = C2:
As an example, the fact employee(bob; cs; nyc) states that bob is an employee working in the cs department located in nyc. The dependency says that every department must be located in a single city. Clearly, the first two facts are conflicting with the last one. There are two repairs for this inconsistent knowledge base, which are as follows (more details on the employed notion of repair will be provided in the following): bob cs nyc R1 = mike cs nyc alice cs nyc
bob cs paris R2 = mike cs paris alice cs paris Repair R1 is obtained from the original database by replacing paris with nyc, while R2 is obtained by replacing nyc with paris. The query asking for the city of the cs department has no consistent answers. Thus, a user trying to extract this information from the knowledge base is left with no answer altogether, all she/he gets is the empty set.
To overcome the limitation illustrated in the example above, we propose a probabilistic approach to querying inconsistent knowledge bases whose aim is to provide more informative query answers than the classical consistent query answering framework. The main idea is to give a “degree of consistency” to every repair, which is then taken into account to assign a degree of consistency to query answers.
Example 2. Consider again the scenario of Example 1. The degree of consistency of R1 is 2/3, as nyc is supported by two facts out of three in the original knowledge base, while the degree of consistency of R2 is 1/3, as paris is supported by only one fact out of three.
Consider again the query asking for the city of the cs department. Rather than providing no information (like classical consistent query answers do), our query answers are nyc with confidence 2=3 (as this is entailed by R1), and paris with confidence 1=3 (as this is entailed by R2), which is much more informative than returning nothing.
The previous examples illustrate the limitation of providing only certain information and how this might be overcome by assigning a degree of consistency to query answers (notice that consistent query answers are still provided – they have degree 1).
In this paper, we consider knowledge bases where dependencies are expressed by means of equality-generating dependencies (EGDs). Equality-generating dependencies are one of the two major types of data dependencies—the other major type consists of tuple-generating dependencies (TGDs)—and can model several kinds of constraints arising in practice, such as functional dependencies and thus key dependencies.
In the presence of EGDs, the two main approaches to restore consistency are to perform fact deletions or fact updates. A drawback of the former is that entire facts are deleted to resolve inconsistency, even if they may still contain “reliable” information. Thus, in this paper we adopt a notion of repair based on fact updates (we will provide a precise definition in the following). Nonetheless, the ideas developed in this paper can be used also when a notion of repair based on fact deletions is adopted.
As we show, providing more informative query answers comes at a price: it is #Phard. In light of this result, we discuss further developments providing polynomial time algorithms to compute approximate query answers.
Related work. Most inconsistency-tolerant approaches in the literature adopt the classical
notion of repair (via fact deletions/insertions) and consistent query answer [
Basics. We assume the existence of the following pairwise disjoint (countably infinite) sets: a set Const of constants, a set Var of variables, and a set Null of labeled nulls. Nulls are denoted by the symbol ? subscripted with natural numbers. A term is a constant, variable, or null. We also assume a set of predicates, disjoint from the aforementioned sets, with each predicate being associated with an arity, which is a non-negative integer.
An atom is of the form p(t1; : : : ; tn), where p is an n-ary predicate and the ti’s are terms. We write an atom also as p(t), where t is a sequence of terms. An atom without variables is also called a fact. An instance is a finite multiset of facts. A database is a finite set of facts containing constants only. An instance containing only constants is said to be complete. Notice that, as opposed to databases, instances can contain duplicates— as shown in the following, instances are used in intermediate steps during repairs’ computation and it is needed to keep duplicates to count the number of modifications being made. We assume the existence of a function db converting a complete instance to a database by eliminating duplicates.
A homomorphism is a mapping h : Const[Var[Null ! Const[Var[Null that is the identity on Const. Homomorphisms are also applied to atoms and (multi) sets of atoms in the natural fashion, that is, h(p(t1; : : : ; tn)) = p(h(t1); : : : ; h(tn)), and h(S) = fh(A) j A 2 Sg for every (multi) set S of atoms. A valuation is a homomorphism whose image is Const, that is, (t) 2 Const for every t 2 Const [ Var [ Null.
An equality generating dependency (EGD) is a first-order formula of the form 8x '(x) ! xi = xj ; where '(x) is a conjunction of atoms (without labeled nulls) whose variables are exactly x, and xi and xj are variables from x. We call '(x) the body of , and call xi = xj the head of . We will omit the universal quantification in front of dependencies and assume that all variables are universally quantified.
With a slight abuse of notation, we sometimes treat a conjunction of atoms as the set of its atoms. An instance J satisfies , denoted J j= , if whenever there exists a homomorphism h s.t. h('(x)) J , then h(xi) = h(xj ). An instance J satisfies a set of EGDs, denoted J j= , if I j= for every 2 . A knowledge base (KB) is a pair (D; ), where D is a database and is a finite set of EGDs. We say that the knowledge base is consistent if D j= , otherwise it is inconsistent.
Acyclic EGDs. An argument of a set of EGDs is an expression of the form p[i], where p is an n-ary predicate appearing in and 1 i n. The argument graph of is a directed graph G = (V; E), where V is the set of all arguments of , and E contains a directed edge from p[i] to q[j] labeled iff there is an EGD such that: 2 – the body of contains an atom p(t1; : : : ; tn) such that either ti is a constant or ti is a variable occurring more than once in the body of , and – the body of contains an atom q(u1; : : : ; um) such that uj is a variable also appearing in the head of .
The dependency graph of is a directed graph = ( ; ), where is the set f( 1; 2) j G = (V; E) ^ (p([i]; q[j]; 1); (q[j]; r[k]; 2) 2 Eg. We say that is acyclic if its dependency graph is acyclic.
In the rest of the paper we consider acyclic sets of EGDs only. Thus, from now on,
is understood to be acyclic for every knowledge base (D; ). For acyclic sets of EGDs
we can define a partial order ( ; <) where EGDs in are ordered by reachability in
. The result of evaluating a query Q over a database D is denoted Q(D).
Repairs. The notion of repair used in this paper is based on updating facts and assumes
that conflicting facts denote an attribute-level uncertainty in the data [
Example 3. Consider the set of EGDs = f 1 : employee(X; Y1; Z1) ^ employee(X; Y2; Z2) ! Y1 = Y2;
2 : employee(X1; Y; Z1) ^ employee(X2; Y; Z2) ! Z1 = Z2g and the database D: bob cs rome bob math rome alice math nyc
By enforcing 1 into the first two facts, either cs or math can be chosen as bob’s department. If the latter is chosen, then the instance D0 below is obtained.
Suppose now that 2 is enforced into the last two facts of D0. Then, either rome or nyc can be chosen as math’s city. If the former is chosen, we obtain the instance D00: D0 = bob math rome bob math rome alice math nyc
D00 = No further dependency enforcement is applicable at this point and thus the database derived from D00 by eliminating duplicates is a repair.
The previous example informally illustrated the basic idea of the repair strategy we adopt. In the next section, we formally define it and show how to associate probabilities to repairs on the basis of the modifications that yielded them.
Notice that it might be possible to restore consistency in other different ways. For
instance, in the first step of the example above, one may modify the employee names.
However, we do not consider this option because it is unclear which (different) values
should be assigned (any constant in Const is a candidate value). For instance, bob in the
first fact might be replaced with rome, but this is somewhat arbitrary and indeed does
not make much sense. In contrast, our repair strategy chooses candidate values that are
somehow “justified” by the content of the database (e.g., in the example above, bob works
for either the cs or the math department). Moreover, when EGDs are key dependencies,
the aforementioned way of restoring consistency may lead to the introduction of entities
that are not meaningful. Indeed, our choice has been made by different approaches
relying on value updates—e.g., [
One problem of the classical notion of consistent query answer is that query answers can provide little information in the presence of conflicting information. The alternative approach proposed in this paper is to compute probabilistic answers by taking into account in to what extent information is updated to restore consistency.
In this section, we define probabilistic repairs and probabilistic query answers. In the next section, we show how to compute a compact representation of all probabilistic repairs. In both cases, we will use probabilistic instances, which are used to represent a single probabilistic repair in this section and are used to compactly represent all probabilistic repairs in the next section. Probabilistic instances are instances augmented with a set of “probability assignments”—intuitively, expressions stating conditions on nulls and probabilities on the values they can take.
More formally, let C be the set of all expressions, called conditions, that can be built using the standard logical connectives ^, _, :, and expressions of the form ti = tj , true, and false, where ti; tj 2 Const [ Null. We will also use ti 6= tj as a shorthand for :(ti = tj ). A homomorphism h satisfies a condition ', denoted h j= ', if h(') is true.
A probability assignment is an expression of the form P ('1 j '2) = p, where '1, '2 are conditions and p 2 [0; 1].
A homomorphism h satisfies a probability assignment P ('1 j '2) = p if the following holds true: if h j= '2 then h j= '1. Also, h satisfies a set of probability assignments, denoted h j= , if h satisfies every probability assignment in . For ease of presentation, a probability assignment of the form P ('1 j true) = p will be simply written as P ('1) = p.
A probabilistic instance (PI) is a pair K = (J; ), where J is an instance and is a finite set of probability assignments. For any valuation , we define
P r( ; K) = fp j P ('1 j '2) = p 2 and j= '2g: The semantics of K is given by the set of its probabilistic worlds, that is, the set of pairs (instance, probability) defined as follows: pw (K) = f( (J ); P r( ; K)) j is a valuation s.t. j= ^ P r( ; K) > 0g:
The probabilistic repairs of an inconsistent knowledge base (D; ) are computed starting from the probabilistic instance (D; ;) and iteratively enforcing EGDs (following a topological sorting of ). During the repair process we keep track of which values have been updated and how many modifications have been applied using labeled nulls and probability assignments. The enforcement of an EGD, which we call probabilistic repair step, is informally shown in the next example.
Example 4. Consider the knowledge base (D; ), where D and are from Example 3. Starting from the probabilistic instance (D; ;), by enforcing 1 into the first two facts, either cs or math can be chosen as bob’s department. Therefore we obtain the following two (alternative) probabilistic instances K1 (left) and K2 (right): bob ?1 bob ?1 alice math rome rome nyc P (?1= cs) = 1=2
As D1 j= , (db(D1); 1=2) is a probabilistic repair. On the other hand, D2 6j= , and thus we need to keep applying pr-steps over K2. By enforcing 2 over the first and third facts of K2 we can get the following two (alternative) probabilistic instances K3 (left) and K4 (right): bob ?1 bob ?1 alice math
?2 P (?1= math) = 1=2 P (?2= rome) = 1=2 ?2 rome In the rest of the paper, for every probabilistic instances (J; ), we report the probability assignments in under J .
Since D3 j= , (db(D3); 1=4) is a probabilistic repair. On the other hand, D4 6j= , and thus further pr-steps need to applied to K4. By enforcing 2 over the first two facts of K4 we can get the following two (alternative) probabilistic instances K5 (left) and K6 (right): Since D5 j= and D6 j= , both (db(D5); 1=12) and (db(D6); 1=6) are probabilistic repairs, and no further pr-step need to be applied.
Thus, the probabilistic repairs are (db(D1); 1=2), (db(D3); 1=4), (db(D5); 1=12), and (db(D6); 1=6). Notice that the sum of the probabilities of the probabilistic repairs is 1. Also, notice that D3 and D5 coincide. They might be replaced by a single probabilistic repair (D0; 1=4 + 1=12), where D0 = D3 = D5. However, this does not affect query answering, that is, the probabilistic query answers are the same in both cases. 4
In light of previous result, in the full version of this paper we develop a polynomial time algorithm to compute approximate query answers where point probability are approximated by probability intervals. Thus, rather than providing query answers of the form (t; p), where t is a tuple and p is its probability, our approximation algorithm gives query answers of the form (t; [`; u]) guaranteeing that p 2 [`; u].
In order to do that, we define probabilistic universal repairs, i.e., compact
representations of all repairs along with their degrees of consistency. This is one of the main tools
used by our approximation algorithm, which works as follows: (i) it computes a universal
probabilistic repair, (ii) it evaluates the given query over the universal probabilistic repair
so as to produce a set of tuples associated with conditions (which keep track of how
each tuple is derived), and (iii) it combines tuples’ conditions with probability
assignments of the universal probabilistic repair to derive the approximate intervals. Further
developments should consider more general frameworks with TGDs [
1. Periklis Andritsos, Ariel Fuxman, and Renée J. Miller. Clean answers over dirty databases: A probabilistic approach. In ICDE, page 30, 2006.