Project Topics
Get Complete Project Material File(s) Now! »
Logical Language: Existential Rules Framework
There are two major approaches to represent an ontology in the OBDA set-ting. The rst one is Description Logics such as EL (Baader et al., 2005) and DL-Lite, families (Calvanese et al., 2007). The second is rule-based languages such as Datalog (Cal et al., 2012), a generalization of Datalog (Ceri et al., 1989) that allows for existentially quanti ed variables in rule’s head. Despite Datalog undecidability when answering conjunctive queries, di erent decidable fragments are studied in the literature (see Baget et al. (2011a)). These fragments generalize the aforementioned Description Logics families and overcome their limitations by allowing any predicate arity as well as cyclic structures. Here we follow the second method for its expres-siveness. The main goal of this section is to introduce such logical language, which will serve as a base logic for the abstract argumentation framework.
The guidelines are as follows, in Subsection 3.2.1 we introduce the syn-tactical building blocks of the language and we show how querying facilities are available in such language. Next, to increase the expressiveness we ac-count in Subsection 3.2.2 for the ontological part where rules and negative constraints are taken into account. However, as the OBDA setting is highly prone to inconsistencies we present in Subsection 3.2.3 how inconsistency is dealt with in the literature.
LOGICAL LANGUAGE: EXISTENTIAL RULES FRAMEWORK
The language, facts and queries
We consider the positive existential syntactic fragment of rst-order logic DeFOL(nition9;^) (Chein and Mugnier (2009); Baget et al. (2011b)). Its language L is comp sed of some formulas built with the usual quanti ers (9; 8) and only the connectors, implication (!) and conjunction (^). A special-purpose constant that den tes the falsity ? is used. There is no disjunction and negat .
Consider a vocabulary composed of three dis-joint sets Voc = (C; P; V), where C is a nite set of constants, P is a nite set of predicates and V is an in nite set of variables. A function ar : P ! N associates a natural number ar(p) with each predicate p 2 P that de nes the arity of p.
A term t over Voc is a constant t 2 C or a variable t 2 V.
An atomic formula (or atom) over Voc is of the form p(t1; :::; tn) where p 2 P, ar(p) = n and t1; :::; tn are terms.
A ground atom is an atom with no variables.
A conjunction of atoms is called a conjunct. A conjunction of ground atoms is called a ground conjunct. By convention a ground atom is a ground conjunct. A variable in a formula is free if it is not in the scope of any quanti er. A formula is closed if it has no free variables (also known as sentence).
We denote by ~x(Atomsasequence of variables (x1; : : : ; xn).
Since we are in the setting of knowledge bases, constant symbols with di erent names represent i erent individuals (unique name assumption). This is safe to assume since our data often come from a relational database where constants that represent individuals are meant to be unique. It is to be noted that his logical language is negation-free. We use uppercase Example3lettersforconstan.2.1 andandconjuncts)lowercaseletters. for variables.
Consider the following vocabulary
C = fJohng, P = fstudent; teacher; teachesg and an in nite set of variables V = fx1; x2; x3; : : :g. Then, teaches(John; x1) is an atom, teacher(John) is a ground atom, teaches(John; x1) ^ teacher(John) is a conjunct and teacher(John) ^teaches(John; T om) ^student(T om) is a ground conjunct.
One way to represent knowledge about the world is to grasp factual knowledge. This kind of knowledge is deemed the most basic form of knowl-Deedge,nitionforinstance(Fact)the information \John teaches Tom » is basic or atomic. In logic programming and deductive databases this is called a fact, since represents a basic form of knowledge no wonder that classically ground atom are used to represent facts. To account for incomplete knowledge such as \John teaches s udent that we don’t know the name of », a fact is ex-tended so that it may contain existentially quanti ed variables and not only constants (e3.2g.2Baget et. al. (2011b)).
A fact on Voc is the existential closure of a con-junction of atoms over Voc.
So \John teaches a student that we don’t know the name of » is repre-sented as:
9×1(teacher(John) ^ student(x1) ^ teaches(John; x1)) where x1 is an existentially quanti ed variable. Note that we may omit quanti ers in facts as there is no ambiguity (they are all existentially quanti-ed). So the existential variables permit to represent unknown values which is an interesting property in this language. In addition, in the context of OBDA and Semantic Web we cannot assume that we can name all individ-Notationuals. 3.2.1.
Let F be a fact, we denote by terms(F ) (resp. vars(F )) the set of terms (resp. variables) that occur in F . We exclude duplicate atoms in facts, which allows to see a fact as a set of atoms. For instance, the fact F = 9x9y(r(x)^p(A; y) ^r(x)) can be seen as fp(A; y); r(x)g where vars(F ) = fx; yg and terms(F ) = fx; y; Ag. From now on we may use the set no ation and the logical notation interchangeably to denote a fact.
Arbitrary sets of ground facts F are in fact relational databases that store factual k owledge about a given domain. The reason to store knowledge is to be able answer queries about di erent aspects of such domain. In what follows we recall the notions of substitution and homomorphism between facts. Then we show how these two notions are used to evaluate queries eover nitionagiven3.2set.3 (SubstitutionoffactsF. and homomorphism).
Given a set of variables V and a set of terms T , a substitution of V by T (notation : V ! T ) is a mapping from V to T . Given a fact F , (F ) denotes the fact obtained from F by replacing each occurrence of x 2 V \ vars(F ) by (x). A homomorphism from a fact F to a fact F 0 is a substitution of vars(F ) by (a subset of terms(F 0) such that (F ) F 0.
Adding rules and negative constraints
Rules have been extensively used in knowledge-based and expert systems. Rules are logical formulas which allow us to infer facts from other facts. An example of a rule is: \If x is a cat then x is an animal ». In order to be general, rules often contain variables. To be even more general, rules should account for unknown individuals. For instance \ If x is a cat then x has a mother y and a father z ». These are called existential rules (Baget et al., 2011b; Cal et al., 2012) and the ability to represent unknown individuals is also known in database community as value invention (Abiteboul et al., 1995). This in fact captures the case where some information are incomplete and some individuals are unknown. In the above example, we still know that x has a mother but we fail to know who she is as the variable y is an existential one.
Overall, what we need to do when we have a set of facts supplied by a set of existential rules and negative constraints is to use these rules to de-duce all possible knowledge while respecting the negative constraints. The output of such procedure is a set of facts that extends the rst one. There- fore, query answering can be ea ily done over this new set of facts using homom rphisms.
In what follows we de ne the logical form of existential rules and nega-tive constraints. Then we explain how do we use rules to derive new facts using rule application. And nally we explain the saturation procedure that performsDe nition3abreadth.2.5(Existential-rstapplicationrules). of all rules on the set of facts.
Recall that we denote by ~x a sequence of variables. An existential rule (or simply a rule) is a closed formula of the form R = 8~y((8~xB) ! (9~zH)), where B and H are conjuncts with vars(B) = ~x [ ~y, and vars(H) = ~z [ ~y.
Table of contents :
1 Introduction
1.1 Knowledge Representation and Reasoning
1.2 Inconsistency Tolerance
1.3 Research Problem
1.3.1 Contribution 1: One-shot Argument-based Explanations
1.3.2 Contribution 2: Meta-level Dialectical Explanations
1.3.3 Contribution 3: Object-level Dialectical Explanations
1.4 Thesis Structure
2 Abstract Argumentation
2.1 Introduction
2.2 Abstract Argumentation Frameworks
2.3 Justication State
2.4 Coincidence between Semantics
2.5 Conclusion
3 Logic-based Argumentation
3.1 Introduction
3.2 Logical Language: Existential Rules Framework
3.2.1 The language, facts and queries
3.2.2 Adding rules and negative constraints
3.2.3 Consistent query answering
3.3 Instantiating Dung’s Abstract Framework
3.3.1 Arguments and attack
3.3.2 Outputs of logic-based argumentation
3.3.3 Characterizing the outputs
3.3.4 Properties
3.3.5 Postulates satisfaction
3.3.6 Relation with consistent query answering
3.4 Conclusion
4 Meta-level Dialectical Explanations
4.1 Introduction
4.2 Universal Acceptance Dialectical Proofs
4.3 Example
4.4 Properties
4.4.1 Finiteness, soundness and completeness
4.4.2 Dispute complexity
4.5 Eects of Meta-level Dialectical Explanations
4.5.1 Method
4.5.2 Results and analysis
4.5.3 Post-hoc analysis
4.6 Conclusion
5 Object-level Dialectical Explanations
5.1 Introduction
5.2 Motivating Example
5.3 Walton’s Dialogue Model of Explanation
5.4 The EDS Dialogue Model of Explanation
5.4.1 Protocol’s syntax
5.4.2 Protocol’s semantics
5.4.3 Commitment and understanding stores
5.4.4 Termination and success
5.4.5 The global picture
5.5 Argumentative Explanation Dialogues
5.6 Dialogue Example
5.7 Use-case: Object-level Dialectical Explanations
5.8 Conclusion
6 Application
6.1 Dur-Dur and the Durum Wheat Knowledge Base
6.1.1 The authoring
6.1.2 The structure
6.2 The DALEK Prototype: Explain!
6.2.1 Graphical user interface
6.2.2 Conguration structure
6.2.3 Stores
6.2.4 Dialogue manager
6.2.5 Semantics structure
6.2.6 Dialogue planner
6.2.7 Logical model
6.3 Conclusion
7 Conclusion and Perspectives
7.1 Conclusion
7.2 Future work
8 Appendix
8.1 Chapter 3
