Meghyn Bienvenu
email: meghyn@lirmm.fr

Michel Leclère
email: leclere@lirmm.fr

Marie-Laure Mugnier
email: mugnier@lirmm.fr

Marie-Christine Rousset
email: marie-christine.rousset@imag.fr

Reasoning with Ontologies

This chapter considers the notion of a formal ontology, which is a conceptual vocabulary equipped with a logical semantics. Three families of knowledge representation and reasoning formalisms that put ontologies at the core of any knowledge base are presented, namely: description logics, conceptual graphs and existential rules. We present the main knowledge constructs and dialects of these families, as well as the main reasoning problems with their complexity. We highlight the relationships between these families and compare them from an expressivity viewpoint.

Introduction

Knowledge-based systems exploit formal representations of knowledge to solve different kinds of problems. The fundamental formalism to represent and do reasoning on knowledge is classical first-order logic. Whereas a significant amount of work in knowledge representation aimed to extend classical logic to handle more complex notions (like time, modalities, preferences, ...), most work on ontologies was devoted to simpler logical fragments and to the study of tradeoffs between the ex-pressivity of the representation languages and the computational complexity of reasoning in these languages.

A commonly adopted definition of an ontology is that of an explicit specification of the conceptualisation of a domain [START_REF] Gruber | A translation approach to portable ontology specifications[END_REF]. All ontologies include at least a conceptual vocabulary, i.e., a set of terms (in the natural language sense) used to model a domain, provided with a specification of their meaning. These terms represent concepts (or classes), i.e., the categories of entities in the modeled domain, as well as relations (or properties, roles) which may stand between entities. Concepts and relations may be further specified in different ways, depending on the expressivity of the ontological language. They are usually organized into a specialisation/generalisation hierarchy by means of axioms stating that a concept (respectively a relation) is a subconcept (respectively a subrelation) of another. Other typical ontological axioms include concept disjointness (which expresses that two concepts cannot have common instances), the domain and range of binary relations (which specifies the classes of entities that can be linked by this relation), algebraic properties of relations (for instance that a relation is symmetric or transitive), mandatory relations for instances of a class (for instance that every entity of a given class fulfils a given property), and so on.

Ontologies are widely used in data and knowledge management and they are at the core of the Semantic Web (see Chapter 6 of Volume 3). We refer the reader to the chapter on knowledge engineering (Chapter 23 of this volume) for developments on building and using ontologies.

Without denying the importance of the linguistic aspects in ontologies, we focus in this chapter on formal ontologies. Therefore, an ontology will be seen as a logical theory that specifies the expected meaning of the conceptual vocabulary [START_REF] Guarino | Formal ontology and information systems[END_REF]. More specifically, an ontology is given by a formal vocabulary (or signature) and a set of formulas built on this vocabulary, which define the acceptable models of the considered domain. Hence, any reasoning that takes into account an ontology O considers only the models of O: for instance, given two pieces of knowledge G and F, deciding if G is a logical consequence of F, which we denote by F |= G, becomes O, F |= G, i.e., is every model of O and F a model of G? Moreover, in most settings, the unique name assumption is made: in this case, distinct logical constants are necessarily interpreted by distinct elements of the domain of any interpretation.

In this chapter, we consider knowledge bases composed of two types of knowledge: on the one hand, ontological knowledge, which is general knowledge about the modelled domain, and factual knowledge, composed of facts or assertions about specific entities. Usually, a fact is a ground atom, i.e., has no variable. 1A parallel can be drawn between a knowledge base and a classical database (e.g., a relational database). Indeed, the database schema, which includes a vocabulary and integrity constraints, can be associated with an ontology, while data can be seen as factual knowledge. However, some important differences should be noted. In databases, data are supposed to encode a complete description of the 'world'. In other words, the closed world assumption is made (everything that is not asserted in the database is considered as false), as well as the related closed domain assumption (the only existing entities are those encoded in the data). By contrast, the open world assumption is made in knowledge bases (as well as the related open domain assumption); this often leads to more complex reasoning since a knowledge base encodes a possibly infinite set of all of the descriptions of the world that include the known facts and comply with the ontology. For that reason, the use of negation is often restricted, as the excluded-middle law (stating that a proposition is either true or false) leads to combinatorial explosion. The open world assumption may lead to considering existentially quantified variables in facts (and not only constants) to denote unknown individuals. Moreover, the primary aim of databases is to store and retrieve data with efficient query answering techniques, whereas knowledge bases are used to infer new knowledge that was only implicitly represented in the ontology. However, the two domains are becoming progressively closer, especially under the impulse of the Semantic Web. Indeed, there is an increasing interest in answering complex queries on large knowledge bases, on the one hand, and, on the other hand, dropping the closed world assumption in databases.

This chapter is devoted to several knowledge representation and reasoning formalisms used to build and exploit knowledge bases: description logics, graph-based representations (issued from conceptual graphs) and the more recent existential rule framework. Although description logics and graph-based representations are both rooted in semantic networks [START_REF] Lehmann | Semantic Networks in Artificial Intelligence[END_REF], their development from the 80's followed different research lines, as explained in the next sections. Existential rules can be seen both as the logical counterpart of the graph-based framework and as a generalisation of Datalog, the deductive database querying language.

Several different kinds of reasoning over knowledge bases have been considered, among which we distinguish the following fundamental problems. Given a knowledge base (KB) composed of an ontology O and a set of facts I, we consider the following questions:

• Knowledge base satisfiability: determine if the KB is satisfiable (or consistent), i.e., if it has at least one model. • Ontology-mediated query answering: compute the answers to a query q over the KB; when q is a Boolean query (i.e., a query with a yes/no answer), the problem is whether q is entailed by the KB, i.e., whether O, I |= q holds. The general form of a query q is a first-order formula with possibly free variables, say (x 1 , . . . , x k ).

Then an answer to q in the KB is a tuple of constants (c 1 , . . . , c k ) such that the Boolean query obtained from q by substituting each variable x i by the constant c i is entailed by the KB.

The three formalisms presented in this chapter tackle the above problems, the difference being in their expressivity and the kind of query considered. Description logics traditionally allowed for rich descriptions of ontological axioms using different kinds of constructors; standard reasoning tasks were KB satisfiability, concept subsumption (determine if a concept is a specialisation of another, which is a special case of ontological knowledge entailment) and instance checking (determine if a specific individual is an instance of a given concept, which is a special case of fact entailment). Hence, only very specific queries were considered (single atoms without variables). The growing interest for exploiting large and complex data led the description logic community to investigate more expressive queries, however at the price of less expressive description logics, known as lightweight description logics. The queries most commonly considered so far in the context of ontologymediated query answering are so-called conjunctive queries, which are the basic queries in databases: these are existentially quantified conjunctions of atoms. Conjunctive queries are natural queries in the graph-based and existential rule frameworks, but, on the other hand, these formalisms do not offer the variety of ontological axioms found in classical description logics. Some lightweight description logics, however, can be seen as special cases of the graph-based and existential rule frameworks.

The sequel of this chapter introduces each of these three formalisms and compares them from an expressivity viewpoint.

Description Logics

Description logics (DLs) [START_REF] Baader | The Description Logic Handbook: Theory, Implementation, and Applications[END_REF][START_REF] Baader | An Introduction to Description Logic[END_REF] are family of knowledge representation languages corresponding to decidable2 fragments of first-order logic using only unary and binary predicates. While the lack of higher-arity predicates may seem a strong restriction, it turns out that unary and binary predicates (classes and properties) capture a large part of modelling needs. Indeed, DLs provide the basis of the OWL Web Ontology Language [W3C, 2004a], a W3C-standardized ontology language for the Semantic Web [START_REF] Berners-Lee | The semantic web[END_REF]RDF [W3C, 2004b], a popular format for Web data, is likewise restricted to unary and binary predicates.

A DL knowledge base (KB) has two parts: a TBox that contains general knowledge about the application domain, and an ABox that contains facts about particular individuals. The TBox can be viewed as an ontology, which provides a conceptual model for the data stored in the ABox. What distinguishes different DLs is the type of knowledge that can be expressed in the TBox.

Traditionally, the main reasoning problems considered by the DL community are: KB satisfiability, subsumption, and instance checking. Satisfiability testing is essential for identifying modelling errors, while instance checking and subsumption are used to identify TBox axioms and ABox assertions that follow from the knowledge of the KB. As the latter two tasks correspond to forms of logical entailment, they can be reduced to unsatisfiability testing for all DLs that admit full negation. Our discussion of DLs will center on these traditional reasoning tasks. However, we should point out that over the past decade, several additional reasoning tasks for DLs have been investigated, most notably, ontology-mediated conjunctive query answering, which allows for richer queries to be posed over the ABox, but which cannot be reduced to satisfiability testing and thus required the development of new algorithmic techniques (see survey [Bienvenu and Ortiz, 2015] and references therein). There has also been quite a lot of work on reasoning support for building, debugging, and evolving ontologies, e.g., providing explanations for why a given entailment holds [START_REF] Schlobach | Non-standard reasoning services for the debugging of description logic terminologies[END_REF][START_REF] Sebastiani | Axiom pinpointing in lightweight description logics via horn-sat encoding and conflict analysis[END_REF][START_REF] Peñaloza | Understanding the complexity of axiom pinpointing in lightweight description logics[END_REF], or extracting modules of an ontology that conform to some criterion [START_REF] Grau | Modular reuse of ontologies: Theory and practice[END_REF][START_REF] Kontchakov | Logic-based ontology comparison and module extraction, with an application to dl-lite[END_REF][START_REF] Konev | Model-theoretic inseparability and modularity of description logic ontologies[END_REF].

