Knowledge Graphs

Ontologies

To enable entailment, we must be precise about what the terms we use mean. Returning to Figure 2.1, for example, and examining the node EID16 more closely, we may begin to question how it is modelled, particularly in comparison with EID15. Both nodes – according to the class hierarchy of Figure 3.1 – are considered to be events. But what if, for example, we wish to define two pairs of start and end dates for EID16 corresponding to the different venues? Should we rather consider what takes place in each venue as a different event? What then if an event has various start and end dates in a single venue: would these also be considered as one (recurring) event, or many events? These questions are facets of a more general question: what precisely do we mean by an “event”? Does it happen in one contiguous time interval or can it happen many times? Does it happen in one place or can it happen in multiple? There are no “correct” answers to such questions – we may understand the term “event” in a variety of ways, and thus the answers are a matter of convention.

In the context of computing, an ontology^{8note 8} The term stems from the philosophical study of ontology, concerning the kinds of entities that exist, the nature of their existence, what kinds of properties they have, and how they may be identified and categorised. is then a concrete, formal representation of what terms mean within the scope in which they are used (e.g., a given domain). For example, one event ontology may formally define that if an entity is an “event”, then it has precisely one venue and precisely one time instant in which it begins. Conversely, a different event ontology may define that an “event” can have multiple venues and multiple start times, etc. Each such ontology formally captures a particular perspective – a particular convention. Under the first ontology, for example, we could not call the Olympics an “event”, while under the second ontology we could. Likewise ontologies can guide how graph data are modelled. Under the first ontology we may split EID16 into two events. Under the second, we may elect to keep EID16 as one event with two venues. Ultimately, given that ontologies are formal representations, they can be used to automate entailment.

Like all conventions, the usefulness of an ontology depends on the level of agreement on what that ontology defines, how detailed it is, and how broadly and consistently it is adopted. Adoption of an ontology by the parties involved in one knowledge graph may lead to a consistent use of terms and consistent modelling in that knowledge graph. Agreement over multiple knowledge graphs will, in turn, enhance the interoperability of those knowledge graphs.

Amongst the most popular ontology languages used in practice are the Web Ontology Language (OWL) [Hitzler et al., 2012]^{9note 9} We could include RDF Schema (RDFS) in this list, but it is largely subsumed by OWL, which extends its core., recommended by the W3C and compatible with RDF graphs; and the Open Biomedical Ontologies Format (OBOF) [Mungall et al., 2012], used mostly in the biomedical domain. Since OWL is the more widely adopted, we focus on its features, though many similar features are found in both [Mungall et al., 2012]. Before introducing such features, however, we must discuss how graphs are to be interpreted.

Interpretations and models

We as humans may interpret the node Santiago in the data graph of Figure 2.1 as referring to the real-world city that is the capital of Chile. We may further interpret an edge Arica–flight➛Santiago as stating that there are flights from the city of Arica to this city. We thus interpret the data graph as another graph – what we here call the domain graph – composed of real-world entities connected by real-world relations. The process of interpretation, here, involves mapping the nodes and edges in the data graph to nodes and edges of the domain graph.

Along these lines, we can abstractly define an interpretation of a data graph as being composed of two elements: a domain graph, and a mapping from the terms (nodes and edge-labels) of the data graph to those of the domain graph. The domain graph follows the same model as the data graph; for example, if the data graph is a directed edge-labelled graph, then so too will be the domain graph. For simplicity, we will speak of directed edge-labelled graphs and refer to the nodes of the domain graph as entities, and to its edges as relations. Given a data graph and an interpretation, while we denote nodes in the data graph by Santiago, we will denote the entity it refers to in the domain graph by Santiago (per the mapping of the given interpretation). Likewise, while we denote an edge by Arica–flight➛Santiago, we will denote the relation by Arica–flightSantiago (again, per the mapping of the given interpretation). In this abstract notion of an interpretation, we do not require that Santiago or Arica be the real-world cities, nor even that the domain graph contain real-world entities and relations: an interpretation can have any domain graph and mapping.

