=Paper=
{{Paper
|id=Vol-2954/paper-7
|storemode=property
|title=Geometric Models for (Temporally) Attributed Description Logics
|pdfUrl=https://ceur-ws.org/Vol-2954/paper-7.pdf
|volume=Vol-2954
|authors=Camille Bourgaux,Ana Ozaki,Jeff Z. Pan
|dblpUrl=https://dblp.org/rec/conf/dlog/BourgauxOP21
}}
==Geometric Models for (Temporally) Attributed Description Logics==
https://ceur-ws.org/Vol-2954/paper-7.pdf
Geometric Models for (Temporally) Attributed
Description Logics
Camille Bourgaux1 , Ana Ozaki2 , Jeff Z. Pan3
1
DI ENS, ENS, CNRS, PSL University & Inria, Paris, France
2
University of Bergen, Norway
3
University of Edinburgh, United Kingdom
Abstract. In the search for knowledge graph embeddings that could
capture ontological knowledge, geometric models of existential rules have
been recently introduced. It has been shown that convex geometric
regions capture the so-called quasi-chained rules. Attributed description
logics (DL) have been defined to bridge the gap between DL languages
and knowledge graphs, whose facts often come with various kinds of
annotations that may need to be taken into account for reasoning. In
particular, temporally attributed DLs are enriched by specific attributes
whose semantics allows for some temporal reasoning. Considering that
geometric models and (temporally) attributed DLs are promising tools
designed for knowledge graphs, this paper investigates their compatibility,
focusing on the attributed version of a Horn dialect of the DL-Lite family.
We first adapt the definition of geometric models to attributed DLs and
show that every satisfiable ontology has a convex geometric model. Our
second contribution is a study of the impact of temporal attributes. We
show that a temporally attributed DL may not have a convex geometric
model in general but we can recover geometric satisfiability by imposing
some restrictions on the use of the temporal attributes.
1 Introduction
Knowledge graph embeddings are popular latent representations of knowledge
graphs (KG). In the search for KG embeddings that could capture ontological
knowledge (i.e., schema of KG), geometric models of existential rules have been
recently introduced [14]. Such models have several advantages. Notably, they
ensure that facts which are valid in the embedding are logically consistent and
deductively closed w.r.t. the ontology, and they can also be used to find plausible
missing ontology rules. It has been shown that convex geometric regions capture
the so-called quasi-chained rules, a fragment of first-order Horn logic. Attributed
description logics (DL) have been defined to bridge the gap between DL ontology
Copyright © 2021 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
languages and KG, whose facts often come with various kinds of annotations
that may need to be taken into account for reasoning. In particular, they were
introduced as a formalism for dealing with the meta-knowledge present in KG,
such as temporal validity, provenance, language, and others [17, 18, 8]. As time
is of primary interest in KG, attributed DLs have been enriched with temporal
attributes, whose semantics allows for some temporal reasoning over discrete
time [23]. Considering that geometric models and (temporally) attributed DLs
are promising tools designed for KG, this paper investigates their compatibility,
focusing on the attributed version of a Horn dialect of the DL-Lite family.
Our contributions are as follows:
– We adapt the notion of geometric models for ((temporally) attributed) DLs; in
particular, we use an arbitrary linear map to combine the individual geometric
interpretations instead of restricting ourselves to vector concatenation, and
define satisfaction of concept or role inclusions directly based on geometric
inclusion relationship between the regions that interpret the concepts or roles.
– We show that every satisfiable attributed DL-LiteH horn ontology has a convex
geometric model but there are satisfiable temporally attributed DL-LiteH horn
ontologies without such a model.
– We exhibit restrictions on the use of temporal attributes that guarantee that
temporally attributed DL-LiteH horn ontologies have a convex geometric model.
We define attributed DLs and geometric models in Section 2. Then, in
Section 3, we study the relationship between satisfiability and the existence
of convex geometric models in DL-LiteH horn . We then extend our analysis for
temporally attributed DL-LiteH
horn in Section 4. In Section 5, we discuss related
works and we conclude in Section 6. Omitted proofs are given in [9].
2 Geometric Models for Attributed Description Logics
In this section, we recall the framework of attributed DLs and define geometric
models in this context.
2.1 Attributed DLs
We introduce attributed DLs by defining attributed DL-Lite [8], focusing on the
DL-LiteH horn dialect. The notions presented here can be easily adapted to other
attributed DLs, e.g. EL, as in [17, 18]. Let NC , NR , and NI be countably infinite
and mutually disjoint sets of concept, role, and individual names. We assume that
NI is divided into two sets, called Ni and Na , and we refer to the elements in Na
as annotation names. We consider an additional set NU of set variables and a set
NV of object variables. The set S of specifiers contains the following expressions:
– set variables X ∈ NU ;
– closed specifiers [a1 : v1 , . . . , an : vn ]; and
– open specifiers ba1 : v1 , . . . , an : vn c,
where ai ∈ Na and vi is either an individual name in Na , an object variable in
NV , or an expression of the form X.a, with X a set variable in NU and a an
individual name in Na . We use X.a to refer to the (finite, possibly empty) set of
all values of attribute a in an annotation set X. A ground specifier is a closed or
open specifier built only over Na .
Syntax. A DL-LiteH,@ horn concept (resp. role) assertion is an expression A(a)@S
(resp. R(a, b)@S), with A ∈ NC (resp. R ∈ NR ), a, b ∈ Ni , and S ∈ S a ground
closed specifier. A DL-LiteH,@
horn role inclusion is an expression of the form:
X :S (P v Q), (1)
where S ∈ S is a closed or open specifier, X ∈ NU is a set variable, and P, Q are
role expressions built according to the following syntax:
P := R@S | R− @S, Q := P | ¬P (2)
with S ∈ S, R ∈ NR . A DL-LiteH,@
horn concept inclusion is of the form:
k
l
X1 : S1 , . . . , Xn : Sn ( Bi v C), (3)
i=1
where k, n ≥ 1, S1 , . . . , Sn ∈ S are closed or open specifiers, X1 , . . . , Xn ∈ NU
are set variables, and Bi , C are concept expressions built according to:
B := A@S | ∃P, C := B | ⊥, (4)
where P is as in Equation (2), A ∈ NC and S ∈ S. Role expressions of the form
P are called roles and concept expression of the form B are basic concepts. We
further require that all object variables are safe, that is, if they occur on the right
side of a concept/role inclusion or in a specifier associated with a set variable
occurring on the right side then they must also occur on the left side of the
inclusion (or in a specifier associated with a set variable occurring on the left).
A DL-LiteH,@ H,@
horn ontology is a set of DL-Litehorn assertions, role and concept
inclusions. We say that an inclusion is positive if it does not contain negation
or ⊥. Also, we say that a DL-LiteH,@ horn ontology is ground if it does not contain
variables. To simplify notation, we omit the specifier bc (meaning “any annotation
set”) in role or concept expressions. In this sense, any DL-LiteH horn axiom is also
a DL-LiteH,@
horn axiom. Moreover, we omit prefixes of the form X : b c, which state
that there is no restriction on X.
Semantics. An interpretation I = (∆Ii , ∆Ia , ·I ) of an attributed DL consists of
a non-empty domain ∆Ii of individuals, a non-empty domain ∆Ia of annotations,
and a function ·I . Individual names a ∈ Ni are interpreted as elements aI ∈ ∆Ii
and individual names a ∈ Na are interpreted as elements aI ∈ ∆Ia . To interpret
annotation sets, we use the set ΦI := {Σ ⊆ ∆Ia × ∆Ia | Σ is finite} of all
finite binary relations over ∆Ia . Each concept name A ∈ NC is interpreted
as a set AI ⊆ ∆Ii × ΦI of elements with annotations, and each role name
R ∈ NR is interpreted as a set RI ⊆ ∆Ii × ∆Ii × ΦI of pairs of elements
with annotations. Each element (pair of elements) may appear with multiple
different annotations. I satisfies a concept assertion A(a)@[a1 : v1 , . . . , an : vn ] if
(aI , {(aI1 , v1I ), . . . , (aIn , vnI )}) ∈ AI . Role assertions are interpreted analogously.
Expressions with free set or object variables are interpreted using variable
assignments Z mapping object variables x ∈ NV to elements Z(x) ∈ ∆Ia and
set variables X ∈ NU to finite binary relations Z(X) ∈ ΦI . For convenience,
we also extend variable assignments to individual names, setting Z(a) = aI for
every a ∈ Na . A specifier S ∈ S is interpreted as a set S I,Z ⊆ ΦI of matching
annotation sets. We set X I,Z := {Z(X)} for variables X ∈ NU . The semantics of
closed specifiers is defined as:
– [a: v]I,Z := {{(aI , Z(v))}} where v ∈ Na ∪ NV ;
– [a: X.b]I,Z := {{(aI , δ) | (bS I
, δ) ∈ Z(X)}};
– [a1 : v1 , . . . , an : vn ]I,Z := { ni=1 Fi } where {Fi } = [ai : vi ]I,Z for all 1 ≤ i ≤ n.
S I,Z therefore is a singleton set for variables and closed specifiers. For open
specifiers, however, we define ba1 : v1 , . . . , an : vn cI,Z to be the set:
{F ⊆ ΦI | F ⊇ G for {G} = [a1 : v1 , . . . , an : vn ]I,Z }.
Now given A ∈ NC , R ∈ NR , and S ∈ S, we define:
(A@S)I,Z := {δ | (δ, F ) ∈ AI for some F ∈ S I,Z },
(R@S)I,Z := {(δ, ) | (δ, , F ) ∈ RI for some F ∈ S I,Z }.
Further DL expressions are defined as: (R− @S)I,Z := {(γ, δ) | (δ, γ) ∈ (R@S)I,Z },
¬P I,Z := (∆Ii ×∆Ii )\P I,Z , ∃P I,Z := {δ | there is (δ, ) ∈ P I,Z }, (B1 uB2 )I,Z :=
B1I,Z ∩ B2I,Z , ⊥I,Z := ∅. I satisfies a concept inclusion of the form (3) if, for
all variable assignments Z that satisfy Z(Xi ) ∈ SiI,Z for all 1 ≤ i ≤ n, we have
dk
( i=1 Bi )I,Z ⊆ C I,Z . Satisfaction of role inclusions is defined analogously. An
interpretation I satisfies an ontology O, or is a model of O, if it satisfies all of
its axioms. As usual, |= denotes the induced logical entailment relation.
For ground specifiers {S, T } ⊆ S, we write S ⇒ T if T is an open specifier, and
the set of attribute-value pairs a : b in S is a superset of the set of attribute-value
pairs in T .
2.2 Geometric Models
We now define the geometric interpretations of attributed relations. Let m be an
integer and f : Rm × Rm 7→ R2·m be a fixed but arbitrary linear map satisfying
the following:
(i) the restriction of f to Rm × {0}m is injective;
(ii) the restriction of f to {0}m × Rm is injective;
(iii) f (Rm × {0}m ) ∩ f ({0}m × Rm ) = {02·m };
where 0m denotes the vector (0, . . . , 0) with m zeros. Intuitively, individuals will
be interpreted as vectors from Rm and f will be used to combine two vectors to
interpret pairs of individuals.
Definition 1 (Geometric Interpretation). An m-dimensional f -geometric
interpretation η of (NC , NR , Ni , Na ) assigns
– to each A ∈ NC and ground S ∈ S a region η(A@S) ⊆ Rm ,
– to each R ∈ NR and ground S ∈ S a region η(R@S) ⊆ R2·m , and
– to each a ∈ Ni a vector η(a) ∈ Rm .
Moreover, for all {S, T } ⊆ S and E ∈ NC ∪ NR , if S ⇒ T then η(E@S) ⊆
η(E@T ). We say that η is convex if, for every E ∈ NC ∪ NR , every ground
S ∈ S, every v 1 , v 2 ∈ η(E@S), and every λ ∈ [0, 1], if v 1 , v 2 ∈ η(E@S) then
(1 − λ)v 1 + λv 2 ∈ η(E@S).
The interpretation of ground complex concept or role expressions is as follows.
Assume all specifiers occurring in expressions below are ground, R ∈ NR , P is a
role, and B, Bi are basic concepts. Then,
– η(R− @S) := {f (δ, δ 0 ) | f (δ 0 , δ) ∈ η(R@S)},
– η(¬P ) := R2·m \ η(P ),
0 0
dn) := {δ | ∃δ
– η(∃P Tn, f (δ, δ ) ∈ η(P )},
– η( i=1 Bi ) := i=1 η(Bi ),
– η(⊥) := ∅.
We may omit “of (NC , NR , Ni , Na )” when we speak about m-dimensional f -
geometric interpretations. The interest of geometric interpretations is that concept
and role assertions translate into membership in geometric regions and ground
concept or role inclusions translate into geometric inclusions.
Definition 2 (Satisfaction of Ground Axioms). An m-dimensional f -geometric
interpretation η satisfies
– a concept assertion A(a)@S, denoted η |= A(a)@S, if η(a) ∈ η(A@S);
– a role assertion R(a, b)@S, denoted η |= R(a, b)@S, if f (η(a), η(b)) ∈ η(R@S);
– a ground role inclusion P v d Q, denoted η |= P v Q, if η(Pdn) ⊆ η(Q);
n
– a ground concept
dn inclusion B
i=1 i v C, denoted η |= i=1 Bi v C, if we
have that η( i=1 Bi ) ⊆ η(C).
We are ready for the first theorem which establishes that our more general
notion of geometric models still has the same properties of the geometric models
originally proposed [14].
Theorem 3. Let η be an m-dimensional f -geometric interpretation. For every
linear map f 0 satisfying (i)-(iii), the m-dimensional f 0 -geometric interpretation
η 0 defined as:
– η 0 (a) := η(a), for all a ∈ Ni ;
– η 0 (A@S) := η(A@S), for all A ∈ NC and ground S ∈ S; and
– η 0 (R@S) := {f 0 (δ, δ 0 ) | f (δ, δ 0 ) ∈ η(R@S)}, for all R ∈ NR and ground S ∈ S;
is such that η |= α iff η 0 |= α, for all ground axioms α.
Proof (Sketch). This result follows from the fact that there is an isomorphism
between the regions in η and η 0 .
To define when a geometric interpretation is a model of a (possibly not
ground) DL-LiteH,@horn ontology, we need to define when such an interpretation
satisfies non-ground concept or role inclusions. To do so, we use a standard
interpretation built from the geometric interpretation. Given a ground specifier
S and an annotation name ?, we define FS? = {(a, b) | a: b occurs in S} ∪ {(?, ?) |
if S is open}. Given an m-dimensional f -geometric interpretation η, a subset Da
of Na and an annotation name ? ∈ Na \ Da , we define an interpretation I(η, Da? )
as follows.
I(η,D ? ) ?
– ∆i a
= Rm and, for all a ∈ Ni , aI(η,Da ) = η(a);
I(η,Da? ) ?
– ∆a = Na and for all a ∈ Na , aI(η,Da ) = a;
?
– AI(η,Da ) = {(δ, FS? ) | δ ∈ η(A@S), S built on Da }, for all A ∈ NC ;
?
– RI(η,Da ) = {(δ, , FS? ) | f (δ, ) ∈ η(R@S), S built on Da }, for all R ∈ NR .
The next proposition shows that η and I(η, Da? ) satisfy the same ground
axioms built using only annotation names from Da . It follows in particular that
η satisfies all ground axioms of an ontology O iff I(η, N ?O ) does, where N O is the
set of annotation names from Na that occur in O.
Theorem 4. Let η be an m-dimensional f -geometric interpretation. Let α be a
ground axiom, i.e., α is either a concept/role assertion or a ground concept/role
inclusion. Let Dα be the set of annotation names that occur in α and let D be a
subset of Na such that Dα ⊆ D. Let ? be an annotation name that does not occur
in D. Then, the following holds: η |= α iff I(η, D? ) |= α.
Proof (Sketch). The proof relies heavily on the definition of FS? and the require-
ment that η(E@S) ⊆ η(E@T ) when S ⇒ T in Definition 1.
We are now ready to define geometric models of DL-LiteH,@
horn ontologies.
Definition 5 (Geometric Model). Let O be a DL-LiteH,@ horn ontology, and let
N O be the set of annotation names from Na that occur in O and ? an annotation
name that does not occur in O. An m-dimensional f -geometric interpretation η
is a model of O if I(η, N ?O ) is a model of O.
3 Satisfiability and Convex Geometric Models
We start by recalling some definitions and results on geometric interpretations of
an ontology containing existential rules [14]. An existential rule is an expression of
the form B1 ∧ · · · ∧ Bn → ∃X1 , . . . , Xj .H where n ≥ 0, the Bi ’s and H are atoms
built from sets of predicates, constants and variables, and the Xi ’s are variables.
A negative constraint is a rule whose head is ⊥. An existential rule or negative
constraint is quasi-chained if for all 1 ≤ i ≤ n, |(vars(B1 ) ∪ · · · ∪ vars(Bi−1 )) ∩
vars(Bi )| ≤ 1, where vars(B) denotes the variables that occur in B. It is easy to
see that a DL-LiteH horn ontology without negative role inclusions can be translated
into a quasi-chained ontology. Negative role inclusions are not quasi-chained:
their translation to rules is indeed of the form P1 (x, y) ∧ P2 (x, y) → ⊥ where
the body atoms share two variables. A (standard) model M of an existential
rules ontology K is a set of facts that contains all facts from K and satisfies all
existential rules from K. In this setting, for every fact α, α ∈ M iff M |= α.
Given a set R of relation names and a set X of constants and labelled nulls, a
m-dimensional geometric interpretation η of (R, X) assigns to each k-ary relation
R from R a region η(R) ⊆ Rk.m and to each object o from X a vector η(o) ∈ Rm .
Tuples of individuals are interpreted using vectors concatenation, which plays
the role of the linear map f we use to interpret a pair of individuals: for every
R ∈ R and o1 , . . . , ok ∈ X, η |= R(o1 , . . . , ok ) if η(o1 ) ⊕ · · · ⊕ η(ok ) ∈ η(R). The
authors define
Φ(η) = {R(o1 , . . . , ok ) | R ∈ R, o1 , . . . , ok ∈ X, η |= R(o1 , . . . , ok )}.
Proposition 3 in [14] states that if K is a quasi-chained ontology and M is a
finite model of K, then K has a convex geometric model η such that Φ(η) = M.
This transfers to the DL setting as follows. Let O be a quasi-chained DL ontology
and J be a finite model of O such that ∆J = Ni , and aJ = a for every a ∈ Ni
(which implies that for every concept A, if δ ∈ AJ , then J |= A(δ), and similarly
for roles). Then O has a convex geometric model η such that
{E(t) | η |= E(t)} = {E(t) | J |= E(t)},
where E ∈ NC ∪ NR and t is a tuple with the arity of E. In the following, we may
similarly write E(t)@S to refer to an atom of the form A(a)@S or R(a, b)@S.
Theorem 6. Let O be a satisfiable DL-LiteH,@horn ontology without negative role
inclusions. O has a convex geometric model.
Proof (Sketch). We use grounding to translate O into an equisatisfiable DL-
LiteH
horn ontology. Since O does not contain negative role inclusion, the obtained
DL-LiteHhorn ontology is quasi-chained. We can thus apply the result by Gutiérrez-
Basulto and Schockaert [14] to get a convex m-dimensional f -geometric model
with f being vector concatenation. This geometric model is used to construct a
geometric model of O.
4 Adding Time
In this section, we discuss the ability of convex geometric models to capture
temporally attributed DLs. We show that we need to restrict the expressivity of
the temporal ontology to get a convex geometric model.
We introduce temporally attributed DLs by defining temporally attributed
H,T,@ H,T,@
DL-LiteH horn , called DL-Litehorn , as in [23]. The description logic DL-Litehorn is
H,@
defined as a multi-sorted version of DL-Litehorn , where time points and intervals
are seen as datatypes. Time points are elements of NT , and time intervals are
elements of N2T . These sets and the set of (abstract) individual names NI are
mutually disjoint. Time points are represented in a discrete manner by natural
numbers, and we assume that elements of NT (N2T ) are (pairs of) numbers. A
pair of numbers k, ` in N2T is denoted [k, `].
The annotation names: time, before, after, until, since, during, between ∈ Na are
called temporal attributes and have their own semantics. Basically, time is used to
mark a point in time and before and after refer to some point in the past and in
the future, respectively. The temporal attributes until and since refer to all points
in the past and all point in the future (e.g. since 2020 the KR conference became
an annual event). Finally, during is an interval which represents a period of time
(it refers to all points in the interval) and between is an interval of uncertainty
for when an event happened. The value type of time, before, after, until, since is
NT , while the value type of during, between is N2T . We write valtype(a) to refer to
the value type of the annotation name a. Object variables are now taken from
pairwise disjoint sets Var(Na ), Var(NT ), and Var(N2T ).
Annotation set specifiers are defined as in Section 2.1 with the difference that
for each ai ∈ Na and each vi in attribute value pair ai : vi we require compatibility
between the value type of its attribute, that is:
– vi ∈ valtype(ai ) ∪ Var(valtype(ai )), or
– vi = [v, w] with valtype(ai ) = N2T and v, w in NT ∪ Var(NT ), or
– vi = X.b with X ∈ NU , b ∈ Na , and valtype(ai ) = valtype(b).
A time-sorted interpretation I = (∆Ii , ∆Ia , ·I ) is an interpretation with a
domain ∆Ia that is a disjoint union of ∆IA ∪ ∆IT ∪ ∆I2T , where ∆IA is the abstract
domain of annotations, ∆IT (the temporal domain) is a finite or infinite interval,
and ∆I2T = ∆IT × ∆IT . We interpret individual names in Ni as elements in ∆Ii ;
annotation names in Na as elements in ∆IA ; time points t ∈ NT as tI ∈ ∆IT ;
and intervals [t, t0 ] ∈ N2T as [t, t0 ]I = (tI , t0I ) ∈ ∆I2T . A pair (δ, ) ∈ ∆IA × ∆Ia is
well-typed, if:
1. δ = aI for an attribute ‘a’ of value type NT and ∈ ∆IT ; or
2. δ = aI for an attribute ‘a’ of value type N2T and ∈ ∆I2T ; or
3. δ = aI for an attribute ‘a’ of value type Na and ∈ ∆IA .
Let ΦI be the set of all finite sets of well-typed pairs. The function ·I maps concept
names A ∈ NC to AI ⊆ ∆Ii × ΦI and role names R ∈ NR to RI ⊆ ∆Ii × ∆Ii × ΦI .
The semantics of terms is given by variable assignments, which for a time-sorted
interpretation I is defined as a function Z that maps
– set variables X ∈ NU to finite binary relations Z(X) ∈ ΦI , and
– object variables x ∈ Var(NI ) ∪ Var(NT ) ∪ Var(N2T ) to elements Z(x) ∈ ∆II ∪
∆IT ∪ ∆I2T (respecting their types).
For (set or object) variables x, we define xI,Z := Z(x), and for abstract indi-
viduals, time points, or time intervals a, we define aI,Z := aI . The semantics
of specifiers is as in Section 2.1 with the difference that values can also be time
points and intervals:
– [a: v]I,Z := {{(aI , v I,Z )}}, with v ∈ valtype(a) ∪ Var(valtype(a));
– [a: [v, w]]I,Z := {{(aI , (v I,Z , wI,Z ))}}, with valtype(a) = N2T , and v, w ∈
NT ∪ Var(NT ).
We are now ready to formally define the semantics of temporal attributes.
Definition 7. Consider a temporal domain ∆IT and a domain ∆Ii of individuals
and a domain ∆Ia of annotations, and let (Ii )i∈∆IT be a sequence of (non-temporal)
interpretations with domains ∆Ii and ∆Ia , such that, for all a ∈ NI , we have
aIi = aIj for all i, j ∈ ∆IT . We define a global interpretation for (Ii )i∈∆IT as
a time-sorted interpretation I = (∆Ii , ∆Ia , ·I ) as follows. Let aI = aIi for all
a ∈ NI . For any finite set F ∈ ΦI , let FI := F ∩ (∆IA × ∆IA ) denote its abstract
part without any temporal attributes. For any A ∈ NC , δ ∈ ∆Ii , and F ∈ ΦI with
F \ FI 6= ∅, we have (δ, F ) ∈ AI if and only if (δ, FI ) ∈ AIi for some i ∈ ∆IT ,
and the following conditions hold for all (aI , x) ∈ F :
– if a = time, then (δ, FI ) ∈ AIx ,
– if a = before, then (δ, FI ) ∈ AIj for some j < x,
– if a = after, then (δ, FI ) ∈ AIj for some j > x,
– if a = until, then (δ, FI ) ∈ AIj for all j ≤ x,
– if a = since, then (δ, FI ) ∈ AIj for all j ≥ x,
– if a = between, then (δ, FI ) ∈ AIj for some j ∈ [x],
– if a = during, then (δ, FI ) ∈ AIj for all j ∈ [x],
where [x] for an element x ∈ ∆I2T denotes the finite interval represented by the
pair of numbers x, and j ∈ ∆IT . For roles R ∈ NR , we define (δ, , F ) ∈ RI
analogously.
Definition 8 (Temporal Geometric Interpretation). A temporal m-
dimensional f -geometric interpretation with temporal domain ∆T is a sequence
(ηj )j∈∆T of m-dimensional f -geometric interpretations. An m-dimensional f -
geometric interpretation η is global for (ηj )j∈∆T and Da ⊆ Na if I(η, (Da ∪ NT ∪
N2T )? ) is global for (I(ηj , Da? ))j∈∆T .
Let N O denote the union of all elements in Na , NT , and N2T occurring in O.
Definition 9 (Geometric Model). Let O be a DL-LiteH,T,@ horn ontology. An
f -geometric interpretation η is an m-dimensional f -geometric model of O if it is
global for a sequence (ηj )j∈∆T of m-dimensional f -geometric interpretations and
N O , plus I(η, N ?O ) satisfies O.
Example 10 shows that even if temporal specifiers are only of the form time
and during, convex geometric models may not exist for satisfiable DL-LiteH,T,@
horn
ontologies.
Example 10. Let
O ={∃R@[during: [1, 2]] v A, ∃R@[time: 1] u A v ⊥,
R(a, a)@[time: 1], R(b, b)@[time: 1], R(a, b)@[time: 2], R(b, a)@[time: 2]}
and let η be a convex f -geometric model of O. Let δ = 0.5η(a) + 0.5η(b). By the
convexity of η(R@[time: 1]) and η(R@[time: 2]), we have that
f (δ, δ) ∈ η(R@[time: 1]) and f (δ, δ) ∈ η(R@[time: 2]),
so I(η, N ?O ) |= R(δ, δ)@[time: 1] and I(η, N ?O ) |= R(δ, δ)@[time: 2]. It follows that
I(η, N ?O ) |= R(δ, δ)@[during: [1, 2]]. Since I(η, N ?O ) |= R@[during: [1, 2]] v A, we
also have that I(η, N ?O ) |= A(δ). Hence I(η, N ?O ) 6|= ∃R@[time: 1] u A v ⊥. This
means that I(η, N ?O ) is not a model of O. /
To overcome this problem, we introduce a restriction on the specifiers allowed
on roles. We introduce atemporal specifiers. An atemporal specifier is a specifier
S that can only be interpreted as a set S I,Z ⊆ ΦI of matching annotation sets
that do not contain any temporal attribute.
To show that convex geometric models can capture some DL-LiteH,T,@ horn on-
tologies, we use concept inclusions with conjunctions on the left-hand side, which
can be expressed in DL-LiteH horn . The following example shows that adding con-
junction in role inclusions may however lead to satisfiable ontologies not having
a convex model, even for plain DLs.
Example 11. Assume role conjunctions are allowed in the ontology. Let
O = {R1 u R2 v R3 , ∃R1 v A, ∃R3 u A v ⊥, R1 (a, a), R1 (b, b), R2 (a, b), R2 (b, a)}
and let η be a convex f -geometric model of O. Let δ = 0.5η(a) + 0.5η(b). By the
convexity of η(R1 ) and η(R2 ), we have that
f (δ, δ) ∈ η(R1 ) and f (δ, δ) ∈ η(R2 ), hence f (δ, δ) ∈ η(R1 u R2 ).
Then since η is a model of R1 uR2 v R3 , f (δ, δ) ∈ η(R3 ) so δ ∈ η(∃R3 ). Moreover,
since η is a model of ∃R1 v A, and δ ∈ η(∃R1 ), δ ∈ η(A). Hence η 6|= ∃R3 uA v ⊥
so η is not a model of O. /
We now state the main result of this section, which states that, under certain
conditions, satisfiable DL-LiteH,T,@
horn ontologies have a convex geometric model.
The need of Condition (i) is already illustrated by Example 10 whereas Condition
(ii) ensures that the underlying logic is Horn (that is, it does not have disjunctions
which can be expressed with the temporal attributes before, after and between).
Theorem 12. Let O be a satisfiable DL-LiteH,T,@horn ontology without negative role
inclusions and such that (i) all specifiers attached to a role in O are atemporal,
and (ii) before, after and between do not occur in O. Then O has a convex
geometric model.
5 Related Work
Traditionally, most KG embedding models are time-unaware. These models
embed both entities and relations in a low-dimensional latent space based on some
regularities of target KG. They can be used as approximate reasoning methods [25,
24] for completing KG without using the schema. Typical embedding models
include the translation based models, such as TransE [7] and bilinear models, such
as ComplEx [29] and SimplE [16]. From the expressiveness perspective, TransE
and DisMult have been shown to be not fully expressive; however, CompleEx and
SimplE are fully expressive. Gutierrez-Basulto and Schockaert [14] use geometric
models to study the compatibility between TBox/ontology and KG embeddings.
They show that bilinear models (inc. ComplEx and SimplE) cannot strictly
represent relation subsumption rules. Wiharja et al. [30] show that many well
known KG embeddings based on KG completion methods are not impressive,
when schema aware correctness is considered, despite good performance reported
in silver standard based evaluations. Currently, more and more applications are
involving dynamic KG, where knowledge in practice is time-variant and consists
of sequences of observations. For example, in recommendation systems based on
KG, new items and new user actions appear in real time. Accordingly, temporal
KG embedding models incorporate time information into their node and relation
representations. We next discuss how temporal information is taken into account
in KG embeddings and how it has been used in combination with classical DLs.
Temporal Knowledge Graph Embeddings. Temporal KG embedding
models can be seen as extensions of static KG embedding models. A basic approach
is to collapse the dynamic graph into a static graph by aggregating the temporal
observations over time [19]. This approach, however, may lose large amounts
of information. An alternative approach is to give more weights to snapshots
that are more recent [28]. Another alternative approach to aggregating temporal
observations is to apply decomposition methods to dynamic graphs. The idea is to
model a KG as an order 4 tensor and decompose it using CP or Tucker, or other
decomposition methods to obtain entity, relation, and timestamp embeddings [12].
In addition to aggregation based approaches, there are approaches extending
static KG embedding, such as TransE, by adding a timestamp embedding into
the score function [15, 21]. Jiang et al. [15] only use such timestamps to maintain
temporal order, while using Integer Linear Programming to encode the temporal
consistency information as constraints. Ma et al. [21] extend several models
(Tucker, RESCAL, HolE, ComplEx, DistMult) by adding a timestamp embedding
to their score functions. These models may not work well when the number of
timestamps is large. Furthermore, since they only learn embeddings for observed
timestamps, they cannot generalize to unseen timestamps. Dasgupta et al. [11]
fragments a temporally-scoped input KG into multiple static subgraphs with each
subgraph corresponding to a timestamp. There are also approaches of applying
random walk models for temporal KG. E.g., Bian et al [6] use metapath2vec
to generate random walks on both the initial KG and the updated nodes and
re-compute the embeddings for these nodes. These approaches mainly leverage
the temporal aspect of dynamic graphs to reduce the computations. However,
they may fail at capturing the evolution and the temporal patterns of the nodes.
Another natural choice for modeling temporal KG is by extending sequence
models to graph data. E.g., Garcı́a-Duran [13] extend TransE and DistMult by
combining the relation and timestamp through a character LSTM, so as to learn
representations for time-augmented KG facts that can be used in conjunction
with existing scoring functions for link prediction. Ma et al. [21] argue that
temporal KG embeddings could also be used as models for cognitive episodic
memory (facts we remember and can recollect) and for semantic memory (current
facts we know) can be generated from episodic memory by a marginalization
operation.
Temporal Description Logics. In the DL literature, there are several ap-
proaches for representing and reasoning temporal information [20, 33, 5]. Schmiedel
[27] was the first to propose an extension of the description logics (the FLEN R−
DL in this case) with an interval-based temporal logic, with the temporal quanti-
fier at, the existential and universal temporal quantifiers sometime and alltime.
Artale and Franconi [2, 3] considered a class of interval-based temporal description
logics by reducing the expressivity to keep the property of decidability of the
logic proposed by Schmiedel [27]. Schild proposed ALCT [26], extending ALC
with point-based modal temporal connectives from tense logic [10], including
existential future (♦), universal future (), next instant ( ),until (U), reflexive
−
until (U). Wolter and Zakharyaschev studied the ALCM DL and showed that it is
decidable in the class of linear, discrete and unbounded temporal structures [31].
−
They also showed that the ALCM DL (extending the ALCM DL with global roles)
is undecidable [32]. Temporal operators can be used in a temporal ABox as well,
allowing the use of next instant ( ϕ) and until (ϕUψ) with ABox assertions [4].
Ozaki et al. [22, 23] propose temporally attributed DLs, which allows the use
of absolute temporal information in both TBoxes and ABoxes. They show that
the satisfiability of ground ELH@ T
ontologies is ExpTime-complete, and that the
satisfiability of ground ELH@ ontologies without the temporal attributes between,
T
before and after is PTime-complete.
6 Conclusion
We investigate how geometric models can (or cannot) be used to capture rules
about annotated data expressed in the formalism of attributed DLs. We show
that every satisfiable attributed DL-LiteH horn ontology has a convex geometric
model and that this is also the case when allowing the use of temporal attributes
under some restrictions. There is still a long way to make this result practical
since we still require an embedding technique that would construct such a model.
In this direction, we highlight the work of Abboud et al. [1], where relations are
mapped to convex regions in the format of hyper-rectangles.
Acknowledgements. We thank Bruno Figueira Lourenço for his contribution
on the proof of Theorem 3. Ozaki is supported by the Norwegian Research
Council, grant number 316022.
References
1. Ralph Abboud, İsmail İlkan Ceylan, Thomas Lukasiewicz, and Tommaso Salvatori.
Boxe: A box embedding model for knowledge base completion. In Proceedings of
NeurIPS, 2020.
2. A. Artale and E. Franconi. A computational account for a description logic of time
and action. In Proceedings of KR, 1994.
3. A. Artale and E. Franconi. A temporal description logic for reasoning about actions
and plans. Journal of Artificial Intelligence Research, 9, 1998.
4. Alessandro Artale, Roman Kontchakov, Carsten Lutz, Frank Wolter, and Michael
Zakharyaschev. Temporalising tractable description logics. In Proceedings of TIME,
2007.
5. Alessandro Artale, Roman Kontchakov, Vladislav Ryzhikov, and Michael Za-
kharyaschev. A cookbook for temporal conceptual data modelling with description
logics. ACM Trans. Comput. Log., 15(3):25:1–25:50, 2014.
6. Ranran Bian, Yun Sing Koh, Gillian Dobbie, and Anna Divoli. Network embedding
and change modeling in dynamic heterogeneous networks. In Proceedings of the of
the 42nd International ACM SIGIR Conference on Research and Development in
Information Retrieval, pages 861–864, 2019.
7. Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana
Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances
in neural information processing systems, pages 2787–2795, 2013.
8. Camille Bourgaux and Ana Ozaki. Querying attributed DL-Lite ontologies using
provenance semirings. In Proceedings of AAAI , 2019.
9. Camille Bourgaux, Ana Ozaki, and Jeff Z. Pan. Geometric models for (temporally)
attributed description logics, 2021. arXiv:2108.12239 [cs.LO].
10. J.P. Burgess. Basic tense logic. In D. Gabbay and F. Guenther, editors, Handbook
of Philosophical Logic, page 89–133. 1984.
11. Shib Sankar Dasgupta, Swayambhu Nath Ray, and Partha Talukdar. HyTE:
Hyperplane-based temporally aware knowledge graph embedding. In Proceedings of
the 2018 Conference on Empirical Methods in Natural Language Processing, 2018.
12. Cristobal Esteban, Volker Tresp, Yinchong Yang, Stephan Baier, and Denis
Krompass. Predicting the co-evolution of event and knowledge graphs. In Proceed-
ings of FUSION, 2016.
13. Alberto Garcı́a-Durán, Sebastijan Dumancic, and Mathias Niepert. Learning
sequence encoders for temporal knowledge graph completion. In Proceedings of the
2018 Conference on Empirical Methods in Natural Language Processing, 2018.
14. Vı́ctor Gutiérrez-Basulto and Steven Schockaert. From knowledge graph embedding
to ontology embedding? an analysis of the compatibility between vector space
representations and rules. In Proceedings of KR, 2018.
15. Tingsong Jiang, Tianyu Liu, Tao Ge, Lei Sha, Baobao Chang, Sujian Li, and
Zhifang Sui. Towards time-aware knowledge graph completion. In Proceedings of
COLING, 2016.
16. Seyed Mehran Kazemi and David Poole. Simple embedding for link prediction in
knowledge graphs. In Proceedings of NeurIPS, 2018.
17. Markus Krötzsch, Maximilian Marx, Ana Ozaki, and Veronika Thost. Attributed
description logics: Ontologies for knowledge graphs. In Proceedings of ISWC, 2017.
18. Markus Krötzsch, Maximilian Marx, Ana Ozaki, and Veronika Thost. Attributed
description logics: Reasoning on knowledge graphs. In Proceedings of IJCAI, 2018.
19. David Liben-nowell and Jon Kleinberg. The link-prediction problem for social
networks. J. AMERICAN SOCIETY FOR INFORMATION SCIENCE AND
TECHNOLOGY, 2007.
20. Carsten Lutz, Frank Wolter, and Michael Zakharyaschev. Temporal description
logics: A survey. In Proceedings of TIME, 2008.
21. Yunpu Ma, Volker Tresp, and Erik A Daxberger. Embedding models for episodic
knowledge graphs. Journal of Web Semantics, 59, 2018.
22. Ana Ozaki, Markus Krötzsch, and Sebastian Rudolph. Happy ever after: Temporally
attributed description logics. In Magdalena Ortiz and Thomas Schneider, editors,
Proceedings of DL, 2018.
23. Ana Ozaki, Markus Krötzsch, and Sebastian Rudolph. Temporally attributed
description logics. In Description Logic, Theory Combination, and All That -
Essays Dedicated to Franz Baader on the Occasion of His 60th Birthday, 2019.
24. Jeff Z. Pan, Yuan Ren, and Yuting Zhao. Tractable approximate deduction for
OWL. Artificial Intelligence, 235:95–155, 2016.
25. Jeff Z. Pan and Edward Thomas. Approximating OWL-DL Ontologies. In Proceed-
ings of AAAI, 2007.
26. K.D. Schild. Combining terminological logics with tense logic knowledge bases. In
Proceedings of EPIA, 1993.
27. A. Schmiedel. A temporal terminological logic. In Proceedings of AAAI, 1990.
28. Umang Sharan. Temporal-relational classifiers for prediction in evolving domains.
In In Proceedings of the IEEE International Conference on Data Mining, 2008.
29. Theo Trouillon, Christopher R. Dance, Eric Gaussier, Johannes Welbl, Sebastian
Riedel, and Guillaume Bouchard. Knowledge graph completion via complex tensor
factorization. J. Mach. Learn. Res., 18:130:1–130:38, 2017.
30. Kemas Wiharja, Jeff Z. Pan, Martin J. Kollingbaum, and Yu Deng. Schema Aware
Iterative Knowledge Graph Completion. Journal of Web Semantics, 2020.
31. F. Wolter and M. Zakharyaschev. Satisfiability problem in description logics with
modal operators. In Proceedings of KR, 1998.
32. F. Wolter and M. Zakharyaschev. Modal description logics: Modalizing roles. In
Fundamentae Informaticae, pages 411–438, 1999.
33. Frank Wolter and Michael Zakharyaschev. Temporalizing description logics. Fron-
tiers of Combining Systems, 2:379–402, 1999.