Early work on DLs in the 1980's mostly focused on building reasoning systems, and it was only later that it was discovered that some of these DLs were in fact undecidable or at the very least intractable. These initial negative results led to the introduction of simple DLs for which polynomial-time reasoning was possible, but which turned out to be too limited in their expressivity. In the late 1990's, however, new systems were developed based upon highly optimized tableaux algorithms, which demonstrated acceptable performance for expressive DLs despite their high worstcase complexity. This line of work continues to this day, with ever more sophisticated optimisations targeting ever more expressive DLs. At the same time, there has been renewed interest in lightweight DLs that provide the required scalability for applications involving very large TBoxes and/or ABoxes. Importantly, however, this new breed of low-complexity DLs provides combinations of modelling constructs that are much better suited to the needs of real-world applications than the previous generation of simple DLs.

Nowadays, there is an extensive body of results pinpointing the exact computational complexity of performing different kinds of reasoning in the whole range of DLs, allowing one to choose the optimal trade-off between expressivity and efficiency of reasoning for the application at hand. For an overview of the complexity landscape, interested readers can consult the surveys [START_REF] Ortiz | Reasoning and query answering in description logics[END_REF] and [Bienvenu and Ortiz, 2015].

In this section, we introduce the basics of description logics, and then present several concrete DLs and show how varying the expressivity of the DL impacts the complexity of reasoning.

Preliminaries: DL syntax and semantics

In DL jargon, classes are called concepts and properties are called roles. DL knowledge bases are built starting from a set N C of atomic concepts (unary predicates), a set N R of atomic roles (binary predicates), and a set N I of individuals (constants). We typically use A, B, . . . for atomic concepts, P, Q, . . . for atomic roles, and a, b, . . . for individuals. More complex concept and role expressions can be built using different constructors, with the set of available constructors depending on the particular DL (see further for more details). We will use C, D, . . . to denote (possibly complex) concepts and R, S for (possibly complex) roles.

A DL knowledge base K is a pair T , A , consisting of a TBox T and an ABox A. A TBox is a finite set of axioms expressing the relationships holding between different concepts and roles. The types of axioms allowed in the TBox depends on the choice of DL, but the most common forms of TBox axioms are concept inclusions (C D, with C, D possibly complex concepts) and role inclusions (R S, with R, S possibly complex roles). Equivalences between concepts (C ≡ D) and roles (R ≡ S) are also common and can be seen as shorthand for inclusions in both directions (i.e., C ≡ D is an abbreviation for the pair of inclusions C D and D C).

An ABox is a finite set of assertions expressing that an individual belongs to a given concept (C(a)) or that a pair of individuals belongs to a role (R(a, b)). To simplify the presentation, we will assume in what follows that ABoxes only contain assertions involving atomic concepts and roles. This assumption can usually be made without loss of generality. For example, if we want to include C(a) in the ABox, with C a general concept, it suffices to use the atomic assertion A C (with A C a fresh atomic concept) and add the inclusion C ≡ A C to the TBox.

The semantics of DL knowledge bases is defined in terms of (first-order) interpretations. An interpretation I = (∆ I , • I ) consists of a non-empty domain ∆ I and an interpretation function • I that assigns a set A I ⊆ ∆ I to every atomic concept A ∈ N C , a binary relation P I ⊆ ∆ I × ∆ I to every atomic role P ∈ N R , and an element a I to every individual a ∈ N I . It is common in DLs to adopt the unique name assumption, which states that distinct individuals are mapped to distinct elements of the interpretation domain.

An interpretation I satisfies a concept inclusion C D (resp. role inclusion R S) if C I ⊆ D I (resp. R I ⊆ S I ). We say I is a model of a TBox T if it satisfies every axiom in T . A TBox T logically implies an axiom α, written T |= α, if every model of T satisfies α. A fundamental reasoning task for TBoxes is testing subsumption between different concepts: given a TBox T and two concepts C and D, decide whether T |= C D.

An interpretation I satisfies a concept assertion A(a) (resp. role assertion P(a, b)) if a I ∈ A I (resp. (a I , b I ) ∈ P I ). We call I a model of an ABox A if I satisfies every assertion in A. An interpretation I is a model of a knowledge base T , A if it is a model of both T and A. A KB K is satisfiable (or consistent) if it possesses at least one model. Testing satisfiability of a given KB is another standard reasoning task.

A KB logically entails a TBox axiom or ABox assertion α, written K |= α, if every model of K satisfies α. The instance checking problem is defined as follows: given a KB T , A , a concept C, and an individual a, decide whether K |= C(a).

In the following sections, we give the syntax and semantics of the principal DL constructors by presenting a variety of DLs, ranging from 'simple' DLs EL, FL 0 , and DL-Lite which offer polynomial-time reasoning (Sections 2.2 and 2.3), to ALC (Section 2.4) which is often considered the prototypical DL, to highly expressive DLs like SROIQ (Section 2.5), which provide the logical foundations for OWL.

Lightweight description logics: FL 0 and EL

We begin by considering two DLs, FL 0 and EL, which are deliberately restricted in expressivity in order to allow for sound and complete polynomial-time reasoning. Both logics contain the concept conjunction constructor (C 1 C 2 ), which corresponds to intersecting the classes represented by C 1 and C 2 . Additionally, FL 0 offers qualified value restrictions (∀R.C), while EL offers qualified existential restrictions (∃R.C), which provide suitably restricted forms of universal and existential quantification. In EL, one can further use the top concept ( ), which denotes the class of all objects.

Figure 1 provides an example of a taxonomy of classes, formulated using a set of inclusions between atomic concepts. Such simple axioms form the backbone of realworld ontologies, and they are available in every DL (and in particular, in FL 0 and EL). The axioms in the first line of Figure 1 stipulate that professors and teaching assistants are both kinds of teaching staff, and every teaching assistant is a graduate student. The remaining axioms state that teaching staff and admin staff are two types of staff and that students (resp. courses) can be specialized into undergraduate and graduate students (resp. courses). In FL 0 and EL, we can additionally use the conjunction constructor to state that every student that is part of the teaching staff must be a graduate student:

Prof TeachingStaff TAssistant TeachingStaff TAssistant GradStudent TeachingStaff Staff AdminStaff Staff UndergradStudent Student GradStudent Student UndergradCourse Course GradCourse Course

Student TeachingStaff GradStudent

By making use of qualified value restrictions, we can express in FL 0 that graduate students only take graduate courses and that a student that takes only graduate courses is a graduate student: GradStudent ∀takes.GradCourse Student ∀takes.GradCourse GradStudent

In EL, we can use qualified existential restrictions to formulate the following axioms:

Student ∃takes.Course ∃teaches. TeachingStaff ∃teaches.GradCourse Prof TeachingStaff ∃teaches.Course which state respectively that every student must take some course, that everyone who teaches something is a member of the teaching staff, that everyone who teaches a graduate course must be a professor, and that every member of teaching staff must teach some course. The semantics of complex concepts built using the preceding constructors is defined recursively as follows (starting from the semantics of atomic concepts and roles which is directly provided by each interpretation):

• I = ∆ I • (C 1 C 2 ) I = C I 1 ∩C I 2 • (∃R.C) I = {o 1 | there exists (o 1 , o 2 ) ∈ R I such that o 2 ∈ C I } • (∀R.C) I = {o 1 | (o 1 , o 2 ) ∈ R I implies o 2 ∈ C I }
Every DL concept can be translated into a first-order logic formula with one free variable. Figure 2 gives the first-order translation of concepts in FL 0 and EL, using X as the free variable. To improve readability, we commit a slight abuse of notation by using C(X) to designate the translation of the concept C using free variable X. Every TBox axiom can be translated into a corresponding FOL sentence (that is, a formula without free variables): a concept inclusion C D gives rise to the formula ∀X(C(X) → D(X)) and an equivalence axiom C ≡ D corresponds to the formula ∀X(C(X) ↔ D(X)).

