Knowledge graphs often enrich data with contextual information (such as temporal validity or provenance of an assertion) in the format of annotations, which can be seen as attribute-value pairs. Recently, attributed description logics have been proposed to bridge the gap between the data format present in knowledge graphs and classical description logics [4, 3, 5]. The mentioned works analyse the complexity of the satisfiability problem for various attributed description logics. This extended abstract gives an overview of our work [1], published at AAAI 2019, on query answering in attributed description logics using provenance semirings. After investigating satisfiability and query answering in attributed DL-LiteR, we turn our attention to provenance information, one of the most common types of annotation in knowledge graphs. Indeed, since knowledge graphs often integrate data from multiple sources, one may not be only interested in obtaining query results but also in establishing levels of trust, or determining authorship, among others [7]. To deal with provenance information, we propose a new semantics based on provenance semirings, as first introduced in database theory [2] (and also recently studied in an ontology-based data access setting [6]). Attributed DL-LiteR Attributed DLs are defined over the usual DL signature with countable sets of concept names NC, role names NR, and individual names NI. We consider an additional set NU of set variables and a set NV of object variables. Annotation sets are defined as finite binary relations, understood as sets of attribute-value pairs. Attributes and values refer to domain elements and are syntactically denoted by individual names. To describe annotation sets, we use a set S of specifiers, which can be either set variables; closed specifiers bda1 : v1; : : : ; an : vnce; or open specifiers ba1 : v1; : : : ; an : vnc, where ai 2 NI and vi is either an individual name in NI, 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 NI. We use X:a to refer to the (finite, possibly empty) set of all values of attribute a in an annotation set X. Intuitively, closed specifiers define specific annotation sets whereas open specifiers merely provide lower bounds [3]. A ground specifier is a closed or open specifier that only contains individual names. A DL-Lite@R role (resp. concept) assertion is an expression R(a; b)@S (resp. A(a)@S), with R 2 NR (resp. A 2 NC), a; b 2 NI, and S 2 S a ground closed specifier. DL-Lite@R role and concept inclusions are of the form X : S (P v Q) and X : S (B v C) respectively, where X 2 NU, S 2 S is a closed or open specifier, and P; Q and B; C are respectively role and concept expressions defined by the following syntax, where A 2 NC, R 2 NR and S 2 S:
Q ::= P j :P;
C ::= B j :B:
We require that all variables are safe, which intuitively means that if they appear on the
right side of an inclusion then they should also be associated to the concept on the left.
Example 1. In DL-Lite@R, we can express that those who are married (role spouse) to
someone are married (concept Married), and that this fact is associated with the same
sources from which the information has been extracted (attribute src): 9spouse@X v
Married@bsrc : X:srcc: The assertion spouse(gabor; ryan)@[src : s1; src : s2] states that
Gabor is married to Ryan and it is annotated with the sources of this information.
We similarly define attributed conjunctive queries by associating concept and role names
with specifiers. The formal definition of the semantics is given in [
Example 4. The query (Married(a)^Married(b))@bsrc: s1 (s2 +s3); cls: pub cnfc is entailed by the assertions Married(a)@bdsrc: s1; cls: pubce, Married(b)@bdsrc: s2; cls: cnfce, and Married(b)@bdsrc: s3; cls: cnfce. The fact that a and b are both married is obtained by combining s1 with s2 or s3, and by having access to public and confidential information. Sums may also appear in concept inclusions, e.g., X : bsrc : s1 + s2c(9spouse@X v Married@X); which requires that the fact that someone has a spouse has to be associated both with s1 and with s2 to conclude that this person is married.
We establish complexity results for this variant of attributed DL-Lite, which we call DL-Lite@R;K. The salient results of our investigation are the EXPTIME-hardness for the satisfiability problem, and the NP-completeness of query entailment for a restricted class of ontologies, called simple, that allows for inclusions among atomic concepts or roles of the form E1@S v E2@T where S and T are ground specifiers.
Theorem 5. In DL-Lite@R;K, satisfiability is EXPTIME-hard and in 2EXPTIME. When the ontology is simple, query entailment is NP-complete.