JournalofArtificialIntelligence Research21(2004) 245–286 Submitted07/2003; published03/2004 Coherent Integration of Databases by Abductive Logic Programming Ofer Arieli [email protected] Department of Computer Science, The Academic College of Tel-Aviv, 4 Antokolski street, Tel-Aviv 61161, Israel. Marc Denecker [email protected] Bert Van Nuffelen [email protected] Maurice Bruynooghe [email protected] Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A, B-3001 Heverlee, Belgium. Abstract We introduce an abductive method for a coherent integration of independent data- sources. The idea is to compute a list of data-facts that should be inserted to the amal- gamated database or retracted from it in order to restore its consistency. This method is implemented by an abductive solver, called Asystem, that applies SLDNFA-resolution on a meta-theory that relates different, possibly contradicting, input databases. We also give a pure model-theoretic analysis of the possible ways to ‘recover’ consistent data from an inconsistent database in terms of those models of the database that exhibit as minimal inconsistent information as reasonably possible. This allows us to characterize the ‘recov- ereddatabases’intermsofthe ‘preferred’(i.e., mostconsistent)models ofthe theory. The outcome is an abductive-based application that is sound and complete with respect to a correspondingmodel-based,preferentialsemantics,and – to the best ofour knowledge– is moreexpressive(thusmoregeneral)thananyotherimplementationofcoherentintegration of databases. 1. Introduction Complex reasoning tasks often have to integrate information that is coming from different sources. Oneofthemajorchallengeswiththisrespectistocomposecontradictingsourcesof information such that what is obtained would properly reflect the combination of the data- sources on one hand1, and would still be coherent (in terms of consistency) on the other hand. There are a number of different issues involved in this process, the most important of which are the following: 1. Unification of the differentontologies and/or database schemas, inorder to get a fixed (global) schema, and a translation of the integrity constraints2 of each database to the new ontology. 2. Unification of translated integrity constraints in a single global set of integrity con- straints. Thismeans,inparticular,eliminationofcontradictionsamongthetranslated 1. This property is sometimes called compositionality (Verbaeten,Denecker,& DeSchreye,1997, 2000). 2. I.e., therules that represent intentional truthsof a database domain. (cid:13)c2004AIAccessFoundation. Allrightsreserved. Arieli, Denecker, Van Nuffelen, & Bruynooghe integrity constraints, and inclusion of any global integrity constraint that is imposed on the integration process. 3. Integration of databases w.r.t. the unified set of integrity constraints, computed ac- cording to the previous item. Each one of the issues mentioned above has its own difficulties and challenges. For instance, the first issue is considered, e.g., by Ullman (2000) and Lenzerini (2001, 2002), where questions such as how to express the relations between the ‘global database schema’ and the source (local) schemas, and how this influences query processing with respect to the global schema (Bertossi, Chomicki, Cort´es, & Gutierrez, 2002), are dealt with3. The second issue above is concerned with the construction of a single, classically con- sistent, set of integrity constraints, applied on the integrated data. In database context, it is common to assume that such a set is pre-defined, and consists of global integrity con- straints that are imposed on the integration process itself (Bertossi et al., 2002; Lenzerini, 2002). In such case there is no need to derive these constraints from the local databases. When different integrity constraints are specified in different local databases, it is required to integrate not only the database instances (as specified in issue 3 above), but also the integrity constraints themselves (issue2). Thereason for separating these two topics is that integrity constraints representtruths that should bevalid in all situations, while a database instance exhibits an extensional truth, i.e., an actual situation. Consequently, the policy of resolving contradictions among integrity constraints is often different than the one that is applied on database facts, and often the former is applied before the latter. Despite their different nature, both issues are based on some formalisms that main- tain contradictions and allow to draw plausible conclusions from inconsistent situations. Roughly, there are two approaches to handle this problem: • Paraconsistent formalisms, in which the amalgamated data may remain inconsistent, but the set of conclusions implied by it is not explosive, i.e.: not every fact follows from an inconsistent database, and so the inference process does not become trivial in the presence of contradictions. Paraconsistent procedures for integrating data, like those of Subrahmanian (1994) and de Amo, Carnielli, and Marcos (2002), are often based on a paraconsistent reasoning systems, such as LFI (Carnielli & Marcos, 2001), annotated logics (Subrahmanian, 1990; Kifer & Lozinskii, 1992; Arenas, Bertossi, & Kifer, 2000), or other non-classical proof procedures (Priest, 1991; Arieli & Avron, 1996; Avron, 2002; Carnielli & Marcos, 2002)4. • Coherent (consistency-based) methods, in which the amalgamated data is revised in order to restore consistency (see, e.g., Baral, Kraus, & Minker, 1991; Baral, Kraus, Minker, & Subrahmanain, 1992; Benferhat, Dubois, & Prade, 1995; Arenas, Bertossi, 3. For surveyson schema matching and related aspects, see also (Batini, Lenzerini, & Navathe,1986) and (Rahm & Bernstein, 2001). 4. See also (Decker, 2003) for a historical perspective and some computational remarks on this kind of formalisms. 246 Coherent integration of databases by abductive logic programming & Chomicki, 1999; Arieli & Avron, 1999; Greco & Zumpano, 2000; Liberatore & Schaerf,2000; Bertossi&Schwind,2002;Arieli,Denecker,VanNuffelen,&Bruynooghe, 2004). In many cases the underlying formalisms of these approaches are closely re- lated to the theory of belief revision (Alchourr´on, Ga¨rdenfors, & Makinson, 1995; Ga¨rdenfors & Rott, 1995). In the context of database systems the idea is to consider consistent databases that are ‘as close as possible’ to the original database. These‘re- paired’ instances of the ‘spoiled’ database correspond to plausible and compact ways of restoring consistency. Inthispaperwefollowthelatterapproach,andconsiderabductiveapproachesthathan- dle the third issue above, namely: coherent methods for integrating different data-sources (with the same ontology) w.r.t. a consistent set of integrity constraints5. The main diffi- culty in this process stems from the fact that even when each local database is consistent, the collective information of all the data-sources may not remain consistent anymore. In particular, facts that are specified in a particular database may violate some integrity con- straints defined elsewhere, and so this data might contradict some elements in the unified set of integrity constraints. Moreover, as noted e.g. in (Lenzerini, 2001; Cali, Calvanese, De Giacomo, & Lenzerini, 2002), the ability to handle, in a plausible way, incomplete and inconsistent data, is an inherent property of any system for data integration with integrity constrains, nomatter which integration phaseis considered. Providingproperways of gain- ing this property is a major concern here as well. Our goal is therefore to find ways to properly ‘repair’ a combined (unified) database, and restore its consistency. For this, we consider a pure declarative representation of the composition of distributed data by a meta-theory, relating a number of different input databases (that may contradict each other) with a consistent output database. The un- derlying language of the theory is that of abductive logic programming (Kakas, Kowalski, & Toni, 1992; Denecker & Kakas, 2000). For reasoning with such theories we use an ab- ductive system, called Asystem (Kakas, Van Nuffelen, & Denecker, 2001; Van Nuffelen & Kakas, 2001), which is an abductive solver implementing SLDNFA-resolution (Denecker & De Schreye, 1992, 1998). The composing system is implemented by abductive reasoning on the meta-theory. In the context of this work, we have extended this system with an optimizing component that allows us to compute preferred coherent ways to restore the consistency of agiven database. Thesystem that is obtained induces an operational seman- tics for database integration. In the sequel we also consider some model-theoretic aspects of the problem, and define a preferential semantics (Shoham, 1988) for it. According to this semantics, the repaired databases are characterized in terms of the preferred models (i.e., the most-consistent valuations) of the underlying theory. We relate these approaches by showing that the Asystem is sound and complete w.r.t. the model-based semantics. It is also noted that ourframework supportsreasoning with various types of specialinformation, such as timestamps and source identification. Some implementation issues and experimen- 5. In this sense, one may view this work as a method for restoring the consistency of a single inconsistent database. We prefer, however, to treat it as an integration process of multiple sources, since it also has somemediatingcapabilities,suchassourceidentification,makingprioritiesamongdifferentdata-sources, etc. (see, e.g., Section 4.6). 247 Arieli, Denecker, Van Nuffelen, & Bruynooghe tal results are discussed as well. The rest of this paper is organized as follows: in the next section we formally define our goal, namely: a coherent way to integrate different data-sources. In Section 3 we set up a semantics for this goal in terms of a corresponding model theory. Then, in Section 4 we introduce our abductive-based application for database integration. This is the main section of this paper, in which we also describe how a given integration problem can be represented in terms of meta logic programs, show how to reason with these programs by abductive computational models, present some experimental results, consider proper ways of reasoning with several types of special data, and show that our application is sound and complete with respect to the model-based semantics, considered in Section 3. Section 5 contains an overview of some related works, and in Section 6 we conclude with some further remarks, open issues, and future work6. 2. Coherent Integration of Databases We begin with a formal definition of our goal. In this paper we assume that we have a first-order language L, based on a fixed database schema S, and a fixed domain D. Every element of D has a unique name. A database instance D consists of atoms in the language L that are instances of the schema S. As such, every instance D has a finite active domain, which is a subset of D. Definition 1 A database is a pair (D, IC), where D is a database instance, and IC, the set of integrity constraints, is a finite and classically consistent set of formulae in L. Given a database DB =(D, IC), we apply to it the closed word assumption, so only the facts that are explicitly mentioned in D are considered true. The underlying semantics corresponds, therefore, to minimal Herbrand interpretations. Definition 2 The minimal Herbrand model HD of a database instance D is the model of D that assigns true to all the ground instances of atomic formulae in D, and false to all the other atoms. There are different views on a database. One view is that it is a logic theory consisting of atoms and, implicitly, the closed world assumption (CWA) that indicates that all atoms not in the database are false. Another common view of a database is that it is a structure that consists of a certain domain and corresponding relations, representing the state of the world. Whenever there is a complete knowledge and all true atoms are represented in the database, both views coincide: the unique Herbrand model of the theory is the intended structure. However, in the context of independent data-sources, the assumption that each local database represents the state of the world is obviously false. However, we can still view a local database as an incomplete theory, and sotreating a database as a theory rather than as a structure is more appropriate in our case. 6. This is a combined and extended version of (Arieli, Van Nuffelen, Denecker, & Bruynooghe, 2001) and (Arieli, Denecker,Van Nuffelen,& Bruynooghe, 2002). 248 Coherent integration of databases by abductive logic programming Definition 3 A formula ψ follows from a database instance D (alternatively, D entails ψ; notation: D |= ψ) if the minimal Herbrand model of D is also a model of ψ. Definition 4 A database DB=(D, IC) is consistent if every formula in IC follows from D (notation: D |= IC). Our goal is to integrate n consistent local databases, DB =(D , IC ) (i=1,...n) to one i i i consistent database that contains as much information as possiblefromthe local databases. The idea, therefore, is to consider the union of the distributed data, and then to restore its consistency in such a way that as much information as possible will be preserved. Notation 1 Let DB = (D , IC ), i = 1,...n, and let I(IC ,...,IC ) be a classically i i i 1 n consistent set of integrity constraints. We denote: n UDB = ( D , I(IC ,...,IC )). i 1 n i=1 [ Inthenotation above, I is an operator thatcombines theintegrity constraints andelim- inates contradictions (see, e.g., Alferes, Leite, Pereira, & Quaresma, 2000; Alferes, Pereira, Przymusinska, & Przymusinski, 2002). As we have already noted, how to choose this oper- ator and how to apply it on a specific database is beyond the scope of this paper. In cases that the union of all the integrity constraints is classically consistent, it makes sense to take I as the union operator. Global consistency of the integrity constraints is indeed a common assumption in the database literature (Arenas et al., 1999; Greco & Zumpano, 2000; Greco, Greco, & Zumpano, 2001; Bertossi et al., 2002; Konieczny & Pino P´erez, 2002; Lenzerini, 2002), but for the discussion here it is possible to take, instead of the union, any operator I for consistency restoration. A key notion in database integration is the following: Definition 5 A repair of a database DB=(D, IC) is a pair (Insert,Retract), such that: 1. Insert∩D=∅, 2. Retract ⊆ D7, 3. (D∪Insert\Retract, IC) is a consistent database. Intuitively, Insert is a set of elements that should be inserted into D and Retract is a set of elements that should be removed from D in order to have a consistent database. As noted above, repair of a given database is a key notion in many formalisms for data integration. In the context of database systems, this notion was first introduced by Arenas, Bertossi, and Chomicki (1999), and later considered by many others (e.g., Greco & Zumpano, 2000; Liberatore & Schaerf, 2000; Franconi, Palma, Leone, Perri, & Scarcello, 2001; Bertossi et al., 2002; Bertossi & Schwind, 2002; deAmo et al., 2002; Arenas, Bertossi, & Chomicki, 2003; Arieli et al., 2004). Earlier versions of repairs and inclusion-based consistency restoration may be traced back to Dalal (1988) and Winslett (1988). 7. Notethat byconditions (1) and (2) it follows that Insert∩Retract=∅. 249 Arieli, Denecker, Van Nuffelen, & Bruynooghe Definition 6 A repaired database of DB =(D, IC) is a consistent database of the form (D∪Insert\Retract, IC), where (Insert,Retract) is a repair of DB. As there may be many ways to repair an inconsistent database8, it is often convenient to make preferences among the possible repairs, and consider only the most preferred ones. Below are two common preference criteria for preferring a repair (Insert,Retract) over a repair (Insert′,Retract′): Definition 7 Let (Insert,Retract) and (Insert′,Retract′) be two repairs of a given database. • set inclusion preference criterion : (Insert′,Retract′) ≤ (Insert,Retract), if i Insert ⊆ Insert′ and Retract ⊆ Retract′. • minimal cardinality preference criterion: (Insert′,Retract′) ≤ (Insert,Retract), if c |Insert|+|Retract| ≤ |Insert′|+|Retract′|. Setinclusionisalsoconsideredin(Arenasetal., 1999; Greco&Zumpano,2000; Bertossi et al., 2002; Bertossi & Schwind, 2002; deAmoet al., 2002; Arenas et al., 2003; Arieli et al., 2004, and others), minimal cardinality is considered, e.g., in (Dalal, 1988; Liberatore & Schaerf, 2000; Arenas et al., 2003; Arieli et al., 2004). In what follows we assume that the preference relation ≤ is a fixed pre-order that represents some preference criterion on the set of repairs (and we shall omit subscript notations in it whenever possible). We shall also assume that if (∅,∅) is a valid repair, it is the ≤-least (i.e., the ‘best’) one. This corresponds to the intuition that a database should not be repaired unless it is inconsistent. Definition 8 A ≤-preferred repair of DB is a repair (Insert,Retract) of DB, s.t. for every repair (Insert′,Retract′) of DB, if (Insert,Retract)≤(Insert′,Retract′) then (Insert′,Retract′)≤ (Insert,Retract). The set of all the ≤-preferred repairs of DB is denoted by !(DB,≤). Definition 9 A ≤-repaired database of DB is a repaired database of DB, constructed from a ≤-preferred repair of DB. The set of all the ≤-repaired databases is denoted by: R(DB,≤)= {(D∪Insert\Retract, IC) | (Insert,Retract) ∈ !(DB,≤)}. Note that if DB is consistent and ≤ is a preference relation, then DB is the only ≤- repaired database of itself (thus, there is nothing to repair in this case, as expected). Note 1 It is usual to refer to the ≤-preferred databases of DB as the consistent databases that are ‘as close as possible’ to DB itself (see, e.g., Arenas, Bertossi, & Chomicki, 1999; Liberatore & Schaerf, 2000; de Amo, Carnielli, & Marcos, 2002; Konieczny & Pino P´erez, 2002; Arenas, Bertossi, & Chomicki, 2003; Arieli, Denecker, Van Nuffelen, & Bruynooghe, 2004). Indeed, let dist(D ,D )= (D \D )∪(D \D ). 1 2 1 2 2 1 8. Somerepairsmaybetrivialand/oruseless,though. Forinstance,onewaytoeliminatetheinconsistency in(D, IC)=({p,q,r},{¬p})isbydeletingeveryelementinD,butthisiscertainlynottheoptimalway of restoring consistency in this case. 250 Coherent integration of databases by abductive logic programming It is easy to see that DB′ = (D′,IC) is a ≤ -repaired database of DB = (D, IC), if the set i dist(D′,D) is minimal (w.r.t. set inclusion) among all the sets of the form dist(D′′,D), where D′′ |= IC. Similarly, if |S| denotes the size of S, then DB′ = (D′,IC) is a ≤ -repaired c database of DB = (D, IC), if |dist(D′,D)| = min{|dist(D′′,D)| | D′′ |= IC}. Given n databases and a preference criterion ≤, our goal is therefore to compute the set R(UDB,≤) of the ≤-repaired databases of the unified database, UDB (Notation 1). The reasoner may use different strategies to determine the consequences of this set. Among the common approaches are the skeptical (conservative) one, that it is based on a ‘consensus’ among all the elements of R(UDB,≤) (see Arenas et al., 1999; Greco & Zumpano, 2000), a ‘credulous’ approach, in which entailments are determined by any element in R(UDB,≤), an approach that is based on a ‘majority vote’ (Lin & Mendelzon, 1998; Konieczny & Pino P´erez, 2002), etc. In cases where processing time is a major consideration, one may want to speed-up the computations by considering any repaired database. In such cases it is sufficient to find an arbitrary element in the set R(UDB,≤). Below are some examples9 of the integration process10. Example 1 Consider a relation teaches of the schema (course name,teacher name), and an integrity constraint, stating that the same course cannot be taught by two different teachers: IC = {∀X∀Y∀Z(teaches(X,Y)∧teaches(X,Z) → Y = Z)}. Consider now the following two databases: DB = ({teaches(c ,n ), teaches(c ,n )}, IC), 1 1 1 2 2 DB = ({teaches(c ,n )}, IC). 2 2 3 Clearly, the unified database DB ∪DB is inconsistent. It has two preferred repairs, which 1 2 are (∅, {teaches(c ,n )}) and (∅, {teaches(c ,n )}). Thecorrespondingrepaired databases 2 3 2 2 are the following: R = ({teaches(c ,n ), teaches(c ,n )}, IC), 1 1 1 2 2 R = ({teaches(c ,n ), teaches(c ,n )}, IC). 2 1 1 2 3 Thus, e.g., teaches(c ,n ) is true both in the conservative approach and the credulous 1 1 approach to database integration, while the conclusion teaches(c ,n ) is supported only by 2 2 credulous reasoning. Example 2 Consider databases with relations class and supply, of schemas (item,type) and (supplier,department,item), respectively. Let DB = ({supply(c ,d ,i ), class(i ,t )}, IC), 1 1 1 1 1 1 DB = ({supply(c ,d ,i ), class(i ,t )}, ∅), 2 2 2 2 2 1 whereIC = {∀X∀Y∀Z(supply(X,Y,Z)∧class(Z,t ) → X = c )}statesthatonlysupplier 1 1 9. See,e.g.,(Arenasetal.,1999;Greco&Zumpano,2000;Bertossi&Schwind,2002)forfurtherdiscussions on these examples. 10. In all the following examples we use set inclusion as the preference criterion, and take the operator I that combines integrity constraints (see Notation 1) to bethe union operator. 251 Arieli, Denecker, Van Nuffelen, & Bruynooghe c can supply items of type t . Again, DB ∪DB is inconsistent, and has two preferred 1 1 1 2 repairs: (∅, {supply(c ,d ,i )})and(∅, {class(i ,t )}). Itfollows thattherearetworepairs 2 2 2 2 1 of this database: R = ({supply(c ,d ,i ), class(i ,t ), class(i ,t )}, IC), 1 1 1 1 1 1 2 1 R = ({supply(c ,d ,i ), supply(c ,d ,i ), class(i ,t )}, IC). 2 1 1 1 2 2 2 1 1 Example 3 Let D ={p(a), p(b)},D ={q(a), q(c)}, and IC={∀X(p(X)→q(X))}. Again, 1 2 (D ,∅)∪(D ,IC) is inconsistent. The corresponding preferred repairs are ({q(b)}, ∅) and 1 2 (∅, {p(b)}). Thus, the repaired databases are the following: R = ({p(a), p(b), q(a), q(b), q(c)}, IC), 1 R = ({p(a), q(a), q(c)}, IC). 2 In this case, then, both the ‘consensus approach’ and the ‘credulous approach’ allow to infer, e.g., that p(a) holds, while p(b) is supported only by credulous reasoning, and p(c) is not supported by either of these approaches. 3. Model-based Characterization of Repairs In this section we set up a semantics for describing repairs and preferred repairs in terms of a corresponding model theory. This will allow us, in particular, to give an alternative description of preferred repairs, this time in terms of a preferential semantics for database theory. As database semantics is usually defined in terms of two-valued (Herbrand) models (cf. Definition 2 and the discussion that proceeds it), it is natural to consider two-valued semantics first. We show that arbitrary repairs can be represented by two-valued models of the integrity constraints. When a database is inconsistent, then by definition, there is no two-valued interpretation which satisfies both its database instance and its integrity constraints. Astandardway tocopewith this typeof inconsistencies is to move to multiple- valued semantics for reasoning with inconsistent and incomplete information (see, e.g., Subrahmanian,1990, 1994; Messing, 1997; Arieli & Avron, 1999; Arenas, Bertossi, & Kifer, 2000; de Amo, Carnielli, & Marcos, 2002). What we will show below, is that repairs can be characterizedbythree-valuedmodelsofthewholedatabase,thatis,ofthedatabaseinstance and the integrity constraints. Finally, we concentrate on the most preferred repairs, and show that a certain subset of the three-valued models can be used for characterizing ≤- preferred repairs. Definition 10 Given a valuation ν and a truth value x. Denote: νx = {p | p is an atomic formula, and ν(p) = x}11. The following two propositions characterize repairs in terms of two-valued structures. Proposition 1 Let (D, IC) be a database and let M be a two-valued model of IC. Let Insert = Mt\D and Retract = D\Mt. Then (Insert,Retract) is a repair of (D, IC). 11. Note,in particular, that in terms of Definition 2, if ν=HD and x=t,we havethat νx =D. 252 Coherent integration of databases by abductive logic programming Proof: The definitions of Insert and Retract immediately imply that Insert ∩ D = ∅ and Retract ⊆ D. For the last condition in Definition 5, note that D ∪Insert\Retract = D ∪ (Mt\D)\(D\Mt)= Mt. ItfollowsthatM istheleastHerbrandmodelofD∪Insert\Retract and it is also a model of IC, therefore D∪Insert\Retract |= IC. ✷ Proposition 2 Let (Insert,Retract) be a repair of a database (D, IC). Then there is a two-valued model M of IC such that Insert = Mt\D and Retract = D\Mt. Proof: Consider a valuation M, defined for every atom p as follows: t if p ∈ D∪Insert\Retract, M(p) = ( f otherwise. By its definition, M is a minimal Herbrand model of D ∪ Insert \ Retract. Now, since (Insert,Retract) is a repair of (D, IC), we have that D ∪ Insert \ Retract |= IC, thus M is a (two-valued) model of IC. Moreover, since (Insert,Retract) is a repair, necessarily Insert∩D = ∅ and Retract ⊆ D, hence we have the following: • Mt\D = (D∪Insert\Retract)\D = Insert, • D\Mt = D\(D∪Insert\Retract)= Retract. ✷ When a database is inconsistent, it has no models that satisfy both its integrity con- straints and its database instance. Onecommon method to overcome such an inconsistency is tointroduceadditional truth-values thatintuitively representpartialknowledge, different amounts of beliefs, etc. (see, e.g., Priest, 1989, 1991; Subrahmanian, 1990; Fitting, 1991; Arieli, 1999; Arenas et al., 2000; Avron, 2002). Here we follow this guideline, and consider database integration in the context of a three-valued semantics. The benefit of this is that, as we show below, any database has some three-valued models, from which it is possible to pinpoint the inconsistent information, and accordingly construct repairs. Theunderlyingthree-valuedsemanticsconsideredhereisinducedbythealgebraicstruc- ture THREE, shown in the double-Hasse diagram of Figure 112. ≤ ✻k ⊤ ✉ (cid:0)❅ (cid:0) ❅ (cid:0) ❅ (cid:0) ❅ (cid:0) ❅ ✉(cid:0) ❅✉ f t ≤ ✲t Figure 1: The structure THREE Intuitively, the elements t and f in THREE correspond to the usual classical values true and false, while the third element, ⊤, represents inconsistent information (or belief). 12. Thisstructureisusedforreasoningwithinconsistencybyseveralotherthree-valuedformalisms, suchas LFI (Carnielli & Marcos, 2001, 2002) and LP (Priest, 1989, 1991). 253 Arieli, Denecker, Van Nuffelen, & Bruynooghe Viewed horizontally, THREE is acomplete lattice. Accordingtothisview, f istheminimal element, t is the maximal one, and ⊤ is an intermediate element. The corresponding or- der relation, ≤ , intuitively represents differences in the amount of truth that each element t exhibits. We denote the meet, join, and the order reversing operation on ≤ by ∧, ∨, and t ¬ (respectively). Viewed vertically, THREE is a semi-upper lattice. In this view, ⊤ is the maximal element and the two ‘classical values’ are incomparable. This partial order, denoted by ≤ , may be intuitively understood as representing differences in the amount k of knowledge (or information) that each element represents13. We denote by ⊕ the join operation on ≤ 14. k VarioussemanticnotionscanbedefinedonTHREE asnaturalgeneralizations ofsimilar classical ones: a valuation ν is a function that assigns a truth value in THREE to each atomic formula. Given a valuation ν, truth values x ∈{t,f,⊤}, and atomic formulae p , i i we shall sometimes write ν = {p :x } instead of ν(p ) = x (i=1,2...). Any valuation is i i i i extended to complex formulaein theobvious way. For instance, ν(¬ψ) = ¬ν(ψ), ν(ψ∧φ)= ν(ψ)∧ν(ψ), and so forth15. The set of the designated truth values in THREE (i.e., those elements in THREE that represent true assertions) consists of t and ⊤. A valuation ν satisfies a formula ψ iff ν(ψ) is designated. A valuation that assigns a designated value to every formula in a theory T is a (three-valued) model of T. Lemma 1 Let ν and µ be three-valued valuations s.t. for every atom p, ν(p)≥ µ(p). Then k for every formula ψ, ν(ψ)≥ µ(ψ). k Proof: By induction on the structure of ψ. ✷ We shall write ν≥ µ, if ν and µ are three-valued valuations, for which the condition of k Lemma 1 holds. Lemma 2 If ν≥ µ and µ is a model of some theory T, then ν is also a model of T. k Proof: For every formula ψ ∈ T, µ(ψ) is designated. Hence, by Lemma 1, for every formula ψ ∈ T ν(ψ) is also designated, and so ν is a model of T. ✷ Next we characterize the repairs of a database DB by its three-valued models: Proposition 3 Let (D, IC) be a database and let M be a two-valued model of IC. Consider the three-valued valuation N, defined for every atom p by N(p)=HD(p)⊕M(p), and let Insert = N⊤\D, Retract = N⊤∩D. Then: 1. N is a three-valued model of D∪IC, and 13. See (Belnap, 1977; Ginsberg, 1988; Fitting, 1991) for a more detailed discussion on these orders and theirintuitivemeaning. 14. Wefollow herethe notations of Fitting (1990, 1991). 15. As usual, we use here the same logical symbol to denote the connective that appear on the left-hand side of an equation, and the corresponding operator on THREE that appear on the right-hand side of thesame equation. 254