For example, if C = A ∃R.B, with A and B atomic concepts, then C(X) is the FOL formula A(X) ∧ ∃Y [R(X,Y ) ∧ B(Y )]. DL notation Corresponding FOL formula C 1 C 2 C 1 (X) ∧C 2 (X) ∃R.C ∃Y [R(X,Y ) ∧C(Y )] ∀R.C ∀Y [R(X,Y ) → C(Y )]
The first polynomial-time reasoning procedures for lightweight DLs relied upon structural subsumption, in which concept expressions are first put into a normal form and then compared syntactically. This method can be used to show that subsumption between concepts w.r.t. an empty TBox is tractable in both FL 0 and EL. However, in most applications, one wishes to compute subsumption in the presence of a non-empty TBox. Rather interestingly, FL 0 and EL exhibit dramatically different complexities for the general version of subsumption. In FL 0 , the problem becomes EXPTIME-complete (and thus provably intractable) [START_REF] Baader | Pushing the EL envelope[END_REF] and remains coNP-hard even when restricted to TBoxes in the form of acyclic terminologies [START_REF] Nebel | Terminological reasoning is inherently intractable[END_REF]. By contrast, in EL (and several of its extensions), subsumption can be decided in PTIME in the presence of arbitrary TBoxes [START_REF] Baader | Pushing the EL envelope[END_REF]. This tractability result relies upon forward-chaining algorithms that construct in an iterative manner a subset of the axioms that are entailed from the TBox. A similar approach can be used to handle instance checking in EL.

Nowadays, EL and its extensions have become popular ontology languages, whereas FL 0 is no longer much in use. This is due in large part to the much more favourable computational properties of EL, but also to the utility of the constructors provided by EL. Indeed, while it was initially believed that value restrictions were more useful than existential restrictions, it turns out that (slight extensions of) EL closely match the modelling needs of many applications, particularly those in the biomedical domain. Indeed, the large-scale professional medical ontology SNOMED CT3 (Systematized Nomenclature of Medicine, Clinical Terms), developed by an international consortium for use in the health-care systems of several countries, is expressed in a tractable DL of the EL family. The importance of EL is further witnessed by the inclusion of the OWL 2 EL profile [W3C, 2012b], based upon EL, in the latest version of the W3C OWL standard.

DL-Lite: Another lightweight description logic