Why is such an abstract notion of interpretation useful? The distinction between nodes/edges and entities/relations becomes important when we define the meaning of ontology features and entailment. To illustrate this distinction, if we ask whether there is an edge labelled flight between Arica and Viña del Mar for the data graph in Figure 2.1, the answer is no. However, if we ask if the entities Arica and Viña del Mar are connected by the relation flight, then the answer depends on what assumptions we make when interpreting the graph. Under the Closed World Assumption (CWA), if we do not have additional knowledge, then the answer is a definite no – since what is not known is assumed to be false. Conversely, under the Open World Assumption (OWA), we cannot be certain that this relation does not exist as this could be part of some knowledge not (yet) described by the graph. Likewise under the Unique Name Assumption (UNA), the data graph describes at least two flights to Santiago (since Viña del Mar and Arica are assumed to be different entities and, therefore, Arica–flightSantiago and Viña del Mar–flightSantiago must be different edges). Conversely, under No Unique Name Assumption (NUNA), we can only say that there is at least one such flight since Viña del Mar and Arica may be the same entity with two “names”.

These assumptions (or lack thereof) define which interpretations are valid, and which interpretations satisfy which data graphs. We call an interpretation that satisfies a data graph a model of that data graph. The UNA forbids interpretations that map two data terms to the same domain term. The NUNA allows such interpretations. Under the CWA, an interpretation that contains an edge x–py in its domain graph can only satisfy a data graph from which we can entail x–p➛y. Under the OWA, an interpretation containing the edge x–py can satisfy a data graph not entailing x–p➛y so long it does not explicitly contradict that edge. OWL adopts the NUNA and OWA, which is the most general case: multiple nodes/edge-labels in the graph may refer to the same entity/relation-type (per the NUNA), and anything not entailed by the data graph is not assumed to be false as a consequence (per the OWA).

Ontology features

Beyond our base assumptions, we can associate certain patterns in the data graph with semantic conditions that define which interpretations satisfy it; for example, we can add a semantic condition to enforce that if our data graph contains the edge p–subp. of➛q, then any edge x–py in the domain graph of the interpretation must also have a corresponding edge x–qy to satisfy the data graph. These semantic conditions then form the features of an ontology language. In what follows, to aid readability, we will introduce the features of OWL using an abstract graphical notation with abbreviated terms. For details of concrete syntaxes, we rather refer to the OWL and OBOF standards [Hitzler et al., 2012, Mungall et al., 2012]. Likewise we present semantic conditions over interpretations for each feature in the same graphical format;^{10note 10} We abbreviate “if and only if” as “iff” whereby “\(\phi\) iff \(\psi\)” can be read as “if \(\phi\) then \(\psi\)” and “if \(\psi\) then \(\phi\)”. further details of these conditions will be described later in Section 4.1.3.

Individuals

In Table 4.1, we list the main features supported by OWL for describing individuals (e.g., Santiago, EID16), sometimes distinguished from classes and properties. First, we can assert (binary) relations between individuals using edges such as Santa Lucía–city➛Santiago. In the condition column, when we write \(x\)–\(y\)\(z\), for example, we refer to the condition that the relation is given in the domain graph of the interpretation; if so, the interpretation satisfies the axiom. OWL further allows for defining relations to explicitly state that two terms refer to the same entity, where, e.g., Región V–same as➛Región de Valparaíso states that both refer to the same region (per Section 3.2); or that two terms refer to different entities, where, e.g., Valparaíso–diff. from➛Región de Valparaíso distinguishes the city from the region of the same name. We may also state that a relation does not hold using negation, which can be serialised as a graph using a form of reification (see Figure 3.8a).

Ontology features for individuals

Feature	Axiom	Condition	Example
Assertion	\(x\)–\(y\)➛\(z\)	\(x\)–\(y\)\(z\)	Chile–capital➛Santiago
Negation		not \(x\)–\(y\)\(z\)
Same As	\(x_1\)–same as➛\(x_2\)	\(x_1\) = \(x_2\)	Región V–same as➛Región de Valparaíso
Different From	\(x_1\)–diff. from➛\(x_2\)	\(x_1\) ≠ \(x_2\)	Valparaíso–diff. from➛Región de Valparaíso

