The eld of Data Exchange has overcome many obstacles, but when it comes to negation in rule bodies combined with existentially quanti ed variables in rule heads, to unequalities ≠, as well as to inconsistency management, the same intractability barriers that plague the area of incomplete information arise. In this paper we develop an intuitionistic relevance-logic based semantics that allows us to extend the polynomial time \naive evaluation" technique to Data Exchange dependencies (TGDs and EGDs) with negated atoms and unequalities, and to Data Exchange Target Queries consisting of unions of conjunctive queries with negation and unequalities. The semantics is also paraconsistent, and avoids the intractability barriers encountered in inconsistency management as well.
The problem of data exchange poses one of the major challenges in distributed
information processing environments. A connection in such an environment can
be viewed as a labeled directed edge from a node representing a source database to
a node representing a target database. The edge-label denotes a schema mapping
that guides the middle-ware in restructuring the data from the source database
to t the requirements of the target database. Since its inception in 2003 by
Fagin et al. in [
These problems have been shown to admit e cient implementation, based
on a property colloquially called the naive evaluation property. The property
roughly says that the incompleteness of some domain values can be ignored, as
long as these values are distinguished from each other, and from the \ordinary"
domain values that denote named and known objects. The price to pay is that we
have to restrict the schema-mappings and target queries to be monotone. Most
attempts to include non-monotone features, such as negation (¬) and unequality
(≠), soon run into intractability barriers, due to the underlying issues of
incomplete information. For a comparison between di erent closed world semantics
the reader should consult [
We recall (see [
When it comes to dependencies with negation in the body, the main
proposals are the strati ed model the stable model and the well-founded model (for
de nitions, see [
∀X BIRD(X); ¬P EN GU IN (X) → F LY (X): If the source database is {BIRD(tweety)} it might be desirable to \defeasibly" conclude F LY (tweety). However, if we use the same semantics for ∀X COUN T RY (X); ¬N U KES(X) → F RIEN D(X); and the source database is {COU N T RY (sylvania)}, it might not be prudent to conclude F RIEN D(sylvania).
Intuitionistic logic rejects the law of the excluded middle and non-constructive
existence proofs. The motivation is usually epistemological, but it can also be
computational, as in Kleene's intuitionistic logic based on recursive predicates
[
If non-constructive existence proofs are epistemologically susceptible, what
can one say about defeasible reasoning? We contend that negative facts should
be explicitly derived, just as the positive ones are. In other words, only if we
have explicitly decided the fact ¬P EN GU IN (tweety) can we draw the
conclusion F LY (tweety). In this spirit we propose to use Nuel Belnap's four-valued
relevance logic R [
Belnap's logic also is paraconsistent, meaning that \if we have inconsistent
information about ducks, it is possible that our information about decimals can
still be trusted" (see Fitting [
The rest of this paper is organized as follows. The next section introduces the
notions used throughout the paper. This is followed by the section dedicated to
Belnap's Logic FOUR that plays a central role in this paper. Section 4 describes
the \naive evaluation" of conjunctive queries with negation, and Section 5 adds
negation to the bodies of tuple generating dependencies, in a way that allows us
to extend the \naive chase" (i.e. the standard chase [
For basic de nitions and concepts we refer to [
Signatures, schemas, languages etc. A signature consists of a nite set R = {R; S; : : :} of relation symbols (called the schema), a countably in nite set Vars = {X; Y; Z; : : :} of variables, a countably in nite set Nulls = {x; y; z; : : :} of nulls, and a countably in nite set Cons = {a; b; c; : : :} of constants. We assume that Nulls and Cons are semigroups under the ⋅ operation. Each relational symbol R ∈ R has an associated natural number ar(R), called the arity of R.
Let be a signature. The set of well-formed formulas (w 's) of the language L is de ned inductively by stating that each atom R(X), where R ∈ R and X ∈ (Vars ∪ Cons)ar(R), is a w , and then closing the set under ∨ ∧ ¬ ∃ ; ; ; , and ∀. If (X) is a L -formula, then v ars( ) denotes its variables, the sequence X denotes the free variables, and cons( ) the constants in . If (X) is a formula and v is the mapping X ↦ a, then (a) denotes the sentence (v(X)). If a w does not have any free variables, it is called a sentence.
Boolean valued instances. In algebraic semantics (see e.g. [
The well known Boolean valued models [
De nition 1. Let = (R; Vars; Nulls; Cons) be a database signature, and let B = (B; ∨; ∧; ¬; 0; 1) be a Boolean algebra. A B-instance I consists of the following parts: 1. A nite set of elements d om(I) ⊆ Cons ∪ Nulls, the domain of I, 2. cons(I) = d om(I) ∩ Cons, the constants of I, 3. The set nulls(I) = d om(I) ∩ Nulls, the nulls of I, and 4. For each R ∈ R and a ∈ d om(I)ar(R), an interpretation R(a)I ∈ B. De nition 2. Let be an L-sentence, B a Boolean algebra, ' ⊂ B an ultra lter in B, and I a B-interpretation. Then the satisfaction relation I ⊧B;' is de ned inductively as follows. 1. I ⊧B;' R(a), if R(a)I ∈ ', 2. I ⊧B;' ∧ , if I ∧ I ∈ ', 3. I ⊧B;' ¬ , if ¬( I ) ∈ ', 4. I ⊧B;' ∀X (X), if ⋀ a∈dom(I)ar(R) ( (a)I ) ∈ ', 5. I ⊧B;' → , if I ∈ ' entails that I ∈ '.
The natural partial order ≤ in B is de ned as ≤ i ∨ = . The partial order can be lifted to (B; ')-instances I and J by stipulating that I ≤ J if cons(I) ⊆ cons(J ), and there is a mapping h ∶ d om(I) → d om(J ), identity on the constants, such that R(a)I ≤ R(h(a))J , for all R ∈ R and a ∈ d om(I)ar(R). Such a mapping h is said to be a homomorphism from I to J . It is easily shown that ≤ is a partial order on the equivalence classes generated by the relation I ≃ J , de ned to hold i I ≤ J and J ≤ I.
Going back to the satisfaction relation ⊧B;', note that if B = {0; 1}, then B = 2 (the two-element Boolean algebra), and the unique ultra lter is { } 1 . Thus we can write simply ⊧2, and I ⊧2 becomes the standard two-valued semantics in which → behaves as material implication. Thus I ⊧2 → if and only if
I ≤ I . Here ≤ is the natural order, i.e. 0 ≤ 1, and I ≤ J means that there is a
classical database homomorphism [
Usually the certain answer is further restricted to only the named domain
values (the constants). For an instance I, de ne I↾ as function I restricted to
sequences of objects in cons(I). Thus, the usual certain answer is
C ert(q; X ) = ( {q(I) ∶ I ∈ X })↾ :
(1)
Note that q(X ) is what Libkin [
Belnap's logic F OU R
We are interested in Belnap's intuitionistic logic FOUR. This logic has a sound
and complete axiomatization in terms of a system R of relevance logic, and
→ becomes relevant entailment of rst degree (see [
The logic FOUR is a generalization of Kleene's strong three-valued logic.
FOUR has four truth-values ∅; {f }; {t}, and {f ; t}. Intuitively, assigning a
sentence the value {t} means that \the computer has been told that is true,"
(see [
Since truth-values are sets, they are naturally ordered by set-inclusion. The more elements the set contains, the more information the computer has about the truth. This gives rise to the information ordering, which we in the sequel will denote t. We can still retain the ≤-order, which is called the truth order, by stipulating that {f } ≤{t}, and that ∅ and {f ; t} are incomparable and both lie strictly between {f } and {t}. We shall use the following symbols: 0 for {f }, 1 for {t}, for ∅, and ⊺ for {f ; t}. Furthermore, ⊺ and are incomparable wrt ≤, and 0 and 1 are incomparable in t. All of this can be put together into a structure 4 = (4; ∨; ∧; /; .; ¬; 0; 1; ; ⊺); where 4 = {; ⊺; 0; 1}. Here ∨ is the least upper bound in the ≤-order, and ∧ the greatest lower bound (i.e. ⊺ ∨ = 1, and ⊺ ∧ = 0, etc). The least upper bound in the t-order is /, and the greatest lower bound is . (e.g. 0 / 1 = ⊺, and 0 . 1 = , etc). For negation, ¬ 1 = 0; ¬ 0 = 1; ¬ ⊺ = ⊺, and ¬ = . Consequently, (4; ∨; ∧; ¬; 0; 1) is a Boolean algebra.
Belnap's structure 4 has subsequently been generalized by Ginsberg and
Fitting to so called bilattices [
Since 4 is an algebra, it can be used to give meaning to L sentences, by
choosing the designated values '. Arieli and Avron [
A 4-instance is then a B-interpretation of De nition 1, where B = 4, and by noticing that (4; ∨; ∧; ¬; 0; 1) is a Boolean algebra, I ⊧4 can be read from De nition 2 of ⊧(B;'), by choosing B = 4, and ' = {⊺; 1}.
Let I and J be 4-instances, such that cons(I) ⊆ cons(J ) and let h be a mapping from d om(I) to d om(J ), such that h is identity on the constants. The mapping h is said to be a homomorphism from I to J , provided that R(a)I t R(h(a))J , for all R ∈ R and a ∈ d om(I)ar(R). The partial order t of 4 is lifted to 4-instances in the following de nition.
De nition 3. Let I and J be 4-instances such that cons(I) ⊆ cons(J ). We say that J is more informative than I, denoted I t J , if there is a homomorphism from I to J . Furthermore, if both I t J and J t I, we say that I and J are information equivalent, and denote it I ≐ J . Let I denote the set of all instances over . Then I ~≐ denotes the set of equivalence classes of instances induced by ≐.
Clearly t is a partial order on I ~≐. Due to space limitation, the de nitions
for relations . and / are omitted, they can be found in the full version [
Reducing FOUR to T WO. We now losslessy represent a 4-instance as a twovalued instance as follows.
De nition 4. 1. Let I be a 4-instance over schema R. The 2 -projection of I, denoted I↓2, is a two-valued Boolean instance over schema ⋃R∈R{R+; R−}, where (a) cons(I↓2) = cons(I), nulls(I↓2) = nulls(I), and d om(I↓2) = d om(I). (b) For all relations R ∈ R and a = a1; : : : ; a (R), where ai ∈ d om(I) for all iR∈−{(a1;):I:↓2: ;= 1(Rif)}R, (Ra)+I(au)I0↓,2 a=n1d i0f oRt(haer)wIiuse1., and 0 otherwise; and 2. Let I be a 2-instance. Then the 4-instance corresponding to I is I↑4, where (a) cons(I↑4) = cons(I), nulls(I↑4) = nulls(I), and d om(I↑4) = d om(I). (b) For all R ∈ R and a = a1; : : : ; a (R), for all i ∈ {1; : : : ; (R)}, R(a)I↑4 ⎧⎪ ⊺ if R+(a)I = 1 and R−(a)I = 1 ⎪ ⎪ ⎪⎪ if R+(a)I = 0 and R−(a)I = 0 = ⎨⎪ 1 if R+(a)I = 1 and R−(a)I = 0 ⎪ ⎪⎪⎪ 0 if R+(a)I = 0 and R−(a)I = 1 ⎩ 4
The intuitionistic semantics (4; {⊺; 1}) allows us to extend the (polynomial time) \naive evaluation" from unions of conjunctive queries to unions of conjunctive queries with negation. We next de ne CQs with negation. UCQs with negation is de ned similarly.
A literal is an expression of the form R(X) or ¬R(X), where R(X) is an atom in L . A conjunctive query with negation (NCQ) is a rst order formula of the form q = ∃Y (XY); where is a conjunction of literals. Consider now an NCQ n
n+m q = ∃Y
Ri(XY) ∧
¬Ri(XY): i=1 i=n+1 The NCQ q, when applied on an instance I, extends the interpretation I to also include the relation Q, de ned as follows. (3) De nition 5. Let I be a 4-instance and q = ∃Y (XY) an NCQ of the form (3). Let v range over all mappings from XY to d om(I). Then
Q(a)I =
n {v ∶ v(X)=a} i=1Ri(v(XY))I ∧ n+m i=n+1¬ Ri(v(XY))I ; for each a ∈ d om(I)SXS.
We next show that NCQs are monotonic in the information order t. By a
recent result of Gheerbrant et al. [
Theorem 1. Let q be an NCQ, and let I and J be 4-instances, such that I t J by homomorphism h. Then Q(a)I t Q(h(a))J , for all a ∈ d om(I)ar(Q).
Furthermore, the naive evaluation property of CQs on 2-instances can now be extended to NCQs on 4-instances. It turns out that an NCQ q can be evaluated naively on I↓2 by turning q into a UCQs, denoted q↓2. Assume q is of the form (3). Then q↓2 = ∃Y n i=1 n+m i=n+1 n i=1
m j=n+1 Ri+(XY) ∧
Ri−(XY) ∨
Ri−(XY) ∨
Rj+(XY): (4)
In the next theorem we view an NCQ query q as mapping an instance I to the instance q(I), where q(I) is a 4-instance over schema {Q}, with Q(a)q(I) = Q(a)I .
Theorem 2. Let q be an NCQ and I a 4-instance. Then q(I) ≐ (q↓2(I↓2))↑4: Similarly to the two-valued case, we can regard a 4-instance I as a naive table de ning the set XI = {J ∶ I t J and d om(J ) ⊆ Cons} of possible worlds. We can now extended the naive evaluation property to NCQs on 4-instances, by using the result (proved in the full version) that q(XI) ≐ q(I). In analogue with (1) we de ne the certain answer as C ert4(q; X ) = ( {q(I) ∶ I ∈ X })↾ : To wrap this section up formally, we conclude Corollary 1. Let q be an NCQ and I a 4-instance. Then C ert4(q; XI) = (q↓2(I↓2)↑4↾ :
Note that all the previous results hold as well for the larger class NUCQ of unions of conjunctive queries with negation. We have only presented the transformation of NCQs q into UCQs q↓2. In a very similar fashion we can transform any NUCQ query into a UCQ, while preserving all theorems of this section, and in particular Corollary 1. 5
Data Exchange in T WO and FOUR
A tuple generating dependency (TGD) is a rst order formula having the form
∀XY( (XY) → ∃Z R(XZ)): An equality generating dependency (EGD) is a
rst order formula of the form ∀X( (X) → X1 = X2); where X1 and X2 are
variables in X. A TGD with negation and unequality (NTGD≈~ ) is a TDG that
can have atomic negations in the body and in the head, and that also includes
a special equality symbol ≈, possibly negated (denoted ≈~). Note that NTGD≈s
include the EGDs. Also, the notion of a 4-instance has to be extended to account
for the explicit equality. Details appear in the full paper [
De nition 6. Let I be a 2-instance (a 4-instance) and a set of TGDs and EGDs (a set of NTGD≈s). A 2-universal model (a 4-universal model) of (I; ) is a 2-instance J (a 4-instance J ), such that 1. I ≤ J (I t J ), 2. J ⊧2 (J ⊧4 ), and 3. for all instances K, if I ≤ K and K ⊧2 (if I t K and K ⊧4 , then J ≤ K , then J t K).
Let I be a 2-instance and a set of dependencies. The de nition of the
procedure C hase(I; ) can be found in [
Data Exchange. A data exchange schema is a schema of the form S ∪ T, where S ∩ T = ∅. The schema S is called the source schema, and T is called the target schema. Let S∪T be a data exchange schema. A source-to-target TGD (st-TGD) is a TGD where the relation symbols in the body come from S and the relation symbols in the head come from T. Source-to-target NTGD≈s (s-t NTGD≈s) are de ned similarly. A target EGD (t-EGD) is an EGD where all relation symbols come from T. A data exchange setting is a pair (S ∪ T; ), where S ∪ T is a data exchange schema, and is a set of s-t TGDs (or s-t NTGD≈s) and t-EGDs.
A 2-instance of a data exchange setting is a pair (I; ), such that nulls(I) = ∅, R(a)I = 0, for all R ∈ T and a ∈ d om(I)ar(R), and = st ∪ t, where st is a set of s-t TGDs and t is a set of t-EGDs.
A 4-instance of a data exchange setting is like a 2-instance, except that st can contain NTGD≈'s, and that R(a)I = , for all R ∈ T and a ∈ d om(I)ar(R).
Let n ∈ {2; 4} and ≼ ∈ {≤; t}. An n-solution for an n-instance (I; ) of a data exchange setting (S ∪ T; ), is an n-instance J , such that I ≼ J , J ⊧n , and J ↾S= I↾S. The notation J ↾S stands for the instance J restricted to the relation symbols in S, and similarly for I↾S. The set of all n-solutions to an n-instance I in setting (S ∪ T; ) is denoted S oln(I; ). A n-solution J ∈ S oln(I; ) is said to be an n-universal solution if J ≼ K, for all K ∈ S oln(I; ).
Let I be a 2 instance of a data exchange setting (S ∪ T; ), and let q =
∃Y (XY) be a target UCQ, i.e. such that all relation symbols in come from T.
Then the certain answer [
C ert2(q; I; ) = {q(J ) ∶ J ∈ S ol2(I; )}↾ : In other words, C ert2(q; I; ) is the greatest lower bound in the partial order ≤ of the set {q(J ) ∶ J ∈ S ol2(I; )}, restricted to the constants. The following result is at the foundation of data exchange.
Theorem 3. [
In the full paper [
Theorem 4. Let (S ∪ T; ) be a data exchange setting where st-NTGD≈s and t-EGDs, and let I be a 4-instance. Then consists of S ol4(I;
) = S ol2(I↓2; ↓2)↑4:
Armed with this result we now show that we can use the chase process de ned
in [
Theorem 5. Let (I; ) be a 4-instance of a data exchange setting, where consists of st-NTGD≈s and t-EGDs, Then (C hase(I↓2; ↓2))↑4 is a 4-universal solution for (I; ). Moreover, for every NUCQ query q we have C ert4(q; I;
) = (q↓2((C hase(I↓2; ↓2))))↾↑4 : 6
In the previous sections we have shown that for a given 4-instance I and a
set of NTGDs , (or NTGD≈~ s), the 4-universal solution is the best candidate
for target materialization in data exchange, and that as such it can be used to
e ciently compute certain answers to target UNCQ queries (or UNCQ≈ queries).
The question then arises whether a 4-universal solution exists. Since our results
include the lossless decomposition S ol4(I; ) = S ol2(I↓2; ↓2)↑4, the answer
follows directly from from [
The de nition of the core-chase procedure can be found in [
Theorem 7. The core chase procedure is complete for nding 4-universal solutions for 4-instances I and NTGD≈s
One of the important classes for which universal solutions are guaranteed
to exist, is the guarded dependencies of [
In the literature one can nd many classes of TGDs that are known to
ensure uniform chase termination, and thus guaranteeing the existence of universal
solutions for all instances (for an overview, see e.g. [
We note that most of the known classes guaranteeing uniform termination have a tractable membership problem. 7
In this paper we have put forth a new approach to Data Exchange based on
Belnap's logic FOUR. We showed that moving to a four-valued logic comes with
the bene t of naturally extending the mapping language to NTGD≈s and the
query language to NUCQ≈s, thus allowing negation over atoms, including
equality atoms a ≈ b. We also showed that well-known techniques from Data exchange
(chase, universal solution, naive evaluation, etc) can be used in FOUR as well.
Furthermore, the core of a 4-instance I (minimal instance in size that is ≃
equivalent with I) is the same as core(I↓2)↑4. Thus the core chase [
There is still more work to be done as we haven't touched on for instance meta-data management problems, such as composition and inverse. Another aspect that needs to be further investigated is the chase termination problem in T WO for a set of TGDs corresponding to a set of NTGD≈s in FOUR. Note that the set of TGDs in this case is special in the sense that it always contain the set of full TGDs expressed by .
We believe that ⊧4 is a semantics with natural appeal, and one that can be practically implemented over existing DBMSs.