The DL-Lite family of description logics [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The dllite family[END_REF] was proposed in the mid-2000's with the aim of supporting tractable reasoning while at the same time capturing the principal modelling primitives from conceptual modelling (more precisely, the entity-relationship models utilized in databases and information systems [START_REF] Chen | The entity-relationship model: Toward a unified view of data[END_REF]) and UML4 diagrams from software engineering). Another important motivation for introducing the DL-Lite family was to make it possible to answer more expressive queries by means of a reduction to relational databases.

In DL-Lite, complex concepts and roles can be constructed from atomic concepts and roles according to the following syntax:

B ::= A | ∃R C ::= B | ¬B R ::= P | P - E ::= R | ¬R
where A is an atomic concept, P is an atomic role, and P -is the inverse of P. Here B is called a basic concept, and C is a general concept. Likewise, we have basic roles R and general roles E. For completeness, we formally state the semantics of non-atomic concepts and roles:

• (P -) I = {(o 2 , o 1 ) | (o 1 , o 2 ) ∈ P I } • (∃R) I = {o 1 | there exists o 2 and (o 1 , o 2 ) ∈ R I } • (¬B) I = ∆ I \ B I and (¬R) I = ∆ I × ∆ I \ R I Figure 3
gives the corresponding logical formulas. Note that when we write R(X,Y ), we mean P(X,Y ) if R is an atomic role P and P(Y, X) if R is the inverse role P -. There are several different DL-Lite dialects, each allowing for different TBox axioms. In the core DL-Lite dialect, TBoxes are comprised of concept inclusions B C, where B is a basic concept and C a general concept. Observe that since only basic concepts are allowed on the left-hand side of inclusions, negation can only occur on the right-hand side. To illustrate the expressive power of DL-Lite (core), we return to our running example of the university domain. We first remark that all of the atomic concept inclusions from Figure 1 can be expressed in DL-Lite. Figure 4 displays DL-Lite axioms that constrain the domain and range of the roles teaches, takes, and coordinatorFor:

DL notation Corresponding FOL formula P

- P(Y, X) ∃R ∃Y R(X,Y ) ¬B ¬B(X) ¬R ¬R(X,Y )
• if X teaches Y, then X is a member of teaching staff and Y is a course • if X takes Y, then X is a student and Y is a course • if X coordinatorFor Y, then X is a professor Y is a course
In DL-Lite, we can also express disjointness constraints, stating that two classes or properties have no elements in common, as well as mandatory participation constraints, requiring that elements of a certain class appear in the first or second components of a given binary relation. For example, the following axioms express that Student and AdminStaff are disjoint classes, that every professor must teach something, and that every course is taught by someone:

Student ¬AdminStaff

Prof ∃teaches Course ∃teaches -

We remark that if we replaced the inclusion Student ¬AdminStaff by Student ¬Staff, then this would lead to an anomaly in the ontology. Indeed, using the atomic concept inclusions in Figure 1, we would be able to infer that teaching assistants belong to the class Staff (from TAssistant TeachingStaff and TeachingStaff Staff) as well as to its complement ¬Staff (using TAssistant GradStudent, GradStudent Student, and Student ¬Staff). This would mean that TAssistant must always be interpreted as the empty class, and thus that including even a single instance of TAssistant in the ABox would lead to an inconsistent KB. Two other common dialects, DL-Lite R and DL-Lite F , offer additional TBox axioms. The former allows for role inclusions of the form R E, while the latter authorizes functionality axioms of the form ( f unct R), where R is a basic role, i.e., without negation. For example, the following two axioms are expressible in DL-Lite R and DL-Lite F respectively:

coordinatorFor teaches ( f unct coordinatorFor -)
The first axiom expresses that when X coordinatorFor Y, then X teaches Y, while the second one expresses that the role coordinatorFor -is functional: if Y coordinatorFor X and Z coordinatorFor X then Y=Z.

A role inclusion R E is satisfied in an interpretation I if R I ⊆ E I , and a functionality statement

( f unct R) is satisfied in I if the binary relation R I is a function, i.e. (o, o 1 ) ∈ R I and (o, o 2 ) ∈ R I implies that o 1 = o 2 .
It has been shown in [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The dllite family[END_REF] that in both DL-Lite R and DL-Lite F , satisfiability, subsumption, and instance checking can all be performed in polynomial time (more precisely, these tasks are NLOGSPACE-complete). Rather surprisingly, however, if we consider the minimal DL that extends both DL-Lite R and DL-Lite F , then satisfiability testing becomes EXPTIME-complete [START_REF] Artale | The DL-Lite family and relations[END_REF]. Moreover, in both DL-Lite R and DL-Lite F , it is possible to answer conjunctive queries in polynomial time in the size of the ABox by means of a reduction to the problem of answering first-order queries over relational databases, whereas no such reduction is possible if both role inclusions and functionality axioms are allowed [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The dllite family[END_REF]. (Ontology-mediated conjunctive query answering and the technique of first-order query rewriting will be discussed in more detail in Sections 3 and 4.)

The importance of the DL-Lite family of DLs is witnessed by the inclusion of the OWL 2 QL profile [W3C, 2012b], based upon DL-Lite R , in the OWL 2 standard, which is specifically designed to be the ontology language of choice for applications involving querying of large amounts of data.

ALC: The prototypical description logic

The description logic ALC can be seen as the result of adding (full) concept negation to EL. In ALC, it is possible to construct the disjunction (or union) of two concepts C 1 C 2 (which is just shorthand for ¬(¬C 1 ¬C 2 )), qualified value restrictions (since ∀R.C is equivalent to ¬(∃R.¬C)), and the bottom concept ⊥ (corresponding to ¬ , which is always interpreted as the empty set).

ALC is often considered to be the prototypical DL because it is a fragment of a natural first-order logic (allowing the standard Boolean operators plus restricted forms of universal and existential quantification) and because ALC concepts correspond precisely to the formulas expressible in the basic multi-modal logic K n [START_REF] Blackburn | Handbook of Modal Logic[END_REF]. Returning to our university example, we first note since ALC extends both FL 0 and EL, all axioms from Section 2.2 can be expressed in ALC. Additionally, the new constructors available in ALC allow us to express disjointness constraints, as in DL-Lite, and covering constraints, e.g., that every course is either an undergraduate course or a graduate course:

Student ¬Prof

Course UndergradCourse GradCourse

For completeness, we formally specify the semantics of the new constructors:

• ⊥ I = / 0 • ¬C I = ∆ I \C I • (C 1 C 2 ) I = C I 1 ∪C I 2
The problem of testing satisfiability of ALC KBs has been shown to be EXPTIMEcomplete [START_REF] Schild | A correspondence theory for terminological logics: Preliminary report[END_REF]. The same result holds for subsumption testing and instance checking, which can be straightforwardly reduced to (un)satisfiability:

• T |= C D iff the KB T ∪ {A C ≡ C, A ¬D ≡ ¬D}, {A C (a), A ¬D (a)} is unsatis- fiable • K |= C(a) iff the KB K ∪ {A ¬C ≡ ¬C}, {A ¬C (a)} is unsatisfiable.
To determine whether a given ALC KB is satisfiable, one can use tableaux algorithms, which work by exploring in an exhaustive manner all ways of constructing a model of the KB. If a (compact representation of a) model is found, the KB is satisfiable, and if all attempts fail, then one can conclude that the KB is unsatisfiable.

From ALC to SHIQ to SROIQ: Highly expressive DLs

The description logic ALC is the starting point for defining other (highly) expressive DLs. For example, the DL SHIQ [START_REF] Horrocks | Practical reasoning for expressive description logics[END_REF] extends ALC with inverse roles (P -, as in DL-Lite), (qualified) cardinality restrictions (≥ n R.C, ≤ n R.C), role inclusions (R R ), and transitive roles (using transitivity axioms of the form (Trans R)), where R, R can be either plain or inverse roles.

In our university example, we could use cardinality restrictions to express that every professor must teach at least 2 courses, and students that take at most 3 courses are part-time students:

Prof ≥ 2teaches.Course Student ≤ 3takes.Course PartTimeStudent
The even more expressive SROIQ [START_REF] Horrocks | The even more irresistible SROIQ[END_REF], which provides the logical underpinnings of OWL 2 (the latest version of OWL standard) [W3C, 2012a], extends SHIQ with nominals ({a}), the universal role (u), and more complex role axioms of the forms R • S R and S • R R (where • denotes role composition). It further allows for roles to be declared as reflexive, irreflexive, or antisymmetric, and for pairs of role to be declared disjoint.

The semantics of the new constructors is as follows:

• (≥ nP.C) I = {d ∈ ∆ I | {e | (d, e) ∈ P I and e ∈ C I } ≥ n} • (≤ nP) I = {d ∈ ∆ I | {e | (d, e) ∈ P I and e ∈ C I } ≤ n} • {a} I = {a I } • u I = ∆ I × ∆ I • (R•S) I = {(d 1 , d 3 ) ∈ ∆ I ×∆ I | there exists d 2 ∈ ∆ I such that (d 1 , d 2 ) ∈ R I and (d 2 , d 3 ) ∈ S I } An axiom of the form (Trans R) is satisfied in I if R I is a transitive relation, i.e., (d 1 , d 2 ) ∈ R I and (d 2 , d 3 ) ∈ R I implies (d 1 , d 3 ) ∈ R I .
TBox axioms declaring roles to be reflexive, irreflexive, or antisymmetric are handled analogously.

In the DL SHIQ, the standard reasoning tasks (satisfiability, subsumption, and instance checking) are all EXPTIME-complete, and thus of the same complexity as in ALC. For the DL SHOIQ obtained by adding nominals to SHIQ, the complexity rises to NEXPTIME-complete, and for SRIQ, which extends SHIQ with complex role inclusions and additional types of axioms concerning roles, the problem becomes 2EXPTIME-complete. If we move all the way up to SROIQ, then reasoning becomes even more difficult (2NEXPTIME-complete).

The preceding complexity results show that automated reasoning with (highly) expressive DLs like ALC, SHIQ, and SROIQ may require (doubly) exponential time in the worst case. However, in practice, modern DL reasoners5 , mainly employing highly optimized tableaux algorithms, demonstrate acceptable performance for reasonably-sized ontologies. The reason is that the type of ontological constraints that are needed to model even complex real-world applications do not give rise to the pathological combinations of constructors that are required for establishing the negative complexity results.

Finally, several proposals have been made to overcome a limitation of description logics, which is the tree-shaped structure of terminological descriptions, in particular by combining them with Datalog rules. These proposals impose restrictions on the interaction between DL axioms and datalog rules, as early work has shown undecidability of standard reasoning if no restriction was made [START_REF] Levy | Combining horn rules and description logics in carin[END_REF]]. The existential rules presented in Section 4 can be seen as another way of overcoming the tree-shaped structure limitation of description logics.

Conceptual Graphs

Conceptual graphs [START_REF] Sowa | Conceptual Graphs[END_REF][START_REF] Sowa | Conceptual Structures: Information Processing in Mind and Machine[END_REF] are mainly rooted in semantic networks, natural language processing and Peirce's existential graphs, a diagrammatical system of logic alternative to predicate logic. They have been studied along different directions. One research line consists in developing conceptual graphs as a graphical interface to first-order logic. Another research line follows the existential graph approach: conceptual graphs are then seen as diagrams, rather than graphs in the graphtheoretic meaning, and inferences are based on diagrammatic operations that do not aim to be automated (see, in particular, [START_REF] Dau | The Logic System of Concept Graphs with Negation And Its Relationship to Predicate Logic[END_REF]). A third research line, which is the one presented in this chapter, develops conceptual graphs as a knowledge representation and reasoning formalism, equipped with its own reasoning mechanisms. This formalism is both graph-and logic-based: on the one hand, the basic objects are labelled graphs and reasoning is based on graph operations, with graph homomorphism at the core; on the other hand, these objects have a logical semantics and reasoning mechanisms are sound and complete with respect to this semantics. This approach to conceptual graphs is similar to the description logic approach in the sense that it defines and studies a family of formalisms that offer different tradeoffs between expressivity and complexity of reasoning. However, we will see in Section 3.5 that the logical fragments studied in both families are quite different. The interested reader will find an in-depth presentation of theoretical and algorithmic results on conceptual graphs in [START_REF] Chein | Graph-based Knowledge Representation and Reasoning-Computational Foundations of Conceptual Graphs[END_REF]. All aspects presented here are implemented in the software tools CoGUI6 and CoGITaNT7 .

The Kernel: Basic conceptual graphs

A basic conceptual graph (BG) defines entities and relationships among these entities. Hence, it is a bipartite graph: one class of nodes, called concept nodes, represents entities, and the other class, called relation nodes, represent relationships among these entities. Nodes are labelled according to a vocabulary, which contains a set of concept types and a set of relation symbols, with both sets being partially ordered by specialisation. This vocabulary can be seen as a lightweight ontology, which can be further enriched by rules and constraints in more complex conceptual graph fragments.

Syntax

A vocabulary, also called a support, is a triple (T C , T R , I) where:

• T C is a finite set of concept types, partially ordered by ≤, and provided with a greatest element, denoted by ; The partial orders on T C and T R encode a specialisation relation, i.e., t ≤ t means that "t is a specialisation of t". Figure 5 pictures a set of concept types, which correspond to the set of DL inclusions from Figure 1 except for the part in italics. Each individual marker refers to a specific and distinct entity (i.e., the unique name assumption is made) and the generic marker refers to an unspecified entity.

• T R
A basic conceptual graph (BG) G = (C G , R G , E G , l G ) defined over a support S = (T C , T R , I
) is a finite, labelled, undirected and bipartite multigraph (i.e., there may be several edges between two nodes), where C G is the set of concept nodes, R G is the set of relation nodes, E G is the multiset of edges, and l G is a labelling function of the nodes and edges that satisfies the following conditions:

• each concept node c is labelled by a concept type t c and a marker m such that

(t c , m) ∈ T C × (I ∪ { * }) ; if m = * , c is called generic, otherwise it is individual; • each relation node r is labelled by a relation t r ∈ T R
and the number of edges incident to r is equal to the arity of t r ; these edges are labelled from 1 to the arity of t r ; we denote by (c 1 . . . c k ) the list of arguments of r, where c j denotes the extremity of the j-th edge incident to r.

Note that a BG is not necessarily connected. By convention, concept nodes are pictured as rectangles and relation nodes as ovals. For instance, the BG H pictured in Figure 6 may represent the following knowledge "there is a professor coordinator for a course on databases and a course on logics in the graduate degree MSc IA". A BG can also be seen as a hypergraph, with the relations being encoded by hyperedges. Then the graph view of a BG corresponds to the incidence bipartite graph of this hypergraph.

The notion of a support can be extended to allow for multi-instantiation. Then a concept node is labelled by a set of concept types, called a conjunctive type, instead of a single concept type. For instance, a course can be both a course in mathematics and a course in computer science, which is denoted by the conjunctive type {Maths,CS}. The set of concept types T C is then defined in intension by a partially ordered set of primitive types, and its elements are all the conjunctive types that can be built with from primitive types. The partial order on conjunctive types is the natural extension of the order on primitives types: given conjunctive types t 1 and t 2 , t 2 ≤ t 1 if for all primitive type t 1 i in t 1 , there is a primitive type t 2 j in t 2 with t 2 j ≤ t 1 i . For instance, {Logics} ≤ {CS, Maths} (note that {CS, Maths} ≤ {Logics}).

Semantics

This basic formalism is provided with a semantics in first-order logic by a translation denoted by Φ. Concept types are translated into unary predicates, relation symbols into predicates with the same arity and individual markers into constants (for simplicity, the same names are used for the elements of the support and their translation). To a support S is assigned a set of formulas Φ(S) that translates the partial orders on T C and T R , i.e., if t 2 ≤ t 1 , one has the formula ∀x 1 . . .

x k (t 2 (x 1 . . . x k ) → t 1 (x 1 . . . x k )),
where k is the arity of predicates t 1 and t 2 .

A BG is translated into a formula Φ(G) built as follows: to each concept node is assigned a term, which is a new variable if its marker is generic, otherwise the constant assigned to its individual marker; to each relation (resp. concept) node is assigned an atom t(e 1 , . . . , e k ) where t is the predicate assigned to its label (resp. concept type) and (e 1 , . . . , e k ) is the list of terms assigned to its arguments (resp. the term assigned to the concept node); Φ(G) is then the existential closure of the conjunction of these atoms. For instance, for H in Figure 6:

Φ(H) = ∃x∃y∃z(Pro f (x) ∧ DBs(y) ∧ Logics(z) ∧ coordinatorFor(x, y) ∧ coordinatorFor(x, z) ∧ curriculum(y, MScIA) ∧ curriculum(z, MScIA) ∧ GradDegree(MScIA)).
The BG fragment is equivalent to the existential, positive and conjunctive fragment of first-order logic (without functional symbols except for constants). Indeed, a polynomial translation of the support and BGs, which preserves logical entailment, allows one to obtain a "flat" support S for which Φ(S ) = / 0. The fundamental notion for reasoning on BGs is a homomorphism (often called "projection" in the conceptual graph community). A homomorphism from a BG G to a BG H is a mapping from C G ∪ R G to C H ∪ R H that preserves the node bipartition and the edges, and may specialize node labels, i.e.,

• for all relation r ∈ R G with arguments (c 1 . . . c k ), h(r) has arguments (h(c 1 ) . . . h(c k )) (equivalently: for all edge rc in G, there is an edge h(r)h(c) with the same label in H) ; • for all node x ∈ C G ∪ R G , l H (h(x)) ≤ l G (x) (for concept nodes one considers the product order on T C × (I ∪ { }), i.e., (t, m) ≤ (t , m ) if t ≤ t and m ≤ m ).

Consider the graphs in Figure 6 and assume that coordinatorFor ≤ teaches is the only comparable pair of distinct relations: there are two homomorphisms from G to H. The first one maps concept nodes in this way: a → x, b → y , c → z, d → t, e → t; each relation node teaches is mapped to a relation node coordinatorFor and each relation node curriculum is mapped to a node with the same label. Note that both entities of type GradDegree are mapped to a single entity, which is identified as "the MSc AI". The second homomorphism maps concept nodes in this way: a → x, b → z , c → z, d → t, e → t. This homomorphism uses the fact that Logics is a specialisation of both Maths and CS, which allows one to map b and c to z.

BG-homomorphism induces a preorder on BGs, called the "specialisation / generalisation" relation: in the following, we note H ≤ G (H is a specialisation of G) if there is a homomorphism from G to H. This relation is sound and complete with respect to logical entailment on the formulas assigned to the BGs (also using the formulas assigned to the support), i.e., for all BGs G and H on a support S, H ≤ G if and only if Φ(S), Φ(H) |= Φ(G). Completeness is up to a normality condition for H: an individual marker has to occur at most once in H (in other words, two distinct nodes cannot refer to the same identified entity). The following problem, called BG-Homomorphism is thus the fundamental problem on BGs: given two BGs G and H, is there a homomorphism from G to H? This problem is NP-complete in general, but belongs to PTime when the source graph (i.e., G) is an acyclic graph (or an acyclic hypergraph, this latter notion being more general than the former), and more generally if it has a bounded treewidth (or hypertreewidth).

Homomorphism being a fundamental notion in the study of relational structures, it is not surprising that BG-Homomorphism is strongly equivalent to other fundamental problems in AI and databases, which allows one to import algorithmic techniques from one domain to another. The logical translation of a BG is the same as a (Boolean) conjunctive query (CQ) in databases. The problems of evaluating a conjunctive query (e.g., given a CQ q and a relational database instance D, does D contain an answer to q?) or determining if a conjunctive query is contained in another (given two CQs q 1 and q 2 , is the set of answers to q 1 included in the set of answers to q 2 for any database instance?) are essentially the same as BG-Homomorphism. The same remark holds for the basic constraint satisfaction problem (CSP): given a constraint network (in which constraints are given in extension), does this network have a solution? (see Chapter 6 of Volume 2).

Finally, let us consider the ontology-mediated query answering problem in the conceptual graph framework, where the knowledge base is composed of a support (the ontology) and of BGs (the facts), and the query is itself a BG. Checking if the query is entailed by the KB is NP-complete in combined complexity (since it amounts to a BG-homomorphism test) and polynomial in data complexity.8

Simple extensions of the support

Two simple extensions of the support are often considered, namely relation signatures and concept type incompatibility. A relation signature specifies the maximal type of each of its arguments. Formally, one adds to the support a mapping σ that assigns to each relation r with arity k a signature σ (r) ∈ (T C ) k . Let σ i (r) denote the i-th element of σ (r); the formula assigned to σ (r) is:

∀x 1 . . . x k (r(x 1 . . . x k ) → σ 1 (r)(x 1 ) ∧ . . . ∧ σ k (r)(x k ))
Figure 7 shows a partially ordered set of relations with their signature that corresponds to the set of DL inclusions from Figure 4, except for the part in italics. Relation signatures must be covariant with respect to the partial orders on concept types and relations: for all relations r 1 et r 2 with arity k, if r 1 ≤ r 2 then σ (r 1 ) ≤ σ (r 2 ), i.e., for all i, σ i (r 1 ) ≤ σ i (r 2 ). This covariance condition translates the fact that when a relation is specialized into another, the maximal type of each argument can be specialized as well, but not generalized. For instance, if the relation teaches links an entity of type TeachingStaff to an entity of type Course, its specialisation into the relation coordinatorFor may enforce that the first argument is of type Prof, which is a specialisation of TeachingStaff.

The support added with relation signatures can be seen as a generalisation of the ontological part of RDFS (i.e., the schema) with relations of any arity (see [START_REF] Baget | Translations between rdf(s) and conceptual graphs[END_REF] for translations between RDFS and basic conceptual graphs).

When multi-instantiation is allowed, i.e., when conjunctive concept types are considered, it is useful to express incompatibility between concept types. This can be achieved by stating that some conjunctive types are forbidden. The logical formula assigned to a banned type {t 1 ,t 2 } is the following:

∀x¬(t 1 (x) ∧ t 2 (x))
The set of banned types is said to be compatible with the set of primitive types if no primitive type is a specialization of a banned type. For instance, the banned type {Student, Staff } (which corresponds to the DL inclusion Student ¬Staff ) is not compatible with Student ≤ Staff, a fortiori with GradStudent ≤ Staff. A BG complies with the set of banned types if no node is labelled by a concept type that specializes a banned type. Note that the logical translation Φ(S) of a support S added with banned types is always consistent. However, for a BG F on S, Φ(S) ∪ Φ(F) may be inconsistent.

Conceptual graph rules

Rules of the form " if premise then conclusion" are an essential knowledge construct in AI. They represent implicit knowledge that can be made explicit by applying them to factual knowledge. A basic graph rule is a pair R = (P(c

1 1 . . . c 1 k ),C(c 2 1 . . . c 2 k )),
where k ≥ 0, P and C are BGs, and the c 1 i (respectively c 2 i ) are distinct generic concept nodes from P (respectively C) called the frontier nodes of the rule. In Figure 8 the bijection between the frontier nodes of the premise and of the conclusion is depicted by dotted lines; the blue nodes form the conclusion of the rule. This rule represents the following knowledge: "if a student X takes a course Y then there is a teaching staff member Z who teaches Y and teaches to X". The logical translation of a BG-rule R = (P(c

1 1 . . . c 1 k ),C(c 2 1 . . . c 2 k )) is the for- mula Φ(R) = ∀x 1 . . . x k (Φ (P) → Φ (C))
, in which the same variable x i is assigned to frontier nodes c 1 i and c 2 i , and Φ (P) (resp. Φ (C)) is obtained from Φ(P) (resp. Φ(C)) by leaving variables x 1 . . . x k free. Equivalently, all the variables in the premise of the rule can be universally quantified, in which case their scope is the whole formula. The logical translation of a rule is thus exactly an ex-istential rule, as defined in the next section. For instance, the logical translation of the rule R from Figure 8 is Φ(R) = ∀x∀y((Student(x) ∧Course(y) ∧ takes(x, y)) → ∃z(TeachingSta f f (z) ∧ teaches(z, y) ∧ teachesTo(z, x))).

BG-rules are provided with forward and backward chaining mechanisms that proceed directly on their graphical form. A BG-rule R is applicable to a BG F if there is a homomorphism h from its premise to F; applying R to F according to h consists of adding C to F, then merging each frontier node c 2 i from C with the node h(c 1 i ) from F. 9 Rule application is the basis of a sound and complete forward chaining mechanism, i.e., given a knowledge base K = (S, F, R), where S is the support, F is the fact base (remember that a BG needs not to be connected) and R is the set of rules, and a BG Q (which can be seen as a query), Φ(K) |= Φ(Q) if and only if there is a sequence of applications of rules in R leading from F to a BG F such that F ≤ Q.

The backward chaining mechanism relies on a specific unification operation (between two subgraphs, respectively of a rule conclusion and of the current BG query), which exploits the complex structure of rule conclusions induced by non-frontier concept nodes (see the existential variables in existential rules). Hence, instead of processing a goal atom by atom as backward chaining a la Prolog would do, entire subgraphs are unified at once. This mechanism is also sound and complete.

Note that the partial orders on concept types and relations can be encoded by BG-rules. Indeed, t 1 ≤ t 2 is logically translated into the logical rule ∀x 1 . . .

x k (t 1 (x 1 ...x k ) → t 2 (x 1 ...x k )),
where k is the arity of the associated predicates. However, the fact that the partial orders are intrinsically taken into account in BGhomomorphism (which allows one to compare concept types or relations in constant time, or almost constant time, depending on the order encoding) leads to better algorithmic efficiency.

BG-rules are able to simulate the behavior of a Turing machine, hence they provide a model of computation. Therefore, the associated entailment problems are undecidable. However, many decidable cases obtained by syntactic restrictions on rules, or sets of rules, have been defined, mostly in the framework of existential rules (see Section 4.3).

Conceptual graph constraints

A BG-constraint has the same shape as a BG-rule. It can be positive or negative, depending on whether it expresses an obligation or a prohibition. A positive constraint (P,C) expresses knowledge of the form "whenever P is true, C must also be true". 9 If c 1 i and c 2 i have the same concept type, the obtained node is labelled by the same label as h(c 1 i ) ; if the type of c 2 i is strictly more specific than the type of c 1 i , it may happen that the labels of h(c 1 i ) and c 2 i are incompatible (with respect to banned types), which points to an inconsistency in the knowledge base; otherwise, the label of the obtained node is the greatest lower bound of both labels: the obtained type is the conjunction of the types of h(c 1 i ) and c 2 i and the obtained marker is the smallest of both markers.

It is satisfied by a BG if every homomorphism from P to F can be extended to a homomorphism from C to F (i.e., given h the considered homomorphism from P to F, there is a homomorphism h from C to F such that h (c 2 i ) = h(c 1 i ) for all frontier nodes). A negative constraint (P,C) expresses knowledge of the form "whenever P is true, C must not be true". It is satisfied by a BG if no homomorphism from P to F can be extended to a homomorphism from C to F. A negative constraint can also be represented as a BG, let C -, obtained by merging P and C on their frontier nodes (with each c 1 i being merged with c 2 i ); then C -is satisfied by F if there is no homomorphism from C -to F.

For instance, the constraint that a student cannot belong to the administrative staff can be expressed by the formula ∀x(Student(x) → ¬AdminSta f f (x)), which corresponds to the form (P,C), or by the equivalent formula ¬∃x(Student(x) ∧ AdminSta f f (x)), which amounts to forbid a BG. Note that the extensions to the support introduced in Section 3.2 can be encoded by constraints, namely relation signatures by positive constraints and banned types by negative constraints. Other frequent forms of constraints in ontologies are cardinality constraints: positive constraints allow one to express the condition "at least 1" (like "every professor must teach at least one undergraduate course") and negative constraints the condition "at most 0" (like "no teaching assistant can be coordinator for a course").

Negative constraints can actually be seen as particular positive constraints (with C restricted to a concept node with banned type). Positive constraints strictly generalize negative constraints, in the sense that the associated consistency problems are not in the same complexity class: the problem of determining whether a given BG satisfies a given constraint is co-NP-complete if the constraint is negative, and Π 2 P -complete otherwise. Finally, equality is represented in conceptual graphs by so-called "co-reference links" which pairwise connect concept nodes that refer to the same entity. While co-reference links do not increase the expressivity of BG (though their use may be interesting for visualisation purposes), they do increase the expressivity of BG-rules, allowing in particular to express functional dependencies.

Relationships with description logics

Description logics and conceptual graphs are both rooted in semantic networks. They both remedy two criticisms on these common ancestors, i.e., the lack of distinction between factual and ontological knowledge, and the lack of formal semantics. Due to these common properties, their relationships have often been questioned.

Provided that relations are restricted to binary relations, a support can be seen as a simple TBox composed of atomic concept and atomic role inclusions. Relation signatures then correspond to the notions of domain and range, and banned concept types to class disjointness constraints. On the other hand, an ABox can be seen as a particular BG without generic concept nodes.

With the aim of characterizing the intersection of BGs (on a simple support) and DLs, two equivalent fragments were identified in [START_REF] Baader | Tractable and Decidable Fragments of Conceptual Graphs[END_REF]. On the CG side, we obtain rooted BG trees with binary relations. On the DL side, we obtain the DL ELIRO 1 (a DL specially tailored for the comparison), in which the constructors are ∃R.C (existential restriction), C D (concept intersection), R -(role inverse), R R (role intersection) and {i} (unary one-of, where i is an individual, which allows one to integrate specific individuals in concept expressions). It is to be noticed that this comparison with conceptual graphs was one of the sources of the EL family, in which homomorphism is a central notion [Baader et al., 1999a].

In this intersection, both formalisms lose some natural features: on the CG side, relations of any arity and unrestricted structure, in particular cycles on generic concept nodes, while, on the DL side, the variety of constructors.

Other results support the claim that both formalisms are quite "orthogonal". On the one hand, it is known that even the most expressive DLs cannot express the whole existential positive conjunctive fragment of first-order logic [START_REF] Borgida | On the relative expressiveness of description logics and predicate logics[END_REF]. On the other hand, BG-homomorphism cannot handle negation in a logically complete way, even when restricted to atomic negation on primitive concept types.

More relationships between DLs and CGs can be found if we turn our attention to richer fragments of conceptual graphs including some classes of BG-rules and negative BG-constraints on the one hand, and to the ontology-mediated query answering problem on the other hand. Indeed, description logics historically focused on reasoning about the ontology (i.e., the TBox). The instance checking problem can only be seen as a very specific querying problem, which asks if a given individual belongs to a given concept. To handle conjunctive queries, new description logics were considered more recently (see Sections 2.2 and 2.3), such as the DL-Lite family, specifically designed to query data, the EL family, and more generally Horn description logics. These DLs can be seen as specific fragments of the existential rule framework (see the next section), which in turn can be seen as the logical translation of the conceptual graph framework described in this section.

Existential Rules

As already mentioned, the increasing volume of complex and heterogeneous data has spurred an intense research effort on the issue of ontology-mediated query answering in recent years. This work has deeply modified the description logic field and led to the emergence of new dialects and algorithmic techniques (Section 2.3). Meanwhile, the framework of existential rules has been developed to address this issue. The existential rule framework has a double origin: on the one hand it corresponds to the logical translation of the conceptual graph fragment (BGs, rules and negative constraints) presented in the previous section [Baget et al., 2011a], on the other hand it has been proposed as an extension to Datalog, the language of deductive databases, under the name Datalog± [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF].

In the relational database field, Datalog was originally designed to provide firstorder queries (or equivalently, core SQL queries) with recursivity [START_REF] Abiteboul | Foundations of Databases[END_REF]. In its plain version (i.e., without negation nor disjunction), a Datalog query can be seen as a set of rules, which are closed formulas of the form ∀x 1 . . . x n (B → H) , where B and H, respectively called the body and the head of the rule (according to the logic programming terminology), are conjunctions of atoms; moreover, these rules satisfy the constraint of being "range-restricted", i.e., all the variables that occur in the head of a rule must also occur in its body. Hence, a plain Datalog rule is logically into a Horn clause without function symbols. These rules could be used as a means of encoding implicit background knowledge. However, they lack a property considered crucial for representing ontological knowledge, which is the ability to reason on open domains. Indeed, when the open-world assumption is made, it cannot be assumed that the only existing entities are those encoded in the data. Hence, one should be able to infer knowledge on unknown individuals, which may (or may not) be equal to entities from the data. These considerations motivated the extension of Datalog rules with existentially quantified variables in rule heads.

The existential rule framework

Formally, an existential rule is of the form R = ∀x∀y (B[x, y] → ∃z H[y, z]), where x, y and z are sets of variables, and B, H are conjunctions of atoms, also denoted by body(R) and head(R). The frontier of R is the set of variables shared between the body and the head of R, i.e., y. The existential variables in R are the existentially quantified variables, i.e., z.

We now consider knowledge bases of the form K = (F, R), where F is a fact base10 and R is a set of (pure) existential rules.

The logical translation of the BG-rules seen in the preceding section yields existential rules. For instance, the formula assigned to the BG-rule R from Figure 8 is Φ(R) = ∀x∀y((Student(x) ∧Course(y) ∧ takes(x, y)) → ∃z(TeachingStaff(z) ∧ teaches(z, y) ∧ teachesTo(z, x))), where the frontier is {x, y} (note that here all the variables from the body are frontier variables) and the only existential variable is z. Any conceptual graph KB of the form K = (S, F, R) can be translated into a logically equivalent existential rule KB of the form K = (F , R ), and reciprocally. In the following, we omit quantifiers in rules as there is no ambiguity.

Beside these "pure" existential rules, two other kinds of rules are generally considered in the framework: negative constraints, which are existential rules with a head restricted to ⊥, and equality rules, which are existential rules with a head restricted to an equality of the form e 1 = e 2 , where the e i are variables from the body or constants. These rules also correspond to constructs in the conceptual graph frame-work, namely negative BG-constraints and BG-rules with a conclusion restricted to two co-referent concept nodes.

Existential rules and classical description logics like ALC are incomparable with respect to expressivity. For instance, the ALC inclusions ∃coordinatorFor.Course Prof or the SHIQ transitivity axiom (Trans P) can be expressed by existential rules, but not the ALC inclusion Course UndergradCourse GradCourse which would require a disjunctive head, and the existential rule R from the previous example cannot be expressed in a description logic.

On the other hand, existential rules are strictly more expressive than so-called Horn description logics, which can be seen as DLs whose logical translation yield existential rules (in other words, the skolemisation of their logical translation yields Horn clauses with possibly functional symbols). The lightweight description logics EL and the DL-Lite dialects seen in Section 2 are examples of Horn description logics. Existential rules can be seen as overcoming two limitations of (Horn) description logics: first, predicates of any arity are allowed; second, there is no restriction on the atoms composing the body and the head of a rule, which allows one to describe complex relationships between entities (see e.g., the above rule R), whereas description logics are essentially limited to "acyclic" structures.

Relationships with database theory

An important connection with relational database theory has to be pointed out. Indeed, existential rules have the same logical form as Tuple-Generating Dependencies (TGDs), a high-level class of database constraints that generalize many constraints of practical database systems (and correspond to the CG positive constraints from the preceding section). Negative constraints are also considered in databases and equality rules (with equality between two variables) have the same logical form as the database Equality Generating Dependencies (EGDs), which generalize constraints on keys (see e.g., [START_REF] Abiteboul | Foundations of Databases[END_REF]). Note that, despite their syntactic correspondence, database constructs and rules have different roles: TGDs/EGDs act as constraints to check the consistency of a database instance, whereas rules act as ontological knowledge to generate new data. However, in the database setting, it is possible to repair constraint violations with respect to TGDs/EGDs by applying them in a forward chaining manner as if they were rules. This process, known as the chase, is considered as one of the fundamental tools in database theory. The similarities between the studied objects explain that many theoretical results obtained in one domain are actually of interest to the other. In particular, it has long been shown that the entailment of an atom from a set of TGDs (hence a set of pure existential rules) and a database instance is an undecidable problem when no restriction is made.

An existential rule R can be applied to a fact base F if there is a homomorphism h from body(R) to F, i.e., a substitution h of the variables in body(R) by terms in F such that h(body(R)) ⊆ F (both seen as sets of atoms). Applying R to F accord-ing to h consists in adding h(head(R)) to F, where h(head(R)) is obtained from H by substituting each frontier variable x by h(x) and safely renaming existential variables by fresh existential variables. The saturation of the fact base consists in iteratively applying rules on it until no rule application is possible. This process may of course not terminate since entailment is undecidable. Several forward chaining (or chase) variants have been defined, which differ in how they deal with the possible redundancies introduced by existential variables. It is well known that the (possibly infinite) saturation obtained by any of these chase variants forms a universal model of the knowledge base, i.e., a model that can be mapped by homomorphism to any other model of the KB. Hence, a universal model acts as a representative of all models of the KB, sufficient to decide conjunctive query entailment from the KB.

Decidability results

Interest in the existential rule framework gave rise to fruitful work on finding classes of existential rules for which (conjunctive) query answering is decidable. A wide range of rule classes offering various expressivity/tractability tradeoffs is now known (see e.g., [START_REF] Mugnier | Ontological query answering with existential rules[END_REF]Gottlob et al., 2012;[START_REF] Thomazo | Conjunctive Query Answering Under Existential Rules -Decidability, Complexity, and Algorithms[END_REF][START_REF] Mugnier | An introduction to ontology-based query answering with existential rules[END_REF] for syntheses). Most of these classes can be understood according to abstract properties that underlie decidability:

1. The set of rules R ensures that any KB K = (F, R) has a finite universal model.

In other words, some chase variant is guaranteed to halt on any fact base. Hence, for any (Boolean) CQ q, K |= q if and only if F * |= q, where F * is the saturation of F. Such sets of rules are called finite expansion sets (fes) [Baget et al., 2011a]. 2. The set of rules R ensures that any (Boolean) CQ q can be rewritten using the rules into a (finite) union of conjunctive queries Q such that for any KB K = (F, R) holds that K |= q if and only if F |= Q. Such sets of rules are called UCQ-rewritable or finite unification sets (fus) [Baget et al., 2011a]. More general forms of rewritings can be considered, such as first-order queries, which may produce a more succinct rewriting, or Datalog queries, which may provide a finite rewriting when there is no finite rewriting as a first-order query (see [START_REF] Gottlob | Rewriting ontological queries into small nonrecursive datalog programs[END_REF][START_REF] Bienvenu | Ontology-mediated queries: Combined complexity and succinctness of rewritings via circuit complexity[END_REF] among others). It is known that UCQrewritability and first-order rewritability are actually equivalent properties (e.g., [START_REF] Gottlob | The price of query rewriting in ontology-based data access[END_REF]). 3. The existence of a finite universal model may not be guaranted, but the set of rules R ensures that the saturation of any KB K = (F, R), seen as a graph, has a bounded treewidth. This allows for finite encodings of infinite saturations. Such sets of rules are called (greedy) bounded-treewidth sets ((g)bts) [Baget et al., 2011a,b;[START_REF] Thomazo | Conjunctive Query Answering Under Existential Rules -Decidability, Complexity, and Algorithms[END_REF].

The two first families of rules clearly enable one to come back to a classical database query answering problem: either the knowledge that can be entailed by the rules is encoded in the facts, or the relevant part of the rules is encoded in the query. In the third case, querying the finite encoding is more involved. Deciding whether a given set of rules satisfies one of these three abstract properties is undecidable, however each abstract property admits some "concrete" cases defined by recognizable syntactic criteria. Generalisations or combinations of these properties have been defined, however their presentation is outside the scope of this chapter.

Table 1 presents the main currently known concrete rule classes for which ontology-mediated conjunctive query answering has polynomial time data complexity. We chose to present the simplest classes, in order to highlight the fundamental ideas, even if most of these classes admit generalisations that often keep the same data complexity. The existence of a finite universal model (fes property) is ensured by some acyclicity conditions that prevent infinite creation of new variables during the chase. Such classes include range-restricted rules (i.e., Datalog rules), weaklyacyclic rules, and aGRD rules. These two last classes are both defined by an acyclicity condition on a directed graph, which encodes variables sharing between positions in predicates in the first case, and dependencies between rules in the second case. In the first graph, called position (dependency) graph [START_REF] Fagin | Data exchange: semantics and query answering[END_REF], the nodes represent all positions in predicates occurring in rules, i.e., the node (p,i) represents the position i in some predicate p. Then, for each rule R and each variable x in body(R) occurring in position (p, i), edges with origin (p, i) are built as follows: if x is a frontier variable, there is an edge from (p, i) to each position of x in head(R); furthermore, for each existential variable y in head(R) occurring in position (q, j), there is a special edge from (p, i) to (q, j). A set of rules is said to be weakly acyclic if its position graph has no circuit passing through a special edge. Intuitively, this condition ensures that the introduction of an existential variable in a given position can never lead to create another existential variable in the same position, hence an infinite number of existential variables.

For example, let R 1 = h(x) → p(x, y) and R 2 = p(u, v), q(v) → h(v). The position graph of {R 1 , R 2 } contains a special edge from (h, 1) to (p, 2) due to R 1 and an edge from (p, 2) to (h, 1) due to R 2 . Hence, {R 1 , R 2 } is not weakly-acyclic.

Range-restricted rules are a special case of weakly-acyclic rules since they do not have existential variables at all.

The second graph is called graph of rule dependencies (GRD) [Baget et al., 2011a;[START_REF] Grau | Acyclicity notions for existential rules and their application to query answering in ontologies[END_REF]. Intuitively, a rule R j depends on a rule R i if there is a fact base such that an application of R i on this fact base leads to a new application of R j . This abstract condition can be effectively computed by a specific unifier between the head of R i and the body of R j . The GRD of a set of rules R has a set of nodes in bijection with R and edges (R i , R j ) whenever the rule R j depends on the rule R i . A set of rules is aGRD if its GRD has no circuit. In the above example, R 1 depends on R 2 but not the contrary (indeed, one can check that an application of R 1 can never lead to trigger an application of R 2 : it produces an atom of the form p(x, y), where y is a new existential variable, but it does not produce the atom q(y), which on the other hand cannot exist in the fact base since y is new, hence no new application of R 2 is made possible); hence, {R 1 , R 2 } is aGRD. Weak-acyclicity and aGRD are in fact incomparable properties, but they admit common generalisations [START_REF] Grau | Acyclicity notions for existential rules and their application to query answering in ontologies[END_REF][START_REF] Rocher | Querying Existential Rule Knowledge Bases: Decidability and Complexity[END_REF].

The fus property is ensured by conditions that allow one to bound the maximal size of a non-redundant CQ generated during the rewriting. Concrete fus classes include in particular linear rules and sticky rules (these two classes being incomparable). A linear rule has a body restricted to a single atom. The stickiness of a set of rules is defined by a marking procedure of the variables occurring in rules; then the set of rules is said to be sticky if no marked variable in a rule body occurs in two different atoms; intuitively, this ensures that a variable generated during the rewriting process occurs in at most one atom [START_REF] Calì | Advanced processing for ontological queries[END_REF][START_REF] Thomazo | Conjunctive Query Answering Under Existential Rules -Decidability, Complexity, and Algorithms[END_REF]. The decidability of ontology-mediated query answering for sets of rules with the bts property comes from an indirect argument (following a result by Courcelle), which does not directly provide a suitable algorithm. However, the expressive subclass known as gbts allows one to greedily build a tree decomposition of the (possibly infinite) saturated fact base, such that this tree decomposition has a bounded width. Concrete rule classes in the gbts family are also known as the guarded family, inspired by the guarded fragment of first-order logic. We list here the main members of this family [START_REF] Calì | Taming the infinite chase: Query answering under expressive relational constraints[END_REF]Baget et al., 2011a]. A rule is guarded if an atom of its body (called a guard) contains all the variables that occur in its body. Note that a linear rule is by definition guarded, hence it is not only fus but also gbts. A rule is frontier-one if it has only one frontier variable. A rule is frontier-guarded if an atom of its body guards all the variables of its frontier (hence, this class generalizes both guarded and frontier-one rules).

Rule Class Data Complexity Datalog

PTime-c [START_REF] Dantsin | Complexity and expressive power of logic programming[END_REF]] weakly-acyclic PTime-c [START_REF] Dantsin | Complexity and expressive power of logic programming[END_REF](LB) [START_REF] Fagin | Data exchange: semantics and query answering[END_REF](UB) aGRD AC 0 (1) linear AC 0 [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF] (1) sticky AC 0 [START_REF] Calì | Advanced processing for ontological queries[END_REF] (1) guarded PTime-c [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF]] frontier-guarded PTime-c [START_REF] Baget | Walking the complexity lines for generalized guarded existential rules[END_REF] frontier-1

PTime-c [START_REF] Baget | Walking the complexity lines for generalized guarded existential rules[END_REF] (1) The AC 0 membership for data complexity follows from the FO-rewritability

Table 1 Fundamental classes of existential rules with polynomial-time data complexity Most Horn description logics belong to the gbts family, except those including transitivity, and more generally composition, of binary relations. Indeed, transitivity destroys the tree-like structure of the saturation. For instance, EL and ELHI are frontier-guarded, while DL-Lite R is linear (hence, also fus).

Conclusion

Reasoning with ontologies is becoming central in many data-centric applications for which ontologies are a way to integrate heterogeneous data by providing a common conceptual vocabulary. In this setting, it is crucial to deeply understand the impact of the ontological constructs on the complexity of the main reasoning problems. This chapter provides the required formal background and results to help data practitioners to choose the knowledge representation formalism with the best expressivity / complexity tradeoff regarding their application needs.

Ontology-mediated query answering is a vibrant area at the crossroads of several domains, namely data management, knowledge representation and reasoning, and the Semantic Web. Undoubtedly, many issues remain to be solved before the widespread adoption of the framework in practice. We will mention some of the challenges currently addressed in the area, without any claim to be exhaustive. Up to recently, most work were limited to conjunctive queries, or slight extensions of them, while the ability to process more complex queries is required. The combination of conjunctive queries and navigational queries has begun to be investigated (e.g., [START_REF] Stefanoni | The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases[END_REF]Bienvenu et al., 2015;[START_REF] Baget | Answering conjunctive regular path queries over guarded existential rules[END_REF]). New algorithmic techniques are being developed to meet the challenge of scalability beyond simple ontological languages (e.g., approaches that combine materialization of inferences and query rewriting [START_REF] Lutz | The combined approach to OBDA: taming role hierarchies using filters[END_REF][START_REF] Feier | The combined approach to query answering beyond the OWL 2 profiles[END_REF]). The integration of heterogeneous data under the form of a (possibly virtual) fact base relies on socalled mappings from these data to facts over the ontological vocabulary [START_REF] Poggi | Linking data to ontologies[END_REF]: while mappings are a classical notion in data integration, their introduction poses new challenges in the presence of an ontology (e.g., [START_REF] Bienvenu | Query-based comparison of mappings in ontology-based data access[END_REF][START_REF] Botoeva | Beyond OWL 2 QL in OBDA: rewritings and approximations[END_REF]). Representing and reasoning with temporal and spatial data, as well as information about their reliability and provenance, are of uttermost importance in most data-centric applications and have only recently begun to be explored in the context of ontology-mediated query answering [START_REF] Artale | First-order rewritability of temporal ontology-mediated queries[END_REF][START_REF] Borgwardt | Temporalizing rewritable query languages over knowledge bases[END_REF][START_REF] Bereta | Ontop of geospatial databases[END_REF][START_REF] Brandt | Ontology-based data access with a horn fragment of metric temporal logic[END_REF]. Last but not least, practically robust query answering has to be tolerant to data inconsistencies, which are likely to occur in large datasets especially when the data issues from multiple data sources (e.g., [START_REF] Lembo | Inconsistency-tolerant query answering in ontology-based data access[END_REF][START_REF] Lukasiewicz | From classical to consistent query answering under existential rules[END_REF][START_REF] Bienvenu | Inconsistency-tolerant querying of description logic knowledge bases[END_REF]).

Fig. 1

 1 Fig. 1 Example taxonomy of classes in the university domain

Fig. 2

 2 Fig. 2 Translation from DLs to first-order logic (1)

Fig. 3 Fig. 4

 34 Fig. 3 Translation from DLs to first-order logic (2) ∃teaches TeachingStaff ∃teaches -Course ∃coordinatorFor Prof ∃coordinatorFor -Course ∃takes Student ∃takes -Course coordinatorFor teaches

  is a finite set of relation symbols (or simply relations) of any arity, partially ordered by ≤, such that only relations with the same arity are comparable; • I is a possibly infinite set of elements called individual markers; furthermore, the symbol * denotes the generic marker, with * ∈ I. The set of all markers I ∪ { * } is partially ordered by ≤ as follows: for all m ∈ I, m ≤ * , and elements in I are pairwise incomparable. • T C , T R and I are pairwise disjoint sets.

  Fig. 5 A set of concept types

  Fig. 6 Basic Conceptual Graphs

Fig. 7

 7 Fig. 7 Relations and their signatures

  Fig. 8 Conceptual Graph Rule

•

  Ontological knowledge entailment: determine if a piece of ontological knowledge o is entailed by the ontology O, i.e., if O |= o holds. • Fact entailment: determine if a fact is entailed by the KB, i.e., if O, I |= o holds.

In the Semantic Web area, and specifically concerning the OWL language, the term ontology often includes both kinds of knowledge. Hence, it corresponds to our notion of knowledge base.

A few undecidable DLs have been studied.

http://www.snomed.org/snomed-ct

http://www.omg.org/uml

See http://owl.cs.manchester.ac.uk/tools/list-of-reasoners/ for an up-to-date list of DL reasoners.

http://www.lirmm.fr/cogui

http://cogitant.sourceforge.net

For query answering problems, the distinction between combined and data complexities is often made: data complexity is the complexity with respect to the size of the data (here the fact base), while combined complexity considers all components of the problem (here, the knowledge base and the query).

A fact is usually defined as a ground atom. However, in the existential rule setting, a more general notion of a fact can be considered, where a fact is an existentially closed conjunction of atoms, which is in line with the view of a fact as a rule with an empty body. This generalized notion allows one to encode unknown values in a natural way.