Paraconsistent Relational Model: A Quasi-Classic Logic Approach Badrinath Jayakumar and Rajshekar Sunderraman Department of Computer Science, Georgia State University, Georgia, USA {bjayakumar2, raj}@cs.gsu.edu Abstract However, such multi-valued logic does not support dis- junctive syllogism (Hunter 1998). For example, suppose The well-founded model for any general deductive a knowledge base contains {passed ∨ failed} about a stu- database computed using the paraconsistent relational model, based on four-valued logic, does not support in- dent. When new information about the student comes to the ference rules such as disjunctive syllogism. In order knowledge base {¬failed}, the four-valued logic gives two to support disjunctive syllogism, we utilize the gener- paraconsistent minimal models (Sakama and Inoue 1995) alization of the relational model to quasi-classic (QC) {{passed, ¬failed}, {failed, ¬failed}}. Hence, ¬failed is logic, whose inference power is much closer to classi- the only logical consequence of the two models. Whether cal logic. As the paraconsistent relational model is ca- the student has passed or not cannot be inferred with four- pable of representing incomplete and inconsistent data, valued logic. we propose an algorithm to find QC model for inconsis- It is very clear from the above example that this four- tent positive extended disjunctive deductive databases. valued logic does not behave as expected in such situa- To accomplish this, in addition to using existing gener- tions. In order to get accurate models, it is required to use a alized algebraic operators, we introduce two new oper- ators F OCU SC and F OCU SD . stronger form of four-valued logic for improving the ability of reasoning. Therefore, we use QC logic (Hunter 2000). In this paper, the algorithm to find the model for positive ex- 1 Introduction tended disjunctive deductive databases is proposed by using Most database systems that are currently in use are based on QC logic with the paraconsistent relational model. To avoid the relational model. This model defines the falsity of its at- getting into an infinite iteration, it is assumed that the pro- tributes based on the absence of information (closed world gram does not have recursions, and constraints are also not assumption). However, the model is not suitable for all ap- used. In the model construction, for any disjunctive clause, it plications. For example, if a database does not contain a per- is necessary to impose a link between each relation in union son’s allergy to a medicine, when a doctor queries the per- and its complementary of the relation in order to enable non- son’s allergy to the medicine, the database will then return trivial classical conclusions. false. To represent negative information in databases, we use The approach presented in this paper differs from the QC paraconsistent databases (Bagai and Sunderraman 1995). model (Zhang, Lin, and Ren 2009) in its algebraic nature. Bagai and Sunderraman developed a framework to represent In this paper, we construct an algebraic equation for every negative facts in relational databases, which is based on four- clause in which expressions of the equation containing carte- valued logic. The four-valued relation represents both posi- sian products operates with a set of tuples instead of one tive and negative information, and negative facts are derived tuple at a time. In other words, the expression that repre- from open world assumption. The authors (Bagai and Sun- sents disjunctive head operates on one tuple at a time. In derraman 1995) also developed an application for the para- addition to that, algrebraic expressions can be optimized by consistent relational model that finds the weak well-founded using various laws of equality. semantics of general deductive databases. For general de- The rest of the paper is organized as follows. In section ductive databases and disjunctive deductive databases, var- 2, we introduce the preliminaries to understand the paper; in ious paraconsistent semantics have been proposed (Bagai section 3, we define a paraconsistent disjunctive relational and Sunderraman 1996b; Subrahmanian 1990; Sunderraman model; in section 4, we provide the key idea to understand 1997), all based upon Belnap’s four-valued model (Belnap Jr the paper; in section 5, we explain the algorithm with an 1977). Even for logic programs, especially disjunctive example; in section 6, we state the conclusion and future logic programs, various paraconsistent semantics are pro- work for this paper. posed (Alcântara, Damásio, and Pereira 2004; Arieli 2002; Damásio and Pereira 1998; Alcântara, Damásio, and Pereira 2 Preliminaries 2002). All of which still come under Belnap’s four-valued Before we explain the details of actual contributions of this model. paper, we must briefly review positive extended disjunctive deductive databases and the paraconsistent relational model Paraconsistent relations move forward a step to complete (Bagai and Sunderraman 1996a; Zhang, Lin, and Ren 2009; the database. Unlike normal relations where we only re- Bagai and Sunderraman 1995) . tain information believed to be true of a particular predicate, Syntax. Given a first order language L, a disjunctive de- we also retain what is believed to be false of a particular ductive database P (Minker and Seipel 2002) consists of predicate in the paraconsistent relational model. Let a rela- logical inference rules of the form tion scheme Σ be a finite set of attribute names, where for any attribute name A ∈ Σ, dom(A) is a non-empty domain r (rule) = l0 ∨ · · · ∨ ln ← ln+1 . . . lm of values for A. A tuple on Σ is any map t : Σ → A∈Σ S l0 . . . ln is called head of the rule and ln+1 . . . lm is called dom(A), such that t(A)∈ dom(A) for each A ∈ Σ. Let τ (Σ) body of the rule. A rule is called fact if the rule has no body. denote the set of all tuples on Σ. An ordinary relation on A rule is called denial rule if the rule has only body and scheme Σ is thus any subset of τ (Σ). A paraconsistent re- no head. A rule is called definite clause or horn clause, if lation on a scheme Σ is a pair < R+ , R− > where R+ and the rule has only one literal in the head and has some literal R− are ordinary relations on Σ. Thus, R+ represents the set in the body. A rule is called positive disjunctive rule if the of tuples believed to be true of R, and R− represents the set rule has both body and head. Concretely, the rule r is called of tuples believed to be false. positive extended disjunctive rule, if l0 , . . . , ln , ln+1 , . . . , lm Algebraic Operators. Two types of algebraic operators are are either positive or negative (¬) literals. defined here: i)Set Theoretic Operators, and ii) Relational For the given syntax of a positive extended disjunctive Theoretic Operators. deductive database, we reproduce the fixed point semantics Set Theoretic Operators. Let R and S be two paraconsis- of P (Zhang, Lin, and Ren 2009). tent relations on scheme Σ. Fixed Point Semantics. Let P be a positive extended dis- Union. The union of R and S, denoted R∪S, ˙ is a para- junctive deductive S database and I be a set of interpretations, consistent relation on scheme Σ, given that then TP (I) = I∈I TP (I) ˙ − = R− ∩ S − ˙ + = R+ ∪ S + , (R∪S) (R∪S)  . ∅, if ln+1 , . . . , lm ⊆ I for some Complement. The complement of R, denoted −̇R, is a   ground constraint ← ln+1 . . . lm from P.      paraconsistent relation on scheme Σ, given that {J | for each ground rule  TP (I) =   ri : l0 ∨ · · · ∨ ln ← ln+1 . . . lm such that −̇R+ = R− , −̇R− = R+ {ln+1 . . . lm } ⊆ I, J = I ∪ ri J 0 where  S    ˙ Intersection. The intersection of R and S, denoted R∩S,   0 J ∈ Lits(f ocus(l0 ∨ · · · ∨ ln , I))}, otherwise. is a paraconsistent relation on scheme Σ, given that In the definition of TP (I), f ocus removes comple- mentary literals from disjunction (f ocus(l0 ∨ l1 , I) = (R∩S) ˙ − = R− ∪ S − ˙ + = R+ ∩ S + , (R∩S) l0 where I = {¬l1 }). If all disjuncts ( l0 . . . ln ) are available Difference. The difference of R and S, denoted R−̇S, is in I as complementary literals, then the disjunction of liter- a paraconsistent relation on scheme Σ, given that als becomes the conjunction of literals. Lits of conjunction gives a set of conjuncts. On the other hand, Lits of disjunc- tion is a collection of sets where every set in the collection (R−̇S)+ = R+ ∩ S − , (R−̇S)− = R− ∪ S + contains a disjunct. Example 1. Let {a, b, c} be a common domain for all at- The TP definition contains the constraint. We write it for tribute names, and let R and S be the following paraconsis- the sake of completeness, but our contribution in this paper tent relations on schemes {X} and {X} respectively: will not address the constraint. The following two propositions are vital for our result. R+ = {(a), (b)}, R− = {(c)} Proposition 1. For any positive extended disjunctive deduc- S + = {(c), (b)}, S − = {(a)} tive database P , TP is finite and TP ↑ n = TP ↑ ω where n is a successor ordinal and ω is a limit ordinal. ˙ is R∪S Proposition 2. For any positive extended disjunctive deduc- ˙ + = {(a), (b), (c)} (R∪S) tive database P , Minimal QC Model(P ) = min(µ(TP ↑ ω) 1 ) where min () stands for sets with a minimum number of ˙ − = {} (R∪S) literals. ˙ is R∩S As we stated earlier, we use the paraconsistent rela- tion model (Bagai and Sunderraman 1995) to find the QC ˙ + = {(b)} (R∩S) model for any given positive extended disjunctive deductive ˙ − = {(a), (c)} (R∩S) database. In the following, we define the paraconsistent re- −̇R is lational model and its operators. −̇R+ = {(c)} 1 µ(TP ↑ ω) = {I | I ∈ TP ↑ ω and I ∈ TP ({I})} −̇R− = {(a), (b)} R−̇S is In the rest of the paper, relations mean paraconsistent rela- tions. In order to find the QC model easily in our algorithm, (R−̇S)+ = {(a)} we create a copy for a given relation. For any given relation R, the copy of R is R0 . Both R and R0 are different relations (R−̇S)− = {(b), (c)} with the same attributes and the same tuples. R is called an Relation Theoretic Operators. Let Σ and ∆ be relation exact relation and R0 is called a copy relation. In addition schemes such that Σ ⊆ ∆, and R and S be paraconsistent to that, the replica of R is R, where replica R has the same relations on schemes Σ and ∆. name, the same tuples, and the same attributes. We assume ˙ Join. The join of R and S, denoted R./S, is a paracon- that a relation and its replica should not appear in the same sistent relation on scheme Σ ∪ ∆ given that set, but it can appear in different sets. If two relations (a re- lation and its replica) appear in the same set, then we merge the tuples and write it as one relation. ˙ − = (R− )Σ∪∆ ∪ (S − )Σ∪∆ ˙ + = R+ ./ S + , (R./S) (R./S) Our main contributions of the paper start from the dis- Projection. The projection of R onto ∆ , denoted π̇∆ (R), junctive relation. is a paraconsistent relation on ∆ given that 3 Disjunctive Relation π̇∆ (R)+ = π∆ (R+ )Σ∪∆ Let a disjunctive relation scheme 2Σ be a finite set of at- π̇∆ (R)− = {t ∈ τ (∆) | tΣ∪∆ ⊆ (R− )Σ∪∆ } tribute sets, where for any attribute set A ⊆ 2Σ , dom(a) where π∆ is the usual projection over ∆ of ordinary rela- is a non-empty domain of values for each a ∈ A. Let tions. τ (2Σ ) denote the set of all tuples on 2Σ . A disjunctive Selection. Let F be any logic formula involving attribute relation, DR, over the scheme 2Σ consists of two compo- names in Σ, constant symbols, and any of these symbols nents hDR+ , DR− i, where DR+ ⊆ τ (2Σ ) and DR− ⊆ {==, ¬, ∧, ∨}. Then the selection of R by F , denoted τ (2Σ ). DR+ is the component that consists of a set of tu- σ̇F (R)+ , is a paraconsistent relation on scheme Σ, given ples. While the tuples in DR+ typically represent the dis- that junction of facts, they also sometimes represent the conjunc- tion of facts. At the same time, DR− is the component that consists of a set of tuples. Each tuple in this component rep- σ̇F (R)+ = σF (R)+ , σ̇F (R)− = R− ∪ σ¬F (τ (Σ)) resents a conjunction of facts. In the case where the tuple is a singleton, both DR+ and DR− have a definite fact that where σF is a usual selection of tuples satisfying F from has neither disjunction or conjunction. ordinary relations. Let T be a tuple in DR, then for all t ∈ T , Att(t) be an The following example is taken from Bagai and Sunderra- attribute set that represents the element in the tuple of the man’s paraconsistent relational data model (Bagai and Sun- disjunctive relation DR, and let Att(R) be an attribute set derraman 1995). that represents the relation R over the scheme Σ. Example 2. Strictly speaking, relation schemes are sets of The disjunctive relational model is very much different attribute names. However, in this example we treat them from the disjunctive database introduced by Molinaro et al. as ordered sequence of attribute names, so tuples can be (Molinaro, Chomicki, and Marcinkowski 2009). The dis- viewed as the usual lists of values. Let {a, b, c} be a com- junctive database (Molinaro, Chomicki, and Marcinkowski mon domain for all attribute names, and let R and S be the 2009) is based on the relational model (not the paraconsis- following paraconsistent relations on schemes hX, Y i and tent relational model), whereas disjunctive relational model hY, Zi respectively: is based on the paraconsistent relational model. Moreover R+ = {(b, b), (b, c)}, R− = {(a, a), (a, b), (a, c)} unlike the disjunctive relational model, disjunctive databases S + = {(a, c), (c, a)}, S − = {(c, b)}. (Molinaro, Chomicki, and Marcinkowski 2009) are well- Then, R./S ˙ is the paraconsistent relation on scheme suited for repairs. At the same time, the disjunctive rela- hX, Y, Zi: tional model is also different from the relational model in- ˙ + = {(b, c, a)} (R./S) troduced by Sunderraman that can handle disjunction (Sun- ˙ − = {(a, a, a), (a, a, b), (a, a, c), (a, b, a), (a, b, b), (R./S) derraman 1997). In Sunderraman’s relation model for dis- (a, b, c), (a, c, a), (a, c, b), (a, c, c), (b, c, b), (c, c, b)} junction, all the disjuncts should have the same arity in the Now, π̇hX,Zi (R./S) ˙ becomes the paraconsistent relation relation. However, in the disjunctive relational model, it can be different. on scheme hX, Zi: ˙ + = {(b, a)} In the following, we define rename operators, mapping, π̇hX,Zi (R./S) and necessary functions, which all play a key role in con- ˙ − = {(a, a), (a, b), (a, c)} π̇hX,Zi (R./S) structing the QC model. In addition to that, we give an ex- Finally, σ̇¬X=Z (π̇hX,Zi (R./S)) ˙ becomes the paraconsis- ample that relates the usage of the operators, mapping and tent relation on scheme hX, Zi: the functions which help to comprehend the algorithm. + σ̇¬X=Z (π̇hX,Zi (R./S))˙ = {(b, a)} Rename Operators. Rename operators change the at- − σ̇¬X=Z (π̇hX,Zi (R./S))˙ = {(a, a), (a, b), (a, c)(b, b), tributes for any relation. We define two rename operators: (c, c)} i) Attribute Rename, and ii) Copy Attribute Rename. Attribute Rename (Θ). Let R be a relation over scheme Example 3. Let R1 , R2 and C are relations over schemes Σ and Σ = {A1 . . . Am , R.A1 . . . R.Am } , Then {X} , {Y, Z} and {X, Y, Z} and domain for every attribute is {a, b, c}. Then, we have the following equation: ΘA1 ...Am →R.A1 ...R.Am (R) (π̇{X,Y,Z} (R1 (X)∪˙ −̇R2 (Y, Z)))[X, Y, Z] = and (π̇{X,Y,Z} (C(X, Y, Z)))+ [X, Y, Z] where C + = {(a, b, c)}, R1− = {(b)} and R2+ = ΘR.A1 ...R.Am →A1 ...Am (R) {(a, c), (b, c)} This operator (Θ) is used to maintain uniqueness of at- Solution. Before the tuples of C are distributed to R1 and tributes between any two relations. R2 , it is imperative to note that R1 and R2 contain definite Copy Attribute Rename (Ω). Let R be a relation over tuples, which are not disjunctive (conjunctive). The first step scheme Σ and Σ = {A1 . . . Am , R10 .A1 . . . Rn0 .Am }. Then is to map the definite tuples of R1 and R2 to a disjunctive re- ΩA1 ...Am →R0 .A1 ...R0 .Am (R) lation. The definite tuples have no disjunction (conjunction) in any disjunctive relation. So,we rename the attributes (Θ) and of R1 and R2 . Then we map the definite tuples to DR. In the rest of the paper, we differentiate positive and neg- ΩR0 .A1 ...R0 .Am →A1 ...Am (R) ative parts of a relation (disjunctive relation) with a double Tuple Mapping to Disjunctive Relation. The algebraic line in every relation (disjunctive relation) diagram. equivalent for disjunction (∨) is union. So, we represent {R1 .X} {R2 .Y, R2 .Z} the disjunctive information in P as paraconsistent unions (b) ˙ of relations. But it is not very flexible to construct the (∪) DR = (a, c) QC model with paraconsistent unions (∪) ˙ of relations. So, (b, c) we map the information in relations to a disjunctive relation The next step is to distribute the tuples from C to each DR. Let R1 . . . Rn be relations over schemes Σ1 . . . Σn individual relation in any union after applying Θ to R1 and where every Σi ⊆ Σ and 1 ≤ i ≤ n. Then a set of R2 . It is necessary to apply Θ before the distribution of attribute sets for any DR obtained from R1 ∪˙ . . . ∪R ˙ n is tuples from C because we changed the attributes of R1 and {Σ1 . . . Σn }. Now, we map the tuples of relations contain- R2 before we map the definite tuples. ing paraconistent unions to a disjunctive relation. For each {Y, Z} t ∈ T , T is a tuple for any disjunctive relation (DR). Then {X} (b, c) t : Σ → ∪A∈Att(Ri ) dom(A) such that t(A) ∈ dom(A) for R1 = (a) and −̇R2 = every i in R1 ∪˙ . . . ∪˙ Rn where Att(t) = Att(Ri ). Infor- (a, c) (b) mally, a disjunctive relation can be considered a collection of (b, c) relations that has unions. It is intuitive to map each disjunc- The next step is to again rename (Θ) the attributes. tive relation back to its base relations because every t ∈ T {R2 .Y, R2 .Z} {R1 .X} of any disjunctive relation represents the corresponding tu- (b, c) R1 = (a) and −̇R2 = ple in the relation (Ri ). (a, c) In our approach, we need to find the name of the underly- (b) (b, c) ing relation for any given element in T . Hence, the following Then we map the newly added tuples of R1 ∪˙ −̇R2 to defintion: DR. NRelation. For any t ∈ T where T is a tuple for any dis- {R1 .X} {R2 .Y, R2 .Z} junctive relation (DR) that is mapped from R1 ∪˙ . . . ∪R ˙ n. (a) ∨ (b, c) N Relation(t):= {Ri | Att(t) = Att(Ri ) for any i in DR = (b) R1 ∪˙ . . . ∪R ˙ n} (a, c) N Relation returns the corresponding relation name (ei- ther positive or negative) for the given t where t ∈ T and (b, c) T ∈ DR. To find the relation name for any given element in As we stated earlier, the positive component of disjunc- the tuple T where T ∈ DR, we use N Relation. So, tive relations contains tuples that are typically disjunctive, N Relation((b, c)) is −̇R2 . but the positive component of disjunctive relations can be In addition to that, DISJ(DR) is (a) ∨ (b, c). conjunctive as well. As we are specifically handling the in- In the following section we introduce F OCU SC and consistencies associated with disjunction, we collect the tu- F OCU SD , which are very essential for handling inconsis- ples that are disjunctive. tencies. DISJ. Let DR be a disjunctive relation that is mapped from R1 ∪˙ . . . ∪R ˙ n . Then 4 Key Idea for QC logic It is very important to note that the paraconsistent relation + DISJ(DR) = {T | ∀T ∈ DR such that T is disjunctive } portrays a belief system rather than a knowledge system. The key idea of QC logic is given by the resolution rule of The following example is very specific, but helps to un- inference, which computes the focused belief. If the as- derstand the algorithm clearly. sumptions are considered as beliefs for the resolution, then the resolvent is called the focused belief. This ensures non- {R1 .X} {R2 .Y, R2 .Z} trivial reasoning in QC logic. As an individual can be both (a) true and false for a given relation in the relational model, DR = (b) we decouple the link during the model construction. This (a, c) is accomplished with the help of F OCU SD and F OCU SC . (b, c) Apply Θ(R20 ) , Θ(Ω(R1 )) andΘ(Ω(R2 )). These opera- F OCU SD . Let DR be a disjunctive relation on scheme 2Σ tions revert the relation back to its old attribute names. To and M R be a set of relations. Then reiterate, DR+ contains tuples which in turn can contain dis- F OCU SD (DR, M R) = {T | ∀T ∈ DISJ(DR) ∧ junction. From the base DR, multiple DR can be obtained ∃t ∈ T ∧ ∃R ∈ M R ∧ Att(R) = Att(N Relation(t)) ∧ by applying disjunction in tuples. Each newly created DR (N Relation(t) is positive ∧ t ∈ R− → (T = T \ t)) ∨ from the base DR should not lose any tuple set; otherwise, (N Relation(t) is negative ∧ t ∈ R+ → (T = T \ t))))} it leads to incorrect models. The following definition ad- As a special case, for a given tuple T where T ∈ DR+ , dresses the issue. if F OCU SD removes every element t in tuple T , then we Proper Disjunctive Relation (PDR). Let DR be a base convert the tuple T into a conjunction of the elements in disjunctive relation. A proper disjunctive relation is a set, the tuple. This is similar to f ocus that we defined in the which contains all disjunctive relations that can be formed Preliminaries section. from DR by applying disjunction in tuples. Concretely, CONJ. Let DR be a disjunctive relation that is mapped for every disjunctive relation (DRi ), which is obtained from from R1 ∪˙ . . . ∪R ˙ n . For any T ∈ DR, DR by applying disjunction, τ (DR+ ) = τ (DRi+ ) where 1 + CON J(T ):= { t1 ∧ · · · ∧ tn | ∀ti ∈ T ∧ n ≤ |T | } ≤ i ≤ (2n − 1)τ (DR ) such DRi is a P DRi . Using CONJ, we define F OCU SC . Example 5. Continuing from Example 4. F OCU SC . Let DR be a disjunctive relation on scheme 2Σ Solution. The next step is to create a set of proper disjunc- and M R be a set of relations. Then tive relation from DR. F OCU SC (DR, M R) = {CON J(T ) | ∀T ∈ P DR = {P DR1 } DR+ ∧ ∀t ∈ T ∧ ∃R ∈ M R ∧ Att(R) = {R1 .X} {R2 .Y, R2 .Z} Att(N Relation(t)) ∧ ((N Relation(t) is positive ∧ t ∈ R− ) ∨ (N Relation(t) is negative ∧ t ∈ R+ ))} (a) F OCU SD removes any element t , where t ∈ T and P DR1 = (b) T ∈ DR, that satisfies the predicate of F OCU SD . Simi- (a, c) larly, F OCU SC introduces conjunction among every t ∈ T (b, c) , where T ∈ DR, that satisfies the predicate of F OCU SC . The size of P DR is 1. Correspondingly, In any DR, any tuple T that contains conjunction should there should be one replica of base relations. never be affected by F OCU SD . {{(π̇{X,Y,Z} (R1 (R1 .X)∪˙ −̇R2 (R2 .Y, R2 .Z)))[X, Y, Z]}}. For every p in PDR, reverse map tuples to a set of base Example 4. Extending from Example 3. Let M R = {R20 } relations. where R20 + = {(a, c), (b, c)}. R20 is called a copy relation. {R1 .X} {R2 .Y, R2 .Z} R1 = (a) and −̇R2 = (a, c) Solution. (b) (b, c) M R = {R20 } where Finally, rename (Θ) each attribute name of every relation {Y, Z} back to its old name. Hence, R1 attribute is < X > and R2 0 R2 = (a, c) attribute is < Y, Z >. (b, c) To individualize the relation, we have the following defi- We know that, nition. {R1 .X} {R2 .Y, R2 .Z} Relationalize. Let R1 ∪˙ . . . ∪R ˙ n and R1 , . . . , Rn be rela- (a) ∨ (b, c) tions on scheme Σ. DR = (b) Relationalize(π̇{Σ} (R1 ∪˙ . . . ∪R ˙ n )[Σ]) : = (a, c) {R1 , . . . , Rn } (b, c) The relationalize operator removes the unions among re- lations and the projection for it. By doing so, the operator The attributes of R20 is different from R1 and produces a set of relations. If there is a select operation asso- R2 . Apply Θ(R20 ) , Ω(Θ(R1 )) and Ω(Θ(R1 )). So, ciated with the expression, then apply the operation before F OCU SC (F OCU SD ) can compare the attributes and per- Relationalize is applied. Relationalize is in accordance form necessary actions on T . to Lits, which is one of the key operators for finding the QC Now we apply focus to DR, model (Zhang, Lin, and Ren 2009). DR= F OCU SD (DR, M R) Example 6. Continuing from Example 5. In this case, in DR, the underlying relation for (b, c) is −̇R2 but (b, c) lies in the positive part of R20 in M R. There- Solution. Relationalize(π̇{Y,X} [R1 ∪˙ −̇R2 ](Y, X)) = {R1 , fore, F OCU SD removes it. R2 } where {X} {Y, Z} {Y, Z} 2. Let lˆi be the atom pi (Bi1 . . . Biki ), and Fi be the con- R1 = (a) and −̇R2 = (a, c) or R2 = (a, c) junction Ci1 ∧ · · · ∧ Ciki . If li is a positive literal, then (b) (b, c) (b, c) Qi is the expression π̇Vi σ̇Fi (lˆi )). Otherwise, let Qi be the Now R1 and R2 are called focused relations because R1 expression −̇π̇Vi (σ̇Fi (lˆi )). and R2 have no inconsistency. As a syntatic optimisation, if all conjuncts of Fi are true During QC model construction, we encounter a set of re- (i.e. all arguments of li are distinct variables), then both dundant relation sets. In order to remove it, we define the σ̇Fi and π̇Vi are reduced to identity operations, and are following. hence dropped from the expression. Minimize. Let {R11 . . . R1m } and {R21 . . . R2n } be two sets of relations where m ≤ n. 3. Let U be the union (∪) ˙ of the Qi ’s thus obtained, 0 M inimize({{R11 . . . R1n }, {R21 . . . R2m }}) : = ≤ i ≤ n. The output expression is (σ̇F1 (π̇DV (U ))) {{R11 . . . R1m } | R1i = R2j ∧ Att(R1i ) = Att(R2j ) ∧ [B01 . . . Bnk n ] where DV is the set of distinct variables τ (R1i ) = τ (R2j ) such that ∀i, 1 ≤ i ≤ m∧∃j, 1 ≤ j ≤ n} occurring in all li . By using the definitions and operators in Section 3 and 4. Let E be the natural join (./) ˙ of the Qi ’s thus obtained, Section 4, we propose an algorithm in the following section. n+1 ≤ i ≤ m . The output expression is (σ̇F1 (π̇DV (E))) [B01 . . . Bnk n ]. As in step 2, if all conjuncts are true, then 5 QC Model for Positive Extended σ̇F 1 is dropped from the output expression. Disjunctive Deductive Databases From the algebraic expression of the algorithm, we con- By using the algebra of the relational model, we present a struct a system of equations. bottom up method for constructing the QC model for the For any positive extended disjunctive deductive database positive extended disjunctive deductive database. The algo- P , EQN (P ) is a set of all equations of the form Ur = DUr , rithm that we present in this section is an extension of the where Ur is a union of the head predicate symbols of P , algorithm proposed by Bagai and Sunderraman (Bagai and and DUr is the union ∪˙ of all expressions obtained by the Sunderraman 1995). The reader is requested to refer to QC algorithm SERIALIZE for clauses in P with the same Ur in logic programs (Zhang, Lin, and Ren 2009) and QC logic their head. If all literals in the head are the same for any two (Hunter 2000). The QC model’s construction involves two rules, then Ur is the same for those two rules. steps. The first step is to convert P into a set of relation The final step is then to construct the model by incremen- definitions for the predicate symbols occuring in P . These tally constructing the relation values in P . For any posi- definitions are of the form tive extended disjunctive deductive database, PE are the non Ur = DUr disjunctive-facts (clauses in P without bodies), and PB are the disjunctive rules (clauses in P with bodies). PE∗ refers where Ur is the paraconsistent union of the disjunctive head to a set of all ground instances of clauses in PE . Then, PI = predicate symbols of P , and DUr is an algebraic expres- PE∗ ∪ PB . sion involving predicate symbols of P . Here r refers to The following algorithm finds the QC model for P . the equation number, 1 ≤ r ≤ N, where N refers to a total ALGORITHM. Model Construction number of equations. The second step is to iteratively evalu- Input. A positive extended disjunctive deductive database ate the expressions in these definitions to incrementally con- (P ) struct the relations associated with the predicate symbols. Output. Minimal QC Model for P . The first step is called SERALIZE and the second step is Method : The values are computed by the following steps. called Model Construction. Algorithm. SERALIZE 1. (Initialization) Input. A positive extended disjunctive deductive database (a) Compute EQN(PI ) using the algorithm SERIALIZE for clause l0 ∨ · · · ∨ ln ← ln+1 . . . lm . For any i, 0≤ i ≤ m, li is each clause in PI . either of the form pi (Ai1 . . . Aiki ) or ¬pi (Ai1 . . . Aiki ). Let (b) SModel= ∅ , For each predicate symbol p in PE , set Vi be the set of all variables occurring in li p+ = {{a1 . . . ak} | p(a1 . . . , ak) ∈ PE∗ }, and p− = ∅ or Output. An algebraic expression involving paraconsistent p− = {{a1 . . . ak} | ¬p(a1, . . . ak) ∈ PE∗ } and p+ = ∅ relations. Method. The expression is constructed by the following SModel=p steps : End for. 1. For each argument Aij of literal li , construct argument 2. (Rule Application) Bij and condition Cij as follows : (a) DModel= ∅. (a) If Aij is a constant a, then Bij is any brand new vari- For every SModel (SModel 6= ∅), create copies of the able and Cij is Bij =a. relations in SModel and replace the SModel with the (b) If Aij is a variable, such that for each k, 1≤ k < j, copies. Aik 6= Aij , then Bij is Aij and Cij is true. (b) For every equation r of the form Ur = DU r , create (c) If Aij is a variable, such that for some k, 1≤ k < j, DRr and insert the tuples from the copies in SModel Aik =Aij , then Bij is a brand new variable and Cij is into the corresponding exact relation in the equation r. Aij = Bij . Then map the definite tuples for the relations in Ur to DRr . Compute the expression DU r and set the rela- and w(X) ∨ g(X) ∨ ¬p(X) ← ¬f (X, Y ) is serialized to + tions in Ur with DU . ˙ (π̇{X} (w(X)∪g(X) ∪˙ −̇p(X))[X]= r (c) Map the newly added tuples of Ur to DRr . Apply Θ (π̇{X} (−̇f (X, Y )))+ [X] and Ω to every relation in Ur . Also apply Θ to every Both equations that are obtained after serialization have relation in SModel. Then the same left-hand side expression. So, it is written as one equation (as show in (1)). EQN(PI ) returns : DRr = F OCU SC (DRr , SM odel) ˙ 1. (π̇{X} (w(X)∪g(X) ∪˙ −̇p(X))[X]= ˙ (π̇{X} (r(X, Y )./s(Y )))+ [X]∪( ˙ π̇{X} (−̇f (X, Y )))+ [X] DRr = F OCU SD (DRr , SM odel) After step 1 (b) in initialization, SModel = {r, p, s, f } Repeat F OCU SD until there is no change in DRr . where When there is no change is DRr , apply Θ to every re- {X} {X, Y } {Y } {X, Y } lation in SModel and apply Ω and Θ to every relation r = (a, c) p = (a) s = (c) f = in Ur . (c) (a, b) (d) Create a set of proper disjunctive relations (P DRr ) After step 2(a), SModel = {r0 , p0 , s0 , f 0 } (COPIES) where from the focused DRr . {X} (e) Delete all tuples for the relations in Ur and create mul- {X, Y } {Y } r0 = (a, c) p0 = (a) s0 = (c) tiple replicas of Ur , which is denoted by the set Cr , (c) where |Cr | = |P DRr |. {X, Y } (f) Re-map each p in P DRr to C where C ∈ Cr . f0 = (a, b) For every C ∈ Cr , In step 2 (b), there is only one SModel and an equation. It C= Relationalize(C) is necessary to insert the tuples from the copies in SModel /* Cr contains a collection S of set of relations. */ to the corresponding relations in the equation. DModel= ∅. DModel = DModel Cr Then map the definite tuples to DR1 for the current SModel. /* Merging relations of every equation */ {w.X} {g.X} {p.X} (g) Once all equations are evaluated for the current DR1 = (a) SModel, perform the following: i) for every M ∈ (c) DModel and for every exact relation for SModel that Compute the equation and assign it to U1 . Map the newly is not in M , create the exact relation in M , and ii) for added (disjunctive) tuples to DR1 . every M ∈ DModel and for every exact relation for {w.X} {g.X} {p.X} SModel that is in M , insert the tuples from the copy (a) ∨ (a) ∨ (a) relation in SModel into the exact relation. Then add DR1 = DModel to TempModel. (a) (h) Once every SModel is applied, start from step 2 (a) (c) with SModel=M inimize (TempModel) and stop when By step 2 (c), DR1 = F OCU SD (DR1 , SM odel) there is no change in SModel. {w.X} {g.X} {p.X} (a) ∨ (a) 3. Minimal QC Model : Pick one (many) set (s) in SModel DR1 = whose sum of the size of all relations in the set (s) is (are) (a) minimal. (c) By step 2 (d), P DR1 = {P DR11 , P DR12 ,P DR13 } It is very intuitive from the algorithm that if the compu- {w.X} {g.X} {p.X} tation of DUr is empty for any SModel, then discard the (a) SModel. We found that the algorithm should be extended a P DR11 = little to accommodate disjunctive facts, duplicate variables (a) in disjunctive literals, and constants in disjunctive literals. (c) The following example shows how the algorithm works. {w.X} {g.X} {p.X} In the example, to show the difference between any two sets, (a) we superscript the set with a number. P DR12 = (a) Example 7. Let P be a positive extended disjunctive deduc- (c) tive database. It has the following facts and rules : {w.X} {g.X} {p.X} r(a, c), p(a), p(c), ¬f (a, b), s(c) (a) ∨ (a) w(X) ∨ g(X) ∨ ¬p(X) ← r(X, Y ), s(Y ) P DR13 = (a) w(X) ∨ g(X) ∨ ¬p(X) ← ¬f (X, Y ) (c) Solution. By step 1 (a) in initialization, Map every p in P DR1 back to a set of base relations. w(X) ∨ g(X) ∨ ¬p(X) ← r(X, Y ), s(Y ) is serialized to We skip a step (2 (d)) here. After relationalizing the set of ˙ (π̇{X} (w(X)∪g(X) ∪˙ −̇p(X))[X]= relations (step 2 (f)), we write: ˙ (π̇{X} (r(X, Y )./s(Y )))+ [X] C1 = {{ w, p }1 ,{g, p}2 ,{w, g, p }3 } { w, p }1 ¬f (a, b)}} {X} Gelfond and Lifschitz adopt the way of trivializing re- {X} w = (a) p = (a) sults (Gelfond and Lifschitz 1991) while the algorithm toler- (c) ates inconsistencies. However, we observe that we have not proven the CORRECTNESS of the algorithm. Our immedi- { g, p }2 ate future work is to prove that the algorithm mimics fixed {X} {X} point semantics (Proposition 1 and Proposition 2) (Zhang, g= (a) (a) p = Lin, and Ren 2009). (c) { w, g, p }3 6 Conclusion {X} {X} {X} In this paper, we proposed an algorithm to find the QC model w = (a) g = (a) p = (a) (c) for any positive extended disjunctive deductive database. S We also introduced the disjunctive relational model to rep- DModel= DModel C1 resent the relations containing paraconsistent unions. The By step 2 (g), algorithm that we presented here is based on the algorithm DModel = {{w, p, r, s, f }1 , {g, p, r, s, f }2 , that is used to compute the well-founded model for general 3 {w, g, p, r, s, f } } deductive databases by using the relational model (Bagai { w, p, r, s, f }1 and Sunderraman 1996a). In query-intensive applications, {X} this precomputation of the model enables efficient process- {X} {X, Y } {Y } w = (a) p = (a) r = (a, c) s = (c) ing of subsequent queries. Though we find the model for any (c) given positive extended disjunctive deductive database, the {X, Y } algorithm does not find models for the databases with recur- f= sions and constraints. One direction of future work could (a, b) be expanding the algorithm to allow recursions and con- { g, p, r, s, f }2 straints. Moreover, the model that we construct is too strong; {X} it causes disjunction introduction to fail, but it is supported {X} {X, Y } {Y } g = (a) r = (a) p = (a, c) s = (c) by QC logic. To compute the QC entailment, it is necessary (c) to have both weak and strong models. So another direc- {X, Y } tion of future work could be finding the weak models for the f= same program so that QC entailment could be achieved. The (a, b) creation of many proper disjunctive databases are expensive, { w, g, p, r, s, f }3 given the QC logic model computation, and are probably not {X} worth the extra computation. We notice that we have not {X} {X} {X, Y } w = (a) r = (a) g = (a) p = (a, c) stated or proven the complexities of the algorithm, and we (c) have also left it for future work. {Y } {X, Y } s= (c) f = (a, b) References Add DModel to TempModel. Alcântara, J.; Damásio, C. V.; and Pereira, L. M. 2002. By step 2 (h), SModel=M inimize (TempModel) Paraconsistent logic programs. In Logics in Artificial Intel- The algorithm stops when there is no change in SModel. ligence. Springer. 345–356. We then skip further iterations and write the final result: Minimal QC Model = { { w, p, r, s, f }1 , {g, p, r, s, f }2 } Alcântara, J.; Damásio, C. V.; and Pereira, L. M. 2004. { w, p, r, s, f }1 A declarative characterisation of disjunctive paraconsistent answer sets. In ECAI, volume 16, 951. Citeseer. {X} {X} {X, Y } {Y } Arieli, O. 2002. Paraconsistent declarative semantics for ex- w = (a) p = (a) r = (a, c) s = (c) (c) tended logic programs. Annals of Mathematics and Artificial Intelligence 36(4):381–417. {X, Y } f= Bagai, R., and Sunderraman, R. 1995. A paraconsistent (a, b) relational data model. International Journal of Computer { g, p, r, s, f }2 Mathematics 55(1-2):39–55. {X} {X} {X, Y } {Y } Bagai, R., and Sunderraman, R. 1996a. Bottom-up compu- g= (a) r = (a) p = (a, c) s = (c) tation of the fitting model for general deductive databases. (c) Journal of Intelligent Information Systems 6(1):59–75. {X, Y } Bagai, R., and Sunderraman, R. 1996b. Computing the well- f= (a, b) founded model of deductive databases. International Jour- In other words, Minimal QC Model = {{w(a), p(a), nal of Uncertainty, Fuzziness and Knowledge-Based Sys- p(c), r(a, c), s(c), ¬f (a, b)}, {g(a), p(a), p(c), r(a, c), s(c), tems 4(02):157–175. Belnap Jr, N. D. 1977. A useful four-valued logic. In Mod- ern uses of multiple-valued logic. Springer. 5–37. Damásio, C. V., and Pereira, L. M. 1998. A survey of para- consistent semantics for logic programs. In Reasoning with Actual and Potential Contradictions. Springer. 241–320. Gelfond, M., and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New generation computing 9(3-4):365–385. Hunter, A. 1998. Paraconsistent logics, handbook of defea- sible reasoning and uncertainty management systems: vol- ume 2: reasoning with actual and potential contradictions. Hunter, A. 2000. Reasoning with contradictory information using quasi-classical logic. Journal of Logic and Computa- tion 10(5):677–703. Minker, J., and Seipel, D. 2002. Disjunctive logic pro- gramming: A survey and assessment. In Computational Logic: Logic Programming and Beyond, Essays in Honour of Robert A. Kowalski, Part I, 472–511. Springer-Verlag. Molinaro, C.; Chomicki, J.; and Marcinkowski, J. 2009. Disjunctive databases for representing repairs. Annals of Mathematics and Artificial Intelligence 57(2):103–124. Sakama, C., and Inoue, K. 1995. Paraconsistent stable se- mantics for extended disjunctive programs. Journal of Logic and Computation 5(3):265–285. Subrahmanian, V. 1990. Paraconsistent disjunctive deduc- tive databases. In Multiple-Valued Logic, 1990., Proceed- ings of the Twentieth International Symposium on, 339–346. IEEE. Sunderraman, R. 1997. Modeling negative and disjunctive information in relational databases. In Database and Expert Systems Applications, 337–346. Springer. Zhang, Z.; Lin, Z.; and Ren, S. 2009. Quasi-classical model semantics for logic programs–a paraconsistent approach. In Foundations of Intelligent Systems. Springer. 181–190.