In this paper we study the distinct count aggregation function used in queries into expressive ontologies. The main di erences in this settings opposed to aggregation in relational database systems are the Open World Assumption and incomplete knowledge. We propose di erent interpretations useful in di erent practical use-cases of the distinct count function, i.e. basic count, semantic count, epistemic count and semantic tuple count some of which use knowledge derived from the ontology in order to obtain results in accordance with the Open World Assumption. We use interval semantics to model the uncertainty of the distinct count function's result induced by incomplete knowledge in the ontology. We show that interval semantics are particularly useful in aggregate queries with ltering clause and when we need the retrieval of the boundaries of the uncertainty of the distinct count function's result. We study and present relationships among the di erent interpretations and decidability of the semantic tuple count. We also propose a theoretical approximation of the semantic tuple count. Our results are applicable to a wide range of description logic formalisms allowing to express equality/inequality between individuals, concepts and relations, e.g. Web Ontology Language.
Aggregation functions are an important feature of modern query languages. Aggregation is well understood in query languages of database systems with Unique Name Assumption (UNA) principle, e.g. SQL for relational databases. Although this simple well-known interpretation of aggregation can in some cases be used correctly in queries over semantic knowledge bases, in general this interpretation will return incorrect results as it will not use knowledge inferred from the knowledge base with the Open World Assumption (OWA). As opposed to that, semantic aggregation relies on the knowledge inferred from the knowledge base in order to provide correct result of aggregation functions.
Currently the research led of semantic aggregation is in its infant state. However the need of semantic aggregation is becoming apparent as more and more applications of semantic technologies emerge. In this paper we propose the need of di erent interpretations of the distinct count function in the settings of OWA and ontology representing incomplete knowledge, i.e. basic count (BC), semantic tuple count (ST C), epistemic count (E C) and semantic count (SC). We study the relationships among the di erent interpretations. We also investigate the decidability of the ST C interpretation. 2
In recent years, expressive query languages, like SPARQL-DL [
Recently the RDF query language SPARQL [
More closely related to our study is the work [
Although not exactly in the same framework of query answering like in this
paper, the authors in [
In this paper we examine the distinct count aggregation function, its possible interpretations and their use-cases. We focus our research on the distinct count aggregation function alone as it is non-trivial but not too overly complicated. We believe that better understanding of the distinct count function and its possible interpretations will cover most of the peculiarities of aggregation in the context of expressive knowledge bases assuming the OWA principle and incomplete knowledge, thus contributing to OWL and RDF.
In this section we present a simple ontology which describes a simple taxonomy
of teachers categories and contains assertions about teachers and courses. The
ontology is presented using the well known description logic syntax, see [
Tbox BusyTeacher v Teacher, Professor v Teacher, 9teaches Course v Teacher, BusyTeacher v 3 teaches, Professor v 3 teaches Abox BusyTeacher(Sara), Professor(Steve), Professor(John), BusyTeacher(John), Course(math), Course(physics), Course(history), teaches(Dave; math), teaches(Dave; physics), teaches(Dave; history), teaches(Sara; history), : math 6= history
We will use the following two aggregate queries throughout the paper to demonstrate the di erences in the results of the individual interpretations of the distinct count function.
Q1 - Find all teachers and the number of distinct courses they teach. Q2 - Find all teachers that teach more than one distinct courses.
Next we will discuss the need of di erent interpretations of the distinct count function. The most natural interpretation of the distinct count function is the semantics count interpretation. This interpretation enables users to query for the distinct count function value or its constraints as entailed by the queried ontology. For example using this interpretation in query Q1 we obtain that John teaches exactly three courses or using it in query Q2 we will obtain that Dave, Sara and John teach more than one course. We call this the semantics count interpretation and we consider it suitable for knowledge retrieval oriented usecases. This interpretation is a natural extension of the certain answer semantics for the distinct count function and it is monotonic.
Although that is the most natural and in fact correct extension of the
semantics of the distinct count function, there are some use-cases that need di erent
CWA interpretations. As argued in [
Note that the epistemic count interpretation may count both named and
unnamed entities. This makes the use of this interpretation inappropriate in
purely data-centric ontology applications. In [
The most common interpretation of the distinct count function is the basic count interpretation. This interpretation is scalable and it is safe to be used in data oriented use-cases in CWA and UNA systems. The usage of this interpretation in applications assuming OWA may return incorrect results, however, it can still be used as an approximation. For example the result of query Q1 contains the answer Dave teaches three courses, which may or may not be true according to the ontology.
We continue with the formal de nition of the di erent interpretations of the distinct count function and the discussion of the results of queries Q1 and Q2 in these interpretations. 4
In this section we will de ne basic terms and notions used in the rest of the paper. We will start with the de nition of ontology followed by the de nition conjunctive queries and aggregate queries with distinct count function. 4.1
De nition 1. An ontology O is a pair hS; Ai, where S is a signature and A is a set of axioms. The semantics of ontologies use a rst order interpretation I = ( I ; I ), where I is an interpretation domain and I : S ! I is an interpretation function mapping elements from the ontology signature S to elements from the interpretation domain I . An ontology O is satis ed by an interpretation I, denoted by I j= O, if all of its axioms are satis ed by the interpretation I, such interpretation I is called a model of O. We say that a set of axioms A is entailed by the ontology O, denoted by O j= A, if every model I of the ontology O, is also a model of A, I j= A.
Next we de ne the notion of the monotonic extension O0 of the ontology O. De nition 2. We say that O0 = hS0; A0i is an extension of O = hS; Ai if A A0 and S S0. O0 is monotonic if the original ontology O is entailed by O0, 0 = O. A model I0 = ( I0 ; I0 ) of the ontology O is an extension of the model IO =j ( I ; I ) j= O if I0 I0 and I0 I .
For a full description of the syntax and semantics of di erent description
logic formalisms see [
We consider description logics which allow only monotonic extensions. In section 5.2 where we prove decidability of the semantic tuple count we further restrict to a subfamily of description logics that enable expressing whether two entity objects are di erent, the same or it is not known, which we will refer to as equality/inequality relation. We require the OWA assumption over the equality/inequality relation because it provides means to model incomplete knowledge, and it is the fundamental source of uncertainty of the semantic tuple count function's value. 4.2
The discussion in this paper about distinct count function and its proposed interpretations is set in the context of conjunctive queries.
De nition 3. We will denote conjunctive queries using the following rule like notation
Q(x) (x; z): (1) The head of the query Q(x) denotes the name of the query and the result variables Rvar(Q) = x. The body of the query (x; z) is a comma separated list of query atoms interpreted as a conjunctive query, as de ned in the SPARQL-DL 2 query language. The query atom list may contain non result variables z. Note that the result variables must be distinguished. By Vvar(Q) we denote the list of all variables in the query. A binding : Vvar(Q) ! S is a mapping of the variables of the query to elements in the ontology's signature and Qj is the substitution of the variables in Q by the binding . The binding substitution of a tuple of variables v = (v1; : : : ; vk) is denoted by (v) = ( (v1); : : : ; (vk)). We call Q a ground query if there are no variables in the query. A solution to the query Q w.r.t. the ontology O is a binding for which the substitution Qj is a ground query, the body of which is entailed by the ontology (denoted by O j= Qj ). The set of all possible solutions of Q w.r.t. O or the model I of O is denoted by SatQO = f jO j= Qj g or SatIQ = f jI j= Qj g respectively . The result set of query Q w.r.t. O denoted by QO, is a set of bindings of the result variables Rvar(Q), formally QO = faja = (Rvar(Q)) ^ 2 SatQOg. 4.3
Here we de ne the types of aggregate queries along with their simple syntax used for the purpose of representing aggregate queries in this paper. We also de ne some additional terminology and symbols used later in the paper. De nition 4. We will denote distinct count retrieval and distinct count ltering queries respectively as follows:
Qa(x; countdSist(y)) (x; y; z) (2)
( opncountdSist(y)); (x; y; z) In the queries of the type Qa, the head Qa(x; countdSist(y)) speci es the disjoint sets of grouping Gvar(Qa) = x and aggregation Avar(Qa) = y variables. The distinct count aggregation function which returns the number of distinct tuples according to the semantics mode speci ed by the superscript S w.r.t. the ontology O is denoted by countdSist. The body of Qa contains a query atom list.
We also consider distinct count ltering by comparison queries of the form Qac show in (3). The head of queries of these type contain only the grouping variables. The body of the query contains cardinality restriction atom3 where op 2 f>; <; ; ; =; 6=g. By Q we denote a non aggregate variant of Q, obtained from Q by removing its aggregate function from the head or the comparison predicate in the body. The result variables of Q are the union of group and aggregate variables of Q, Rvar(Q ) = Gvar(Q) [ Avar(Q).
Before we de ne the general semantics of the result of aggregate queries we clarify and de ne the auxiliary terms and notations in the following three de nitions.
De nition 5. Let N0;1 be the extension of the set of natural numbers with zero and in nity N0;1 = N [ f0; 1g. Let L be a subset of N0;1 and let Int(L) denote the smallest interval containing L,Int(L) = hinf(L); sup(L)i. We extend the intuitive comparison between elements in N0;1 with comparison between sets L N0;1 and elements n 2 N0;1 . L n (L < n) is be true if and only if sup(L) n _ sup(L) = n = 1 (sup(L) < n). L n (L > n) is true if and only if inf(L) n _ inf(L) = n = 1 (inf(L) > n). Note that the symbol 1 is an element of N0;1 .
Next we de ne the interpretation a tuple and a set of tuples.
De nition 6. Let O = hS; Ai be an ontology, I = ( I ; I ) a model of O and T be a set of tuples composed of elements in S. The interpretation of the of the tuple t = (t1; t2; : : : ; tk); t 2 T is tI = (t1I ; t2I ; : : : ; tkI ). The interpretation of T is T I = ftI j8t 2 T g.
Next we de ne aggregate groups or simply groups as the set of tuples with common grouping variable binding.
De nition 7. Let Q be an aggregate query of type Qa or Qac, O be an ontology,
I a model of O and let k = (Gvar(Q )), where is an arbitrary binding. Then
the aggregate group, denoted by (O; Q; k), with key k is equal to the set of tuples
f (Avar(Q))j (Gvar(Q)) = k ^ 2 SatQO g. The aggregate group with key k in a
tuple set T is (T; k) = faj8t 2 T; (k; a) = tg.
3 Note that we reuse the well known notation for property cardinality restrictions, see
[
Note that the de nition of the aggregate group (O; Q; k) w.r.t. to the ontology O can be used also to obtain an aggregate group w.r.t. to the model I of O, i.e. (I; Q; k).
Next we de ne results of aggregate queries in terms of the counting function f S [O;Q] is an [O;Q] and the set KS (O; Q). Informally the counting function f S uncertainty aware generalization of the distinct count function, it takes as an input the key of the group to be counted and returns a set of possible values w.r.t. O and Q. The set KS (O; Q) is the set of keys of the groups to be counted. The counting function and the key of sets will be de ned in each of the concrete distinct count interpretations. The superscript is used to distinguish among the di erent interpretations.
De nition 8. Let D be the set of all tuples of arbitrary length and P(N0;1 ) be the power set of N0;1 . Let S be an aggregate semantic, f S [O;Q] : D ! P(N0;1 ) be the counting function and KS (O; Q) D be the key set in S. The result of an aggregate query Q of type (2) w.r.t. the ontology O is QO = f(k 2 KS (O; Q); inf (L))jL := f S
[O;Q](k) ^ inf(L) = sup(L)g and the result set of an aggregate query Q with comparison ltering, i.e. queries of the form Qac, is QO = fk 2 KS (O; Q)jL := f[SO;Q](k) ^ L op ng. The interpretation of the last condition L op n is de ned in De nition 5. 5
Distinct count function In this section we formally de ne the semantics of each of the various interpretations of the counting function f S
[O;Q] and the set of keys KS (O; Q). We present this de nitions in order to be able to show formally the relations between the interpretations and in the case of SC and ST C to be able evaluate comparison ltering queries in OWA. We show and discuss the results of the example queries Q1 and Q2 from section 3 in each of the proposed semantics. We also study the relationship between individual interpretations of the distinct count function. We prove decidability of the semantic tuple count ST C interpretation. Finally we show how to enable distinct count queries in the context of the description logic SROIQ.
In (4) we show the queries Q1 and Q2 from example 1 in the notation de ned in De nition 4.
Q1(?t; countdist?c) PropertyValue(teaches; ?t; ?c) Q2(?t) (>1countdist(?c)); PropertyValue(teaches; ?t; ?c) (4)
The tables in this section showing the results of the queries have the following notation. Only cells highlighted with grey background color 4 are part of the result set of the query. The other cells have white background. Note that through out this section O = hS; Ai is an arbitrary ontology with a signature S and an axiom set A, Q is an arbitrary aggregate query, O1 refers to the ontology in example 1 and Q1 and Q2 refer to the queries shown in (4). 4 The use of colors in this paper is intended to be readable in gray scale copies. 5.1
In this section we discuss three known interpretations of the distinct count function in aggregate queries.
Basic Count Interpretation The basic count interpretation (BC) is used originally in the SQL query language, but it is also used in semantic query languages, e.g. SPARQL and SQWRL. This interpretation is not adequate for ontological knowledge as it does not infer the distinct count function's value from the ontology. The basic count interpretation can be implemented in n log n time, where n is the size of the tuple set to be counted.
De nition 9. The set of keys KBC(O; Q) is the set of all syntactically distinct result bindings of the grouping variables Gvar(Q) of the query Q over the ontology O, i.e. KBC (O; Q) = fkjk = (Gvar(Q)) ^ 2 SatQO g. For k 2 KBC(O; Q) the counting function is de ned as f[BOC;Q] = fj (O; Q; k)jg.
The result of the distinct count query Q1 is shown in table 1(a).
There are two group keys Dave and Sara. The number of courses Dave teaches is three because there are three courses that Dave teaches asserted in the ontology, whose names are syntactically di erent. For Sara, who teaches only one course according to the ontology, the result of the count function is one. We can see that this interpretation ignores the implicit knowledge derived from the fact that Sara is a BusyTeacher that teaches at least three courses.
Semantic Count Interpretation Informally the semantic count (SC)
interpretation counts the number of possible tuples entailed by the queried ontology.
This interpretation is similar to the exact semantics presented in [
Next we discuss the results of the example queries Q1 and Q2, with formal representation shown in (4), over the ontology O1 from example 1. The last columns in the tables 2(a) and 2(b) show the boundaries of the intervals found for each of the group keys from the rst column.
In table 2(a) we show the results of query Q1. Next we discuss the intuition of the calculation of the values of the SC counting function for each of groups in table 2(a). In order to obtain the nal result of the query we need to apply the comparison semantics from de nition 8. The last row in both tables show an unexpected group which the algorithm should process. In fact we have two more groups that we omitted from the table which are with keys history and physics. This is an e ect of the OWA assumption. This anomaly is caused by the fact that the ontology O1 does not explicitly state that math, history and physics are not teachers and that only teachers can teach and thus allowing the existence of models in which subjects teach something. Moreover the calculated interval is zero to in nity because there are no axioms which constraint it. The SC can be used to locate such unwanted behavior. The minimum in the rst row with group key Dave is obtained from the two semantically distinct courses math and history that Dave teaches. The maximum of the rst row is in nity because the ontology does not constrain the number of courses Dave can teach. The minimum of the second row with group key Sara is determined from the constraint that a BusyTeacher teaches at least three courses and the fact that Sara is a BusyTeacher and who teaches history. In this case there are two restrictions, 'at least three' and 'at least one' which constraint the minimum of courses Sara teaches. In such cases we should select the most speci c one. Therefore the minimum of the second row's interval is three since the rst restriction is more speci c. The evaluation of the maximum in the second row's interval is analogous to the one in the rst row. The third row's minimum is zero because Steve is not constrained to teach a minimum number of courses as Dave and Sara were in the rst and second rows. The maximum in the third row is derived from the fact that Steve is a professor and the constraint of the Professor class which limits its instances to teach at most three courses. Now we apply interval semantics to the rst three rows that we discussed. The three rows are not included in the result of query Q1 with SC semantics because according to the de nition of the results of queries of type Qa in de nition 8 which states that set returned by the counting function must be singleton. The answer contains only the last row because the return value of the counting function is a singleton containing only the number three. This is true because the John is both a Professor and a BusyTeacher the constraints of which were already discussed.
The results of query Q2 as well as all the relevant group keys of Q2 are shown in table 2(b). We have discussed the interval boundaries of the intervals for groups of Q1 and since the Q2 has identical groups, note that KSC(O1; Q1) = KSC(O1; Q2), we skip this explanation for query Q2. The result of Q2 contains all rows except for the third one with group key Steve that does not satis es the comparison lter which limits the retrieval of groups with at least two distinct tuples in all models of the ontology O1.
We point out the importance of interval semantics in the settings of
incomplete knowledge. Note that in query Q2 we obtained results that were not present
in the result of Q1. This proves that the results of query Q2 obtained by ltering
the results of query Q1 won't contain the full result entailed by the ontology.
Epistemic Count Interpretation The epistemic count (E C) interpretation is
introduced in the work [
De nition 11. The E C key set is de ned as KEC(O; Q) = KSC(O; Q). The E C counting function is de ned as f[EOC;Q](k) = finf(f[SOC;Q](k))g.
In tables 3(a) and 3(a) we can see the results of the aggregate queries Q1 and Q2 respectively with distinct count function interpreted with the E C semantics. The results are identical with those of the minimum of the interval in tables 2(a) and 2(b) and are not discussed further. 5.2
Semantic Tuple Count Interpretation The semantic tuple count (ST C) interpretation is de ned using interval semantics. Informally it counts the same tuples as the BC interpretation but it uses knowledge in the ontology to derive the equivalence/inequivalence relation between the counted tuples which is needed to remove semantically duplicate tuples and also to deal with uncertainty of the count's value.
De nition 12. The ST C key set KST C is de ned as the key set of the BC interpretation, i.e. KST C (O; Q) = KBC(O; Q). We de ne the ST C counting function as follows f[SOT;QC](k) = fj (O; Q; k)I jj8I j= Og.
Next we discuss the results of queries Q1 and Q2 from example 1 with the ST C interpretation. Here we also show all the group keys that should be considered during evaluation of the ST C interpretation and since the ST C interpretation is interval based we also show the evaluated intervals in the last columns of the tables 4(a) and 4(b). In table 4(a) we have the results of Q1. Now we discuss the values of the interval boundaries in rows one and two. The minimum in the rst row is based on the two distinct courses math and history. The maximum is three because there are three entailed tuples in the group of the rst row and because there is no other axioms that constraints the maximum to be smaller. The minimum in the second row is one because we have only one tuple for the Sara group. This is also the only possible value for the maximum of row two because there are no other entailed tuples in that group. Apparently from the interval semantics only the second row is returned.
The results for the query Q2 are shown in table 4(b). We already discussed the interval boundaries in the discussion of query Q1. Applying the interval semantics we lter the second row because Sara teaches only one distinct course and therefore it is not contained in the result. The rst is contained in the result because the minimum boundary, which is 2, is bigger than the less than operand in the ltering atom, which is one.
Decidability of the ST C Interpretation In this section we prove decidability
of the ST C interpretation. We present only the statements of the most relevant
lemmas and the proof of the theorem at the end of the section. The omitted
proofs and lemmas can be found in the technical report [
Implementing the evaluation of the ST C counting function based on de nition 5.2 is not feasible because the ontology O might have an in nite number of models. We show that there is a nite number of models su cient for the calculation of the boundaries of the value of the ST C counting function.
The next proposition states that the interval of the distinct count function with SC and ST C interpretation w.r.t. the ontology O will be more speci c if we extend the queried ontology. The interval calculated w.r.t. the original ontology will include the one calculated from the extended ontology.
Note that in this section we will use identical equality and inequality axioms, denoted by =a and 6=a respectively, for all type of entities, i.e. individuals,classes and properties. In the following section we show an equivalent representation of this axioms in the concrete logic SROIQ.
De nition 14. Let O = hS; Ai be an ontology, T be a tuple set composed of elements in the set D S. Let I = ( I ; I ) be an interpretation such that I is de ned on D then the complete set of equality/inequality axioms satis ed by I is denoted as A#(I; D) = fa =a bj8a; b 2 D; aI = bI g [ fa 6=a bj8a; b 2 D; aI 6= bI g. We denote the set all complete sets of equality/inequality axioms between elements in D w.r.t. the ontology O as A#(O; D) = fA#(I; D)j8I j= Og. The cannonic model of A# = A#(I; D), denoted by IA# = ( IA# ; IA# ) is a model with an interpretation function IA# the domain of which is D.
Note that adding equality/inequality axioms to the complete set A#(I; D) wont change the original set or if it does the resulting set is unsatis able. Note also that the cannonic interpretation function IA# can be constructed in polynomial time.
Lemma 1. Let O = hS; Ai be an ontology, D S, then A#(O; D) is nite.
Lemma 2. Let T be a tuple set composed of elements from set D and two interpretations I1 and I2 which agree on the equivalence and inequivalence between elements in D. Then the number of elements in the sets T I1 and T I2 is the same, jT I1 j = jT I2 j.
The next lemma states that for extensions of the ontology O with an axiom set from A#(O; D) the ST C counting function returns a singleton set and that the only value in the set can be calculated in polynomial time.
Lemma 3. Let O = hS; Ai be an ontology, Q be an aggregate query, k 2 KST C, T = (QO; k) and D be the set of elements composing tuples in T , I = ( I ; I ) be a model of O, A# = A#(I; D), O0 = hS; A [ A#i and IA# be the cannonic interpretation function of A#. Then f[SOT0;CQ](k) = fcg, where c = jT I j = jT IA# j.
Instead of looking for the boundaries of the ST C interval in the set of all models as the de nition 12 suggests, we can search for the boundaries in the nite set of representations of the equality interpretation. We rst describe an algorithm which terminates in a nal number of steps and then we prove its correctness.
Algorithm 1 : STC - Semantic Tuple Count procedure PROCEDURE STC
INPUT : O // the queried ontology,
T // set of tuples to be counted OUTPUT : <a,b> // the calculated interval a := inf; b := 0; D := {elements used in tuples in T}; FORALL A# IN A#(O,D) DO
A' := union(A, A#); IF A' is consistent construct cannonic interpretation I#(A#); c := |T interpreted by I#(A#)|; IF a > c THEN a := c;
IF b < c THEN b := c;
END-IF END-FORALL
RETURN <a,b>; END
We will prove decidability by proving correctness and termination of algorithm 1.
Theorem 1. The algorithm 1 terminates and evaluates correctly the interval Int(f[SOT;QC](k)) for an ontology O and aggregate query Q and group key k. Proof. Algorithm 1 terminates since there is a nite number of extensions to check. From lemma 3 we have that the ST C counting function is a subset of the calculated interval. Also from lemma 3 we have that the interval is the smallest because the boundaries correspond to some model of O.
Corollary 1. Calculation of the ST C interval is decidable in the family of
formalisms de ned in De nition 13.
ST C Interpretation approximation The proposed algorithm 1 is searching
trough all the possible extensions for the set of elements D. As we show in
corollary 1 there are n = 2jDj2 possible extensions for each of which we need to make
a consistency check. In this section we propose an approximation of the ST C
interpretation which can be used for example as optimization of an evaluation
algorithm. The approach presented here utilizes the knowledge inferred from the
ontology. The prove of the correctness of the approximation is presented in the
technical report [
De nition 15. Let G = (V; E) be an undirected graph with nodes V and edges E. A connected component K in G is a subgraph in G maximal with the property, for each pair of nodes in K there is a path in K. A (maximal) clique C is a graph maximal with the property C is a subgraph of G and is complete. The biggest clique C in G is called maximum.
In order to de ne the approximation formally we need rst to de ne the auxiliary term di erence graph, and the notion of maximum clique. De nition 16. Let O = hS; Ai be an ontology, let T be a set of tuples of length l and composed of elements from the set D S. Let s; t 2 T , equality s =a t and inequality of tuples w.r.t. the ontology O is de ned respectively as O j= fs1 =a t1; : : : ; sl =a tlg and O j= si 6=a ti for some 1 i l. Let G=(O; T ) = (D; E=(O; T )) be the graph with edges E=(O; T ) = f(a; b)j8(a; b) 2 T 2; O j= a =a bg. The di erence graph is denoted by G(O; T ) = (V; E) w.r.t. O and T . The set nodes is the set of connected components of G=(O; T ), there is an edge between the nodes u and v in V , fu; vg 2 E if and only if the ontology entails 6=a axiom between some pair of the set u v.
Theorem 2. Let O be an ontology, Q an aggregate query, k 2 KST C (O; Q) and let T = (O; Q; k) be the group to be counted. Let the G(O; T ) = (V; E) be the di erence graph w.r.t. O and T and Cmax = (VC ; EC ) be the maximum clique graph of G(O; T ). Int(f[SOT;QC](Vvar(k))) hjVC j; jV ji.
ST C interpretation in SROIQ In this section we discuss the countdSiTstC
function in a concrete description logic SROIQ. The ST C interpretation is
decidable in this description logic since SROIQ satis es all the requirements
shown in De nition 13. We consider any query language which supports
conjunctive queries with mixed Abox, Tbox, Rbox terms, e.g. SPARQL-DLNOT
[
5.2 shows the representations for each of the three term types. Individuals ik; k 2 1; 2; 3:::, are unique and not contained in the ontology. Note that classes and properties have two possible ways of representing the inequality relation. If one of the representations fails we must also test the other when checking whether two terms of type class or property need to be compared for inequality. type =a
6=a We investigated the distinct count function in the context of di erent semantics, i.e. BC, SC and E C. We introduced a new interpretation ST C and compared its behavior with the other interpretations. We found the following relationships between SC and E C, inf(f[SOC;Q]) = E C and also between SC and ST C, inf(f[SOT;QC](k)) inf(f[SOC;Q](k)) and sup(f[SOT;QC](k)) sup(f[SOC;Q](k)). We proved decidability of the ST C interpretation in the context of the selected family of formalisms, provided an approximation using basic graph problems and showed how to apply the ST C in the SROIQ description logic.
In future work we would like to focus on the implementation of the evaluation
of the ST C interpretation into the SPARQL-DLNOT [
Acknowledgments This work has been supported by the grant by the grant of the Czech Technical University in Prague No. SGS13/204/OHK3/3T/13 E ective solving of engineering problems using semantic technologies. Authors also want to express thanks to the anonymous reviewers for providing useful comments during manuscript preparation.