Properties

In Section 3.1.1, we already discussed how sub-properties, domains and ranges may be defined for properties. OWL allows such definitions, and further includes other features, as listed in Table 4.2. We may define a pair of properties to be equivalent, inverses, or disjoint. We can further define a particular property to denote a transitive, symmetric, asymmetric, reflexive, or irreflexive relation. We can also define the multiplicity of the relation denoted by properties, based on being functional (many-to-one) or inverse-functional (one-to-many). We may further define a key for a class, denoting the set of properties whose values uniquely identify the entities of that class. Without adopting a Unique Name Assumption (UNA), from these latter three features we may conclude that two or more terms refer to the same entity. Finally, we can relate a property to a chain (a path expression only allowing concatenation of properties) such that pairs of entities related by the chain are also related by the given property. Note that for the latter two features in Table 4.2 we require representing a list, denoted with a vertical notation ⋮; while such a list may be serialised as a graph in a number of concrete ways, OWL uses RDF lists (see Figure 3.7).

Ontology features for property axioms

Feature	Axiom	Condition (for all \(x_*\), \(y_*\), \(z_*\))	Example
Sub-property	\(p\)–subp. of➛\(q\)	\(x\)–\(p\)\(y\) implies \(x\)–\(q\)\(y\)	venue–subp. of➛location
Domain	\(p\)–domain➛\(c\)	\(x\)–\(p\)\(y\) implies \(x\)–type\(c\)	venue–domain➛Event
Range	\(p\)–range➛\(c\)	\(x\)–\(p\)\(y\) implies \(y\)–type\(c\)	venue–range➛Venue
Equivalence	\(p\)–equiv. p.➛\(q\)	\(x\)–\(p\)\(y\) iff \(x\)–\(q\)\(y\)	start–equiv. p.➛begins
Inverse	\(p\)–inv. of➛\(q\)	\(x\)–\(p\)\(y\) iff \(y\)–\(q\)\(x\)	venue–inv. of➛hosts
Disjoint	\(p\)–disj. p.➛\(q\)	not	venue–disj. p.➛hosts
Transitive	\(p\)–type➛Transitive	\(x\)–\(p\)\(y\)–\(p\)\(z\)       implies \(x\)–\(p\)\(z\)	part of–type➛Transitive
Symmetric	\(p\)–type➛Symmetric	\(x\)–\(p\)\(y\) iff \(y\)–\(p\)\(x\)	nearby–type➛Symmetric
Asymmetric	\(p\)–type➛Asymmetric	not	capital–type➛Asymmetric
Reflexive	\(p\)–type➛Reflexive		part of–type➛Reflexive
Irreflexive	\(p\)–type➛Irreflexive	not	flight–type➛Irreflexive
Functional	\(p\)–type➛Functional	\(y_1\)\(p\)–\(x\)–\(p\)\(y_2\)       implies \(y_1\) = \(y_2\)	population–type➛Functional
Inv. Functional	\(p\)–type➛Inv. Functional	\(x_1\)–\(p\)\(y\)\(p\)–\(x_2\)       implies \(x_1\) = \(x_2\)	capital–type➛Inv. Functional
Key	\(c\)–key➛\(p_1\) ⋮ \(p_n\)	implies \(x_1\)=\(x_2\)	City–key➛lat long
Chain	\(p\)–chain➛\(q_1\) ⋮ \(q_n\)	\(x\)–\(q_1\)\(y_1\)–…\(y_{n-1}\)–\(q_n\)\(z\)       implies \(x\)–\(p\)\(z\)	location–chain➛location part of

Classes

