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-Lite R , 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-Lite R Attributed DLs are defined over the usual DL signature with countable sets of concept names N C , role names N R , and individual names N I . We consider an additional set N U of set variables and a set N V 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 a 1 : v 1 , . . . , a n : v n ; or open specifiers a 1 : v 1 , . . . , a n : v n , where a i ∈ N I and v i is either an individual name in N I , an object variable in N V , or an expression of the form X.a, with X a set variable in N U and a an individual name in N I . 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 ∈ N R (resp. A ∈ N C ), a, b ∈ N I , and S ∈ S a ground closed specifier. DL-Lite R @ role and concept inclusions are of the form X : S (P Q) and X : S (B C) respectively, where X ∈ N U , S ∈ 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 ∈ N C , R ∈ N R and S ∈ S:

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): ∃spouse@X Married@ src : X.src . The assertion spouse(gabor, ryan)@[src : s 1 , src : s 2 ] 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 [1].

Example 2. The query ∃x Married(gabor)@ year : x ∧ Married(taylor)@ year : x holds if Gabor and Taylor were married (to someone) on the same year.

We establish complexity results for the satisfiability and query entailment problems.

Theorem 3. In DL-Lite R @ , satisfiability and query entailment are PSPACE-complete. When the ontology does not contain variables, query entailment is NP-complete.

We now define a new semantics for dealing with provenance, which is based on semirings.

Provenance semirings-based semantics We study query entailment in attributed DL-Lite using a provenance semiring-based semantics. We represent provenance with the positive algebra provenance semiring for N I , defined as the commutative semiring of polynomials with variables in N I and coefficients from N, with operations defined as usual: K = (N[N I ], +, ×, 0, 1) [2]. We denote by N P the set of polynomials of K and by N S the subset of N P containing the sums of the commutative monoid (N[N I ], +, 0). We allow to use provenance polynomials from N P as values in a specifier associated to the whole query and provenance sums from N S as values in specifiers occurring in the ontology or associated with query atoms. Intuitively, + indicates alternative use of the data while × indicates join use of the data. For instance, if the result of a query over an ontology can be obtained from source s 3 together with any of s 1 , s 2 then the provenance polynomial is: (s 1 + s 2 ) × s 3 . The main idea is that now we allow the whole query to be annotated with a provenance polynomial and such query is entailed if the polynomial represents the alternative and join uses of the data. More specifically, we introduce semiring attributed queries, which are attributed queries where we associate a specifier to the whole query [1].

Example 4. The query (Married(a)∧Married(b))@ src: s 1 ×(s 2 +s 3 ), cls: pub×cnf is entailed by the assertions Married(a)@ src: s 1 , cls: pub , Married(b)@ src: s 2 , cls: cnf , and Married(b)@ src: s 3 , cls: cnf . The fact that a and b are both married is obtained by combining s 1 with s 2 or s 3 , and by having access to public and confidential information. Sums may also appear in concept inclusions, e.g., X : src : s 1 + s 2 (∃spouse@X Married@X), which requires that the fact that someone has a spouse has to be associated both with s 1 and with s 2 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 E 1 @S E 2 @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.