For reasoning over streams of data ontology-based data access is a common approach. The method for answering conjunctive queries (CQs) over DL-Lite ontologies in this setting is by rewritings of the query and evaluation of the resulting query by a data base engine. For streambased applications the classical expressivity of DL-Lite lacks means to handle fuzzy and temporal information. In this paper we report on a combination of a recently proposed pragmatic approach for answering CQs over fuzzy DL-Lite ontologies with answering of CQs over sequences of ABoxes, resulting in a system that supplies rewritings for query answering over temporal fuzzy DL-Lite-ontologies.
We report in this paper on work in progress regarding answering queries for extensions of the lightweight ontology language DL-Lite by fuzzy and also by temporal information, which are tailored towards the use in ontology-based situation recognition.
The main task in context-aware or self-adaptive systems is to recognize
situations that might invoke an adaptation of the system to new conditions in their
surroundings. To this end data is collected from multiple sources, often times
sensors and stored in a data base system. A description of situations that might
invoke an adaptation is matched against the data to detect the occurrence of
a critical situation in the data. The ontology-based approach to such situation
recognition enriches the observations made by sensors semantically and thus
offers a higher-level view on the data collected. In the ontology-based approach
the critical situations are captured by queries that are evaluated over the data
enriched by the background knowledge captured in the ontology. Now, since
potentially a huge amount of such preprocessed data has to be queried, e cient
algorithms are expedient. In our case we employ the ontology language DL-Lite
and answering of conjunctive queries (CQs), which are a simple form of rst
order queries, to recognize critical situations. It is well-known that DL-Lite-family
of allows for answering of CQs in LogSpace [
Now, in context-aware systems that employ streams of sensor data, the expressivity of standard ontology languages often might be too limited. For instance, the numerical values obtained from the sensors are mapped to coarser logical categories such as high, medium or low. For such categories the concept membership of a particular measurement is rather vague calling for the use of fuzzy ontology languages that allow for membership degrees expressing that a particular measurement belongs to a category only to a certain extent. Another short-coming of standard ontology languages is the lack of modeling temporal information. Now, each of these two extensions are known to make reasoning in ontology languages undecidable, if allowed for modeling concepts. Thus, we chose combinations that allow for fuzzy or temporal information only in the data and in the query.
In our pragmatic approach to answering of (fuzzy) CQs, a crisp DL-Lite reasoner is used as a black box to obtain an initial rewriting of the CQ (without degrees). The obtained query gets extended in a second rewriting step by (1) fuzzy atoms, (2) degree variables that capture membership degrees, and (3) numerical predicates that realize the fuzzy operators. The resulting query can then be evaluated by a SQL engine. We have implemented this rewriting procedure in our reasoner FLite and report on its performance in this paper.
A similar extension of the classical rewriting approach has recently been
employed for the temporal setting [
The rest of the paper is structured as follows: While in the next section we give the preliminaries on fuzzy DL-Lite and fuzzy ontologies, we describe the extension of the classical rewriting procedure to fuzzy information in Section 3 and its implementation in the FLite system. Section 4 gives results on a performance evaluation of FLite on a situation recognition use-case. Conclusions and future work end the paper in Section 6.
We start with the concept language of DL-LiteR and then introduce our fuzzy variant of ABoxes. The information in a DL-knowledge base is described by means of the following atomic types: concept names form the set NC, role names from the set NR, individual names from the set NI and for the queries also from the set of variables NV. From these elements the complex DL-LiteR-concepts, -roles and -queries are constructed. DL-LiteR-concepts and -roles are de ned according to the following grammar:
B !A j 9Q
C !> j B j :B
Q !P j P
R !Q j :Q; where > is the top concept, A 2 NC, P 2 NR. Based on these kinds of complex concepts and roles, a DL-LiteR TBox T is a nite set of axioms of the form: B v C, Q v R or f unct(Q). Let a; b 2 NI and d 2 [0; 1] a fuzzy degree. A fuzzy assertion is of the form: hB(a); > di or hP (a; b); > di: An ABox A is a nite set of fuzzy assertions. A fuzzy DL-Lite-ontology O = (T ; A) consists of a TBox T and an ABox A. Please note that the TBoxes are crisp in our setting. Crisp DL-LiteR-ontologies are a special case of fuzzy ones, where only degrees 1 and 0 are admitted.
The reasoning problem we address here is answering of (unions of) conjunctive queries. Let t1; t2 2 NI [ NV be terms, an atom is an expression of the form: C(t1) or P (t1; t2). Let x and y be vectors over NV, then (x; y) is a conjunction of atoms of the forms A(t1) and P (t1; t2). A conjunctive query (CQ) q(x) over an ontology O is a rst-order formula 9y: (x; y), where x are the answer variables, y are existentially quanti ed variables and the concepts and roles in (x; y) appear in O. Observe, that the atoms in a CQ do not contain degrees. Now, a union of conjunctive queries (UCQ) is simply a nite set of conjunctive queries that have the same number of answer variables.
The semantics of fuzzy DL-LiteR is provided an interpretation with an interpretation domain and a mapping function that assigns values from the unit interval, instead of just 0 and 1 as in the classical case. More precisely, an interpretation for fuzzy DL-LiteR is a pair I = ( I ; I ), where I is as usual, but I is an interpretation function mapping every { a 2 NI to some element aI 2 I , { A 2 NC to a concept membership function AI : I ! [0; 1], { P 2 NR to a role membership function P I : I I ! [0; 1].
The semantics of the complex concepts in fuzzy DL-LiteR is provided via the di erent families of fuzzy logic operators depicted in Table 1 and interpretations. Let ; 0 denote elements of I and denote fuzzy negation (Table 1), then the semantics of concepts and roles are inductively de ned as follows: (9Q)I ( ) = sup 02 I QI ( ; 0) P I ( ; 0) = P I ( 0; )
(:B)I ( ) = (:Q)I ( ; 0) =
BI ( ) An interpretation I satis es B v C i BI ( ) 6 CI ( ) for every 2 I , Q v R i QI ( ; 0) 6 RI ( ; 0) for every ; 0 2 I , and func(Q) i for every 2 I there is a unique 0 2 I such that QI ( ; 0) > 0. An interpretation I is a model of a TBox T , i.e. I j= T , i it satis es all axioms in T . I satis es hB(a); > di i BI (aI ) > d, and hP (a; b); > di i P I (aI ; bI ) > d. I is a model of an ABox A, i.e. I j= A, i it satis es all assertions in A. Finally an interpretation I is a model of an ontology O = (T ; A) i it is a model of A and T .
Given a CQ q(x) = 9y: (x; y), an interpretation I, a vector of individuals with the same arity as x, we de ne the mapping that maps: i) each individual a to aI , ii) each variable in x to an element of I , and iii) each variable in y to an element 2 I . Suppose that for an interpretation I, is the set of mappings that comply to these three conditions. Computing the t-norm of all atoms: AI ( (t1)) and P I ( (t1); (t2)) yields the degree of I ( I ; (y)). A tuple of individuals is a certain answer to q(x), over O, with a degree greater or equal than d (denoted O j= q( ) > d), if for every model I of O: qI ( I ) = sup 2 f I ( ; (y))g > d: We denote the set of certain answers along with degrees, to a query q(x) w.r.t. an ontology O with ans(q(x); O): ans(q(x); O) = f( ; d) j O j= q( ) > d ^ 6 9d0:d0 > d ^ O j= q( ) > d0g: To illustrate the use of the fuzzy DL-LiteR language and queries, we provide an example from our application domain.
Example 1. The ontology Oex for our running example consists of: Tex := fServer v 9hasCPU; 9hasCPU v CPU; func(hasCPU )g Aex := fhServer(server1); > 1i; hhasCPU(server1; cpu1); > 1i; hOverUsed(cpu1); > 0:6i; hhasCPU(server1; cpu2); > 1i; hOverUsed(cpu2); > 0:8i g The rst two axioms in Tex state that each server has a part that is a CPU. The third one states that no CPU can belong to more than one server. Aex provides information about the connections between servers and CPUs and each CPU's degree of overuse. To query the ontology Oex we can formulate the queries: q1(x; y) = hasCPU(x; y) ^ OverUsed(y)
q2(x) = 9y hasCPU(x; y) ^ OverUsed(y) The query q1 asks for pairs of Servers and CPUs with an overused CPU. The query q2 asks for Servers, where the Server's CPU is overused. If conjunction and negation are interpreted as the Godel family of operators, the certain answers w.r.t. Oex are: ans(q1(x; y); Oex) = f(server1; cpu1; 0:6); (server2; cpu2; 0:8)g
ans(q2(x); Oex) = f(server1; 0:8)g: 3
In the following we are interested in answering the CQ q(x), which is formulated
over the vocabulary of the DL-LiteR ontology O = (T ; A). The main idea
underlying the classic DL-LiteR query answering algorithm is to rewrite the query
q(x) with the information from the TBox T into a UCQ qT (x) and then apply
this UCQ to the ABox A alone [
To explain the algorithm we anneedd t h.eIntpurietidvieclayt,eseacAhf b,inParfy, TBox Fuzz?yQuery Fuzzy ABox predicate Af is an extension of the concept A such that the fuzzy concept assertion hA(a); > di is Query rewriting equivalent to the predicate asser- by tion Af (a; d) (similarly for Pf ). Query The n-ary predicate is needed FLite evabluyaation to realize the semantics of the Reasoner SQL query fuzzy conjunction within a CQ. engine More precisely, it 'combines' the Query rewriting membership degrees obtained for tocotrnenaetcftuozrzsy the conjuncts to yield the membership degree of the conjunction. Thus, for each tuple of de- Answers grees d1; : : : ; dn 2 [0; 1] such that d1 = (d2; : : : ; dn), we have that Fig. 1. The FLite rewriting procedure. (d1; : : : ; dn) 2 .
For the CQ q(x) to be answered, the two-step rewriting algorithm proceeds as follows: 1. The crisp DL-LiteR algorithm rewrites q(x) to qT (x) using the information from the TBox. 2. The fuzzy query qT ;f (x; xd) is computed from qT (x) by replacing atoms of the form A(t1) and P (t1; t2) by Af (t1; yd) and Pf (t1; t2; yd), where the variable yd is a degree variable. Its purpose is to retrieve the degree of an assertion. The degree value for fuzzy conjunction is retrieved by the predicate and (to be) stored in the additional degree variable xd. Thus, the conjunction degree of a new atom qT ;f (x; xd) is obtained by the predicate (xd; y1; : : : ; yn), where yi is a degree variable in the ith atom of the CQ. 3. The query is evaluated over the ABox and the actual computation of the degree values takes place. Now, for a tuple of individuals and degrees d1; d2 2 [0; 1], if ( ; d1) and ( ; d2) are both answers to the query, only the answer with the higher degree is returned.
Note that this description abstracts from the ABox A being implemented by a
relational database D and a mapping M. We see in Section 3.1 how this mapping
is extended to incorporate fuzzy information. For a detailed presentation of the
algorithms, the reader may refer to [
Example 2. We return to Example 1 and illustrate the application of the algorithm to the queries. Initially, q1 and q2 are rewritten to the following UCQs: q1Tex (x; y) =fhasCPU(x; y) ^ OverUsed(y)g
q2Tex (x) =f9y:hasCPU(x; y) ^ OverUsed(y)g In the next step, the algorithm extends the queries with degree variables and atoms, so that the corresponding degrees can be returned: q1fTex (x; y; xd) =fhasCPU(x; y; yd1 ) ^ OverUsed(y; yd2 ) ^ q2fTex (x; xd) =f9y:hasCPU(x; y; yd1 ) ^ OverUsed(y; yd2 ) ^ (xd; yd1 ; yd2 )g (xd; yd1 ; yd2 )g For the ABox Aex the following set of answers to each of the queries are returned: ans(q1fTex (x; xd); Aex) =f(server1; cpu1; 0:6); (server1; cpu2; 0:8)g ans(q2fTex (x; xd); Aex) =f(server1; 0:8)g:
The limitations of our pragmatic approach are explained in [
M : SQL SELECT Statements ! ABox assertions: In order to embed fuzzy information into mappings we adopt a rei cation approach sketched in the following example.
Example 3. We consider a fuzzy mapping described in the Quest syntax [
AS p o p u l a r i t y d e g r e e
FROM v i d e o s Now, a video with an id of 12 and a popularity of 0:8 in the database corresponds to hPopularVideo(videos12); > 0:8i stated in the ontology.
The function fuzzy(column, degree) is a marker for the FLite parser to recognize such fuzzy statements. It indicates that each element of the particular column (or SQL expression) is associated with a membership degree. Such a degree is either a column with values from [0; 1], or an SQL expression corresponding to a fuzzy membership function. SQL expressions that contain the fuzzy marker function appear in the initial mapping M and in qT (x) queries, while in qT ;f (x; xd) queries these markers are converted to SQL expressions that return the membership degrees. 4
A Situation Recognition Application. The project \Highly Adaptive Energye cient Computing" (HAEC) investigates complex computing environments that are highly energy-e cient while compromising utility of services as little as possible. In order to be adaptive, the system needs to trigger adaptations (of hard- or software components), if the quality of the requested services or their number changes. To provide such a trigger mechanism we investigate an ontology-based situation recognition. The situations to be recognized are modelled as conjunctive queries. The background information on the system is captured in the TBox and the current system's state is captured by an ABox. Such 3 The FLite reasoner is available from the following Git: https://iccl-share.inf.tudresden.de/ ite-developer/ ite.git
ABoxes are automatically generated from sensor data and other systems information and the conjunctive queries for the situations are evaluated. In such a setting the numerical sensor data need to be mapped to coarser, symbolic categories and membership degrees. Similarly, the query needs to be able to retrieve individuals that ful ll the conditions of the query to a degree. We have built a TBox and a collection of ABoxes and queries for this application.
We took this application to conduct a study of the performance of FLite. The background knowledge on hard- and software components of the HAEC system is modeled in a TBox which consists of 197 GCIs, 168 named classes and 38 roles (415 axioms in total). Each state of the HAEC system is stored in tables of a relational database, which store the information on the soft- and hardware of the HAEC system. The tables contain numerical values for boards, processes, requests, etc.4 Our test compares the run-time to answer (fuzzy) conjunctive queries over TBox and ABox by Ontop and FLite. In contrast to Ontop which requires a crisp mapping, FLite is using a partially fuzzy mapping.
FLite was evaluated over a series of databases of increasing size, i.e., scaled
by a factor k. The initial database with a size of 768.0 KiB was scaled by k
in the range of 100 to 105 to about 13 GiB by the Virtual Instance Generator
(VIG) [
Figure 2 shows the query execution time for increasing database size of Ontop with a crisp mapping compared to three variants of FLite (with Godel t-norms and with fuzzy mapping): naive, optimization SR and optimization PD. Where SR means self join removal from the SQL statement and PD the precomputation of membership degrees in the database.
Optimization SR shows run-time reduction up to a linear factor of about thousand, afterwards it converges with the naive FLite implementation. Thus, 4 The les necessary to perform this benchmark can be found here: https://icclshare.inf.tu-dresden.de/erikzenker/ ite-benchmark.git optimizations for larger databases are necessary. Optimization PD in Figure 2 shows opposite behavior, resulting in a run-time reduction from a scale factor of thousand. Finally, a combination of both reduces the run-time on all scale factors and is even on the same level with Ontop up to a scale factor of thousand. Thus, a query execution time with a at linear run-time overhead with respect to Ontop is possible when the fuzzy rewriting is optimized and fuzzy translation functions are replaced by fuzzy computed columns.
Instead of comparing FLite with Ontop, a comparison with other fuzzy
DL reasoners would have been desirable. However, reasoners such as LiFR [
In temporal OBDA, one is not restricted to the knowledge about a single moment in time in a single ABox, but a sequence of ABoxes A0; : : : ; An. A stream of data can be transformed into such a sequence by sampling the stream periodically and storing data together with a timestamp in a database. Such a complex entry in the database corresponds to an assertion in the ABox Ai. This data can be used to recognize global contexts, through temporal fuzzy conjunctive queries (TFCQs), which refer to several point in time as well as to fuzzy information. A context-aware system is then able to subscribe and to transform data streams into a sequence of ABoxes and to evaluate a set of TFCQs periodically. 5.1
To accommodate the new information, we extend the notions of knowledge base, interpretation, and CQ to the temporal case. A temporal knowledge base (TKB) K = hO; (Ai)0 i ni consists of an ontology O and a nite sequence of ABoxes Ai. Let I = (Ii)i 0 be an in nite sequence of interpretations Ii = ( ; Ii ) over a non-empty domain that is xed (constant domain assumption). Then, I is a model of K (written I j= K) if { for all i { for all i, 0 0, we have Ii j= O; and
i n, we have Ii j= Ai.
We next describe our query language, which allows to place LTL operators `around' classical conjunctive queries. Temporal conjunctive queries (TCQs) are built from CQs as follows: (1) Every CQ is a TCQ and (2) If 1 and 2 are TCQs, then the following are also TCQs: { 1 ^ 2 (conjunction), 1 _ 2 (disjunction), { # 1 (next), # 1 (previous), { 1 U< 2 (until), 1 S 2(since), { 2 1 (always), and 2 1 (always in the past).
(a( ))I;i
As usual, we use the abbreviation 3 1 (eventually) for true U 1; and, analogously for the past, 3 1, for true S 1.
The answers to TCQs are mappings from the variables and individual names occurring in the query to elements of the domain of a given interpretation. We start by de ning the semantics of CQs for Boolean queries as usual, through the notion of homomorphisms. Let (x) = 9y: 0(x; y) be a CQ, a = (a1; : : : ; am) be a tuple of individual names, of same arity as the tuple x, and I = ( I ; I ) be an interpretation. A mapping from the variables and individual names that occur in to the elements of I is a homomorphism of (a1; : : : ; am) into I if { (xi) = (ai), for all 1 i m; { (a) = aI , for all individual names a occurring in ; { (t) 2 AI , for all concept atoms A(t) in ; and { ( (t1); (t2)) 2 RI , for all role atoms R(t1; t2) in .
Let now be a TCQ, a be a mapping from the distinguished variables in to individual names, and I = (Ii)i 0 be an in nite sequence of interpretations. We de ne the satisfaction relation I; i j= a( ) by induction on the structure of based on Table 5.1; that is, I; i modelsha( ); di i (a( ))I;i d. Given a TKB K, we say that a is a certain answer to w.r.t. K at time point i, written K; i j= a( ), if we have I; i j= a( ), for all models I of K. 5.2
Our algorithm to answer a TFCQ on fuzzy and temporal data is again a modi ed OBDA approach, which rewrites the given query into a standard database query. Here the rewritten query encodes the relevant ontological knowledge, the temporal conditions, and the membership variables, but addresses a general database. The algorithm to rewrite TFCQs is based on the following rewriting approach:
Assume, a TFCQ t in TSPARQL is given, then the procedure SQLif y( t) rewrites t into a SQL query (see Algorithm 1). First the algorithm stores the nested list of LTL-operators as they appear in the input TFCQ t. Then the algorithm is applied to each sub-TFCQ in t recursively until the considered subquery is a plain CQ. This CQ then undergoes the two-step rewriting procedure described in Section 3: rst the CQ is extended by information from the ontology and then fuzzi ed by adding the membership degrees and degree variables to generate the corresponding membership degrees from the data. Subsequently, the extended and fuzzi ed CQs are recombined according to the nested list of temporal operators stored in the beginning.
Algorithm 1 TFCQ to SQL rewriting
Consider the query: t = (# 1 ^(# # 2)) S 3. Recall that the function
SQLif y separates the temporal operators and thus splits the given query. As an
example, we regard the rewriting SQLif y(# 1). Since 1 is a plain CQ, it is
extended and fuzzi ed as outlined above. The nal rewriting obtained from the
call SQLif y( t; T ) can then be evaluated over a common relational database,
and the obtained answers represent the answers to the query t w.r.t. T , with
respect to fuzzy data.
The idea for an implementation is to reuse existing tools to provide fast and e
cient query answering even over large datasets. Techniques developed in FLite
for fast query answering on fuzzy ontologies and in QuAnTOn [
0 1 1 0 0 0 1 1 1 0 0 0 10 S01tream01s 01 1 0 0 0 1 1 1 1 0 1 1 1 0ABo0x gen1erato0r Sequence of ABoxes
TCQ +
Degree Ontology
Timestamp
Separate Temporal
Operators from
Query We have presented a pragmatic approach for answering (temporal) fuzzy conjunctive queries over (sequences of) fuzzy ABoxes and with respect to DL-LiteRontologies. Our approach uses separate rewriting steps to incorporate ontological, fuzzy and temporal information. This allows to make use of standard query rewriting engines for the rst step. Although described here for DL-LiteR, our approach can be extended to other DLs that enjoy FOL rewritability. We have implemented our approach in the FLite system and evaluated it against the Ontop reasoner for ABoxes of varying size. Our evaluation gave evidence that there is a substantial, albeit almost only linear increase of run-time for large ABoxes, when fuzzy information is queried. Furthermore, we presented an approach for temporal fuzzy query answering, which combines two rewriting-based query answering algorithms. A thorough investigation of this subject remains future work. 20. T. Venetis, G. Stoilos, and G. Stamou. Query Extensions and Incremental Query Rewriting for OWL 2 QL Ontologies. Journal on Data Semantics, pages 1{23, 2014.