In Section 3.1.1, we discussed how class hierarchies can be modelled using a sub-class relation. OWL supports sub-classes, and many additional features, for defining and making claims about classes; these additional features are summarised in Table 4.3. Given a pair of classes, OWL allows for defining that they are equivalent, or disjoint. Thereafter, OWL provides a variety of features for defining novel classes by applying set operators on other classes, or based on conditions that the properties of its instances satisfy. First, using set operators, one can define a novel class as the complement of another class, the union or intersection of a list (of arbitrary length) of other classes, or as an enumeration of all of its instances. Second, by placing restrictions on a particular property \(p\), one can define classes whose instances are all of the entities that have: some value from a given class on \(p\); all values from a given class on \(p\);^{11note 11} While something like flight➛prop–DomesticAirport–all➛NationalFlight might appear to be a more natural example for All Values, this would be problematic as the corresponding for all condition is satisfied when no such node exists, so we would infer anything known not to have any flights to be a domestic airport. (We could, however, define the intersection of such a definition and airport as being a domestic airport.) have a specific individual as a value on \(p\) (has value); have themselves as a reflexive value on \(p\) (has self); have at least, at most or exactly some number of values on \(p\) (cardinality); and have at least, at most or exactly some number of values on \(p\) from a given class (qualified cardinality). For the latter two cases, in Table 4.3, we use the notation “\(\#\{\)a\(\mid \phi \}\)” to count distinct entities satisfying \(\phi\) in the interpretation. These features can then be combined to create more complex classes, where combining the examples for Intersection and Has Self in Table 4.3 gives the definition: self-driving taxis are taxis having themselves as a driver.

Ontology features for class axioms and definitions

Feature	Axiom	Condition (for all \(x_*\), \(y_*\), \(z_*\))	Example
Sub-class	\(c\)–subc. of➛\(d\)	\(x\)–type\(c\) implies \(x\)–type\(d\)	City–subc. of➛Place
Equivalence	\(c\)–equiv. c.➛\(d\)	\(x\)–type\(c\) iff \(x\)–type\(d\)	Human–equiv. of➛Person
Disjoint	\(c\)–disj. c.➛\(d\)	not \(c\)type–\(x\)–type\(d\)	City–disj. c.➛Region
Complement	\(c\)–comp.➛\(d\)	\(x\)–type\(c\) iff not \(x\)–type\(d\)	Dead–comp.➛Alive
Union	\(c\)–union➛\(d_1\) ⋮ \(d_n\)	\(x\)–type\(c\) iff \(x\)–type\(d_1\) or \(x\)–type… or \(x\)–type\(d_n\)	Flight–union➛DomesticFlight InternationalFlight
Intersection	\(c\)–inter.➛\(d_1\) ⋮ \(d_n\)	\(x\)–type\(c\) iff	SelfDrivingTaxi–inter.➛Taxi SelfDriving
Enumeration	\(c\)–one of➛\(x_1\) ⋮ \(x_n\)	\(x\)–type\(c\) iff \(x\) \(\in \{\)\(x_1\)\(,\dots,\)\(x_n\)\(\}\)	EUState–one of➛Austria ⋮ Sweden
Some Values		\(x\)–type\(c\) iff there exists \(a\) such that \(x\)–\(p\)\(a\)–type\(d\)
All Values		\(x\)–type\(c\) iff for all \(a\) with \(x\)–\(p\)\(a\) it holds that \(a\)–type\(d\)
Has Value		\(x\)–type\(c\) iff \(x\)–\(p\)\(y\)
Has Self		\(x\)–type\(c\) iff \(x\)–\(p\)\(x\)
Cardinality \(\star \in \{ =, \leq, \geq \}\)		\(x\)–type\(c\)       iff \(\#\{\)a \(\mid\) \(x\)–\(p\)\(a\)\(\} \star n\)
Qualified Cardinality \(\star \in \{ =, \leq, \geq \}\)		\(x\)–type\(c\)       iff \(\#\{\)a \(\mid\) \(x\)–\(p\)\(a\)–type\(d\)\(\} \star n\)

Other features

OWL supports other language features not previously discussed, including: annotation properties, which provide metadata about ontologies, such as versioning info; datatype vs. object properties, which distinguish properties that take datatype values from those that do not; and datatype facets, which allow for defining new datatypes by applying restrictions to existing datatypes, such as to define that places in Chile must have a float between \(-66.0\) and \(-110.0\) as their value for the (datatype) property latitude. For more details we refer to the OWL 2 standard [Hitzler et al., 2012]. We will further discuss methodologies for the creation of ontologies in Section 6.5.

Models under semantic conditions

Each axiom described by the previous tables, when added to a graph, enforces some condition(s) on the models the graph. If we were to consider only the base condition of the Assertion feature in Table 4.1, for example, then the models of a graph would be any interpretation such that for every edge x–y➛z in the graph, there exists a relation x–yz in the model. Given that there may be other relations in the model (under the OWA), the number of models of any such graph is infinite. Furthermore, given that we can map multiple nodes in the graph to one entity in the model (under the NUNA), any interpretation with (for example) the relation a–aa is a model of any graph so long as for every edge x–y➛z in the graph, it holds that x = y = z = a in the interpretation (in other words, the interpretation maps everything to a). As we add axioms with their associated conditions to the graph, we restrict models for the graph; for example, considering a graph with two edges – x–y➛z and y–type➛Irreflexive – the interpretation with a–aa, x = y = … = a is no longer a model as it breaks the condition for the irreflexive axiom. In this way, we can define a precise model-theoretic semantics for graphs based on how the aforementioned ontological features used in the graph restrict the models of that graph.

Entailment

The conditions listed in the previous tables give rise to entailments, where, for example, in reference to the Symmetric feature of Table 4.2, the definition nearby–type➛Symmetric and edge Santiago–nearby➛Santiago Airport entail the edge Santiago Airport–nearby➛Santiago according to the condition given for that feature. We now describe how these conditions lead to entailments.

We say that one graph entails another if and only if any model of the former graph is also a model of the latter graph. Intuitively this means that the latter graph says nothing new over the former graph and thus holds as a logical consequence of the former graph. For example, consider the graph Santiago–type➛City–subc. of➛Place and the graph Santiago–type➛Place. All models of the latter must have that Santiago–typePlace, but so must all models of the former, which must have Santiago–typeCity–subc. ofPlace and further must satisfy the condition for Sub-class, which requires that Santiago–typePlace also hold. Hence we conclude that any model of the former graph must be a model of the latter graph, or, in other words, the former graph entails the latter graph.

If–then vs. if-and-only-if semantics

Consider the graph nearby–type➛Symmetric and the graph nearby–inv. of➛nearby. Both of these graphs result in the same semantic conditions being applied in the domain graph, but does one entail the other? The answer depends on the semantics applied. Considering the axioms and conditions of Tables 4.1, we can consider two semantics. Under if–then semantics – if Axiom matches the data graph then Condition holds in domain graph – the graphs do not entail each other: though both graphs give rise to the same condition, this condition is not translated back into the axioms that describe it.^{14note 14} Here, nearby–typeSymmetric is a model of the first graph but not the second, while nearby–inv. ofnearby is a model of the second graph but not the first. Hence neither graph entails the other. Conversely, under if-and-only-if semantics – Axiom matches data graph if-and-only-if Condition holds in domain graph – the graphs entail each other: both graphs give rise to the same condition, which is translated back into all possible axioms that describe it. Hence if-and-only-if semantics allows for entailing more axioms in the ontology language than if–then semantics. OWL generally applies an if-and-only-if semantics in order to enable richer entailments [Hitzler et al., 2012].

Reasoning

Unfortunately, given two graphs, deciding if the first entails the second – per the notion of entailment we have defined and for all of the ontological features listed in Tables 4.1–4.3 – is undecidable: no (finite) algorithm for such entailment can exist that halts on all inputs with the correct true/false answer [Hitzler et al., 2010]. However, we can provide practical reasoning algorithms for ontologies that (1) halt on any pair of input ontologies but may miss entailments, returning false instead of true in some cases, (2) always halt with the correct answer but only accept input ontologies with restricted features, or (3) only return correct answers for any pair of input ontologies but may never halt on certain inputs. Though option (3) has been explored using, e.g., theorem provers for First Order Logic (FOL) [Schneider and Sutcliffe, 2011], options (1) and (2) are more commonly pursued using rules and/or Description Logics. Option (1) generally allows for more efficient and scalable reasoning algorithms and is useful where data are incomplete and having some entailments is valuable. Option (2) may be a better choice in domains – such as medical ontologies – where missing entailments may have undesirable outcomes.

Rules

A straightforward way to provide automated access to the knowledge that can be deduced through (ontological or other forms of) entailments is through inference rules (or simply rules) encoding if–then-style consequences. A rule is composed of a body (if) and a head (then). Both the body and head are given as graph patterns. A rule indicates that if we can replace the variables of the body with terms from the data graph and form a sub-graph of a given data graph, then using the same replacement of variables in the head will yield a valid entailment. The head must typically use a subset of the variables appearing in the body to ensure that the conclusion leaves no variables unreplaced. Rules of this form correspond to (positive) Datalog [Ceri et al., 1989] in Databases, Horn clauses [Lloyd, 1984] in Logic Programming, etc.

Rules can capture entailments under ontological conditions. In Table 4.4, we list some example rules for sub-class, sub-property, domain and range features [Muñoz et al., 2009]; these rules may be considered incomplete, not capturing, for example, that every class is a sub-class of itself, that every property is a sub-property of itself, etc. A more comprehensive set of rules for the OWL features of Tables 4.1–4.3 have been defined as OWL 2 RL/RDF [Motik et al., 2012]; these rules are likewise incomplete as such rules cannot fully capture negation (e.g., Complement), existentials (e.g., Some Values), universals (e.g., All Values), or counting (e.g., Cardinality and Qualified Cardinality). Other rule languages have, however, been proposed to support additional such features, including existentials (see, e.g., Datalog\(^\pm\) [Bellomarini et al., 2018]), disjunction (see, e.g., Disjunctive Datalog [Rudolph et al., 2008]), etc.

Example rules for sub-class, sub-property, domain, and range features

Feature	Body	\(\Rightarrow\)	Head
Sub-class (I)	?x–type➛?c–subc. of➛?d	\(\Rightarrow\)	?x–type➛?d
Sub-class (II)	?d–subc. of➛?d–subc. of➛?e	\(\Rightarrow\)	?d–subc. of➛?e
Sub-property (I)		\(\Rightarrow\)	?x–?q➛?y
Sub-property (II)	?p–subp. of➛?q–subp. of➛?r	\(\Rightarrow\)	?p–subp. of➛?r
Domain		\(\Rightarrow\)	?x–type➛?c
Range		\(\Rightarrow\)	?y–type➛?c

Rules can be leveraged for reasoning in a number of ways. Materialisation refers to the idea of applying rules recursively to a graph, adding the conclusions generated back to the graph until a fixpoint is reached and nothing more can be added. The materialised graph can then be treated as any other graph. Although the efficiency and scalability of materialisation can be enhanced through optimisations like Rete networks [Forgy, 1982], or using distributed frameworks like MapReduce [Urbani et al., 2012], depending on the rules and the data, the materialised graph may become unfeasibly large to manage. Another strategy is to use rules for query rewriting, which given a query, will automatically extend the query in order to find solutions entailed by a set of rules; for example, taking the schema graph in Figure 3.2 and the rules in Table 4.4, the (sub-)pattern ?x–type➛Event in a given input query would be rewritten to the following disjunctive pattern evaluated on the original graph:

?x–type➛Event \(\cup\) ?x–type➛Type \(\cup\) ?x–type➛Periodic Market \(\cup\) ?x–venue➛?y

Figure 4.2 provides a more complete example of an ontology that is used to rewrite the query of Figure 4.1; if evaluated over the graph of Figure 2.1, Ñam will be returned as a solution. However, not all of the aforementioned features of OWL can be supported in this manner. The OWL 2 QL profile [Motik et al., 2012] is a subset of OWL designed specifically for query rewriting of this form [Artale et al., 2009].

While rules can be used to (partially) capture ontological entailments, they can also be defined independently of an ontology language, capturing entailments for a given domain. In fact, some rules – such as the following – cannot be captured by the ontology features previously seen, as they do not support ways to infer relations from cyclical graph patterns (for computability reasons):

\(\Rightarrow\) ?x–domestic flight➛?y

Various languages allow for expressing rules over graphs – independently or alongside of an ontology language – including: Notation3 (N3) [Berners-Lee and Connolly, 2011], Rule Interchange Format (RIF) [Kifer and Boley, 2013], Semantic Web Rule Language (SWRL) [Horrocks et al., 2004], and SPARQL Inferencing Notation (SPIN) [Knublauch et al., 2011], amongst others.

Description Logics

Description Logics (DLs) were initially introduced as a way to formalise the meaning of frames  and semantic networks . Since semantic networks are an early version of knowledge graphs, and DLs have heavily influenced the Web Ontology Language, DLs thus hold an important place in the logical formalisation of knowledge graphs. DLs form a family of logics rather than a particular logic. Initially, DLs were restricted fragments of FOL that permit decidable reasoning tasks, such as entailment checking [Baader et al., 2017]. Different DLs strike different balances between expressive power and computational complexity of reasoning. DLs were later extended with features beyond FOL that are useful in the context of modelling graph data, such as transitive closure, datatypes, etc.

DLs are based on three types of elements: individuals, such as Santiago; classes (aka concepts) such as City; and properties (aka roles) such as flight. DLs then allow for making claims, known as axioms, about these elements. Assertional axioms can be either unary class relations on individuals, such as City(Santiago), or binary property relations on individuals, such as flight(Santiago,Arica). Such axioms form the Assertional Box (A-Box). DLs further introduce logical symbols to allow for defining class axioms (forming the Terminology Box, or T-Box for short), and property axioms (forming the Role Box, R-Box); for example, the class axiom City \(\sqsubseteq\) Place states that the former class is a sub-class of the latter one, while the property axiom flight \(\sqsubseteq\) connectsTo states that the former property is a sub-property of the latter one. DLs may then introduce a rich set of logical symbols, not only for defining class and property axioms, but also defining new classes based on existing terms; as an example of the latter, we can define a class \(\exists\)nearby.Airport as the class of individuals that have some airport nearby. Noting that the symbol \(\top\) is used in DLs to denote the class of all individuals, we can then add a class axiom \(\exists\)flight.\(\top \sqsubseteq \exists\)nearby.Airport to state that individuals with an outgoing flight must have some airport nearby. Noting that the symbol \(\sqcup\) can be used in DL to define that a class is the union of other classes, we can further define, for example, that Airport \(\sqsubseteq\) DomesticAirport \(\sqcup\) InternationalAirport, i.e., that an airport is either a domestic airport or an international airport (or both).

The similarities between DL features and the OWL features seen previously are not coincidental: the OWL standard was heavily influenced by DLs, where, for example, the OWL 2 DL language is a fragment of OWL restricted so that entailment becomes decidable, where the restrictions are inspired by those defined for DLs. To exemplify a restriction, DomesticAirport \(\sqsubseteq ~=1\) destination \(\circ\) country.\(\top\) defines in DL syntax that domestic airports have flights destined to precisely one country (where p \(\circ\) q denotes a chain of properties). However, counting chains (in this case with \(=1~\texttt{destination} \circ \texttt{country}\)) is often disallowed in DLs to ensure decidability.

Expressive DLs support complex entailments involving existentials, universals, counting, etc. A common strategy for deciding such entailments is to reduce entailment to satisfiability, which decides if an ontology is consistent or not [Horrocks and Patel-Schneider, 2004].^{15note 15} \(G\) entails \(G'\) if and only if \(G \cup \text{not}(G')\) is not satisfiable, i.e., it has no model. Thereafter methods such as tableau can be used to check satisfiability, cautiously constructing models by completing them along similar lines to the materialisation strategy previously described, but additionally branching models in the case of disjunction, introducing new elements to represent existentials, etc. If any model is successfully “completed”, the process concludes that the original definitions are satisfiable (see, e.g., [Motik et al., 2009]). Due to their prohibitive computational complexity [Motik et al., 2012] – where for example, disjunction may lead to an exponential number of branching possibilities – such reasoning strategies are not typically applied in the case of large-scale data, though they may be useful when modelling complex domains for knowledge graphs.