Towards Temporal Fuzzy Query Answering on Stream-based Data? Anni-Yasmin Turhan1 and Erik Zenker2 1 Department of Computer Science, University of Oxford, UK 2 Institute for Theoretical Computer Science, Technische Universität Dresden, Germany Abstract. For reasoning over streams of data ontology-based data ac- cess 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 stream- based applications the classical expressivity of DL-Lite lacks means to handle fuzzy and temporal information. In this paper we report on a com- bination 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 answer- ing over temporal fuzzy DL-Lite-ontologies. 1 Introduction 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 sit- uation recognition. The main task in context-aware or self-adaptive systems is to recognize situ- ations 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 of- fers 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 po- tentially a huge amount of such preprocessed data has to be queried, efficient 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 first or- der queries, to recognize critical situations. It is well-known that DL-Lite-family of allows for answering of CQs in LogSpace [2, 7, 6], which is the same complexity ? Partially supported by DFG in the Collaborative Research Center 912 “Highly Adaptive Energy-Efficient Computing”. as answering database queries. This good complexity is achieved by the so-called rewriting approach, where the CQ is first enriched by the (relevant) information from the TBox and then this rewritten query is evaluated over a data base. The rewriting approach for answering CQs is implemented in optimized systems as QuOnto2 [1, 11], Ontop [13], Owlgres [14], and IQAROS [20] which perform well in practice. Now, in context-aware systems that employ streams of sensor data, the ex- pressivity of standard ontology languages often might be too limited. For in- stance, 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 (with- out 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 [5] and implemented [17]. In this setting the incoming information is modeled as a sequence of fact bases, one for each moment in time in which the system has been observed and thus realizing the sliding window approach. To describe situations, operators of the temporal logic LTL are admitted in the query. Such temporal operators can, for instance, express for a property that it is true at the next point in time or to be satisfied at some point in future. In this rewriting approach the temporal information queried for is treated by an additional rewriting step of the temporal query and the information is also retrieved by a query over the temporal database. Now, as it turns out both two-step rewriting methods can be combined in a straightforward, but elegant way. Yielding a method that is capable to answer CQs over temporal sequences that model data in a fuzzy way. 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 per- formance evaluation of FLite on a situation recognition use-case. Conclusions and future work end the paper in Section 6. 2 Preliminaries We start with the concept language of DL-Lite R 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-Lite R -concepts, -roles and -queries are constructed. DL-Lite R -concepts and -roles are defined according to the following grammar: B →A | ∃Q C →> | B | ¬B Q →P | P − R →Q | ¬Q, where > is the top concept, A ∈ NC , P ∈ NR . Based on these kinds of complex concepts and roles, a DL-LiteR TBox T is a finite set of axioms of the form: B v C, Q v R or f unct(Q). Let a, b ∈ NI and d ∈ [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 finite 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-Lite R -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) conjunc- tive queries. Let t1 , t2 ∈ 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 conjunc- tion of atoms of the forms A(t1 ) and P (t1 , t2 ). A conjunctive query (CQ) q(x) over an ontology O is a first-order formula ∃y.φ(x, y), where x are the answer variables, y are existentially quantified 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 finite set of conjunctive queries that have the same number of answer variables. The semantics of fuzzy DL-Lite R is provided an interpretation with an in- terpretation 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-Lite R is a pair I = (∆I , ·I ), where ∆I is as usual, but ·I is an interpretation function mapping every – a ∈ NI to some element aI ∈ ∆I , – A ∈ NC to a concept membership function AI : ∆I → [0, 1], – P ∈ NR to a role membership function P I : ∆I × ∆I → [0, 1]. The semantics of the complex concepts in fuzzy DL-Lite R is provided via the different 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 defined as follows: (∃Q)I (δ) = supδ0 ∈∆I QI (δ, δ 0 ) (¬B)I (δ) = B I (δ) >I (δ) = 1 P −I (δ, δ 0 ) = P I (δ 0 , δ) (¬Q)I (δ, δ 0 ) = QI (δ, δ 0 ) Table 1. Families of fuzzy logic operators. Family t-norm d⊗e negation d implication α ⇒ e ( ( 1, d = 0 1, d 6 e Gödel min(d, e) 0, d > 0 e, d > e Lukasiewicz max(d + e − 1, 0) 1−d min(1 − d + e, 1) ( ( 1, d = 0 1, d6e Product d×e 0, d > 0 e/d, d > e An interpretation I satisfies B v C iff B I (δ) 6 C I (δ) for every δ ∈ ∆I , Q v R iff QI (δ, δ 0 ) 6 RI (δ, δ 0 ) for every δ, δ 0 ∈ ∆I , and func(Q) iff for every δ ∈ ∆I there is a unique δ 0 ∈ ∆I such that QI (δ, δ 0 ) > 0. An interpretation I is a model of a TBox T , i.e. I |= T , iff it satisfies all axioms in T . I satisfies hB(a), > di iff B I (aI ) > d, and hP (a, b), > di iff P I (aI , bI ) > d. I is a model of an ABox A, i.e. I |= A, iff it satisfies all assertions in A. Finally an interpretation I is a model of an ontology O = (T , A) iff it is a model of A and T . Given a CQ q(x) = ∃y.φ(x, y), an interpretation I, a vector of individuals α with the same arity as x, we define 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 δ ∈ ∆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 |= q(α) > d), if for every model I of O: q I (αI ) = supπ∈Π {φI (α, π(y))} > 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) = {(α, d) | O |= q(α) > d ∧ 6 ∃d0 .d0 > d ∧ O |= q(α) > d0 }. To illustrate the use of the fuzzy DL-Lite R language and queries, we provide an example from our application domain. Example 1. The ontology Oex for our running example consists of: Tex := {Server v ∃hasCPU, ∃hasCPU− v CPU, func(hasCPU− )} Aex := {hServer(server1 ), > 1i, hhasCPU(server1 , cpu1 ), > 1i, hOverUsed(cpu1 ), > 0.6i, hhasCPU(server1 , cpu2 ), > 1i, hOverUsed(cpu2 ), > 0.8i } The first 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) = ∃y 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 Gödel family of operators, the certain answers w.r.t. Oex are: ans(q1 (x, y), Oex ) = {(server1 , cpu1 , 0.6), (server2 , cpu2 , 0.8)} ans(q2 (x), Oex ) = {(server1 , 0.8)}. 3 Fuzzy Query Answering by Extended Crisp Rewritings In the following we are interested in answering the CQ q(x), which is formulated over the vocabulary of the DL-Lite R ontology O = (T , A). The main idea un- derlying the classic DL-Lite R 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 [7, 2]. For fuzzy DLs we extend this approach to handle degrees of ABox assertions. The main idea is depicted in Figure 1. To explain the algorithm we ? need the predicates Af , Pf , TBox Fuzzy Query Fuzzy ABox and Φ⊗ . Intuitively, each binary 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 evaluation The n-ary predicate Φ⊗ is needed FLite by a to realize the semantics of the Reasoner SQL query fuzzy conjunction within a CQ. engine More precisely, it ’combines’ the Query rewriting to treat fuzzy membership degrees obtained for connectors the conjuncts to yield the mem- bership degree of the conjunc- tion. Thus, for each tuple of de- Answers grees d1 , . . . , dn ∈ [0, 1] such that d1 = ⊗(d2 , . . . , dn ), we have that Fig. 1. The FLite rewriting procedure. (d1 , . . . , dn ) ∈ Φ⊗ . For the CQ q(x) to be answered, the two-step rewriting algorithm proceeds as follows: 1. The crisp DL-Lite R 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 predi- cate Φ⊗ 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 ∈ [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 [9]. Example 2. We return to Example 1 and illustrate the application of the algo- rithm to the queries. Initially, q1 and q2 are rewritten to the following UCQs: q1 Tex (x, y) ={hasCPU(x, y) ∧ OverUsed(y)} q2 Tex (x) ={∃y.hasCPU(x, y) ∧ OverUsed(y)} In the next step, the algorithm extends the queries with degree variables and atoms, so that the corresponding degrees can be returned: q1 fTex (x, y, xd ) ={hasCPU(x, y, yd1 ) ∧ OverUsed(y, yd2 ) ∧ Φ⊗ (xd , yd1 , yd2 )} q2 fTex (x, xd ) ={∃y.hasCPU(x, y, yd1 ) ∧ OverUsed(y, yd2 ) ∧ Φ⊗ (xd , yd1 , yd2 )} For the ABox Aex the following set of answers to each of the queries are returned: ans(q1 fTex (x, xd ), Aex ) ={(server1 , cpu1 , 0.6), (server1 , cpu2 , 0.8)} ans(q2 fTex (x, xd ), Aex ) ={(server1 , 0.8)}. The limitations of our pragmatic approach are explained in [9]. To sum up, this pragmatic approach yields sound and complete results for fuzzy semantics based on idempotent operators such as the Gödel family of operators. Non- idempotent operators may be simplified by highly optimized implementations such as Ontop. Consider qT (x) := A(x) ∧ A(x) is simplified to qT (x) := A(x), which is correct for crisp, but not for every fuzzy semantics. The correctness for the case of the Gödel family of operators can be derived from the crisp DL-Lite R proof along with the following points: (1) only crisp TBox axioms are allowed, (2) conjunctions only appear in conjunctive query expressions, (3) Ontop opti- mizations do not affect the correctness of the algorithm due to the properties of the min operator. The latter does not apply for all other t-norms. The pro- posed methodology is complete but not sound for the Lukasiewicz and Gödel families of operators. Nevertheless, in [9], we devised a method by which each unsound answer can be identified and its correct degree estimated by an interval of membership values. 3.1 The FLite Reasoner Implementation FLite3 (Fuzzy DL-Lite R query engine) implements the above query answering algorithm and builds on the Ontop framework [13]. Implementation-wise, the rewriting procedure is a little more involved if a reasoner such as Ontop is deployed, since it operates on relational databases directly. Thus the queries qT (x) and qT ,f (x, xd ) in Figure 1 are SQL queries, while the ABox A is only virtual and implemented by a partial mapping: M : SQL SELECT Statements → ABox assertions. In order to embed fuzzy information into mappings we adopt a reification ap- proach sketched in the following example. Example 3. We consider a fuzzy mapping described in the Quest syntax [12]. In this mapping, for the concept popularVideo each id of the table videos is annotated with a popularity, i.e. a fuzzy degree: t a r g e t haec : v i d e o { p o p u l a r i t y d e g r e e } a haec : PopularVideo . s o u r c e SELECT f u z z y ( id , p o p u l a r i t y ) AS popularity degree FROM videos 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 func- tion 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 mem- bership degrees. 4 Performance Test of FLite A Situation Recognition Application. The project “Highly Adaptive Energy- efficient Computing” (HAEC) investigates complex computing environments that are highly energy-efficient 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 mod- elled as conjunctive queries. The background information on the system is cap- tured 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.tu- dresden.de/flite-developer/flite.git avg. query execution time [m 1x106 Ontop 100000 FLite naive Optimization SR 10000 Optimization PD 1000 Optimization SR+PD 100 10 1 1 10 100 1000 10000 100000 database scale factor k Fig. 2. Ontop is compared to optimized FLite versions SR, PD, and SR+PD. All setups were executed over a CQ with 13 atoms. ABoxes are automatically generated from sensor data and other systems infor- mation and the conjunctive queries for the situations are evaluated. In such a setting the numerical sensor data need to be mapped to coarser, symbolic cate- gories and membership degrees. Similarly, the query needs to be able to retrieve individuals that fulfill 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) [8]. For each of these scaled databases, a query with 13 atoms (2 crisp concepts, 7 fuzzy concepts, 4 crisp roles) in total was evaluated. The system on which the benchmark was performed on is powered by an Intel Core i7 2.6 GHz processor and was equipped with 8 GB DDR 1600 main memory. ABox information was stored in a MySQL 5.6.23 database. FLite and Ontop are executed on Oracle the JVM 1.7. Figure 2 shows the query execution time for increasing database size of On- top with a crisp mapping compared to three variants of FLite (with Gödel 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 pre- computation 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 files necessary to perform this benchmark can be found here: https://iccl- share.inf.tu-dresden.de/erikzenker/flite-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 flat 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 [19], FuzzyDL [4], FiRE [15], and DeLorean [3] support only instance queries instead of conjunctive queries. Others such as the DL-Lite reasoner Ontosearch2 [10] or SoftFacts [16] could either not be obtained or installed. 5 Towards Temporal Fuzzy Query Answering on Streams 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 Introducing Temporal Query Answering 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≤n i consists of an ontology O and a finite sequence of ABoxes Ai . Let I = (Ii )i≥0 be an infinite sequence of interpretations Ii = (∆, ·Ii ) over a non-empty domain ∆ that is fixed (constant domain assumption). Then, I is a model of K (written I |= K) if – for all i ≥ 0, we have Ii |= O; and – for all i, 0 ≤ i ≤ n, we have Ii |= 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 A CQ ψ (a(ψ))Ii φ1 ∧ φ2 (aφ1 (φ1 ))I,i ⊗(aφ2 (φ2 ))I,i φ1 ∨ φ2 (aφ1 (φ1 ))I,i ⊕(aφ2 (φ2 ))I,i #φ1 If i < n, then (a(φ1 ))I,i+1 , else 0. − # φ1 If i > 0, then (a(φ1 ))I,i−1 , else 0. 2φ1 ⊗{(a(φ1 ))I,k | i ≤ k ≤ n} − 2 φ1 ⊗{(a(φ1 ))I,k | 0 ≤ k ≤ i} φ1 U φ2 supk,i≤k≤n ⊗{(aφ2 (φ2 ))I,k , (aφ1 (φ1 ))I,j | i ≤ j < k} φ1 S φ2 supk,0≤k≤i ⊗{(aφ2 (φ2 ))I,k , (aφ1 (φ1 ))I,j | k < j ≤ i} Table 2. The semantics of TCQs. As usual, we use the abbreviation 3φ1 (eventually) for true U φ1 ; and, analo- gously 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 defining the semantics of CQs for Boolean queries as usual, through the notion of homomorphisms. Let ψ(x) = ∃y.ψ 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) ∈ AI , for all concept atoms A(t) in ψ; and – (π(t1 ), π(t2 )) ∈ 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 infinite sequence of interpretations. We define the satisfaction relation I, i |= a(φ) by induction on the structure of φ based on Table 5.1; that is, I, i modelsha(φ), di iff (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 |= a(φ), if we have I, i |= a(φ), for all models I of K. 5.2 An Algorithm for Answering TFCQs Our algorithm to answer a TFCQ on fuzzy and temporal data is again a modified OBDA approach, which rewrites the given query into a standard database query. Here the rewritten query encodes the relevant ontological knowledge, the tempo- ral 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 sub- query is a plain CQ. This CQ ψ then undergoes the two-step rewriting procedure described in Section 3: first the CQ is extended by information from the ontol- ogy and then fuzzified by adding the membership degrees and degree variables to generate the corresponding membership degrees from the data. Subsequently, the extended and fuzzified CQs are recombined according to the nested list of temporal operators stored in the beginning. Algorithm 1 TFCQ to SQL rewriting 1: function SQLify(φt , T ) 2: φ0 ← ∅ 3: t0 ← temporal−operators(φt ) . Store nested list of temporal LTL-operators 4: for all CQs φ in TCQ φt do 5: if φ contains temporal operator then 6: φ0 ← append(φ0 , SQLif y(φ, T )) . Append a rewritten TFCQ to φ0 7: else 8: φT ← extend(φ, T ) . Extends φ by information from T 9: φfT ← f uzzif y(φT ) . Annotate φT with fuzzy information 10: φ0 ← append(φ0 , φfT )) . Append the fuzzyfied CQ to φ0 11: end if 12: end for 13: φt,f 0 0 T ← temporalize(φ , t ) . Reintroduce LTL-operators from list into list of rewritten queries 14: return φt,fT 15: end function 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 fuzzified as outlined above. The final 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. 5.3 Towards an Implementation The idea for an implementation is to reuse existing tools to provide fast and effi- cient query answering even over large datasets. Techniques developed in FLite for fast query answering on fuzzy ontologies and in QuAnTOn [17] for temporal OBDA need to be combined in a single application, which allows for temporal OBDA over fuzzy data. Furthermore, an ABox generator needs to transform streaming data into the sequence of ABoxes, each with fuzzy information. An overview of the idea of such a system is given in Figure 3. The system input consists of (i) (possibly fuzzy) data referencing different time points, (ii) a pair (φt , d) containing a TFCQ φt and a degree d, and (iii) an ontology. The sys- tem then rewrites the query as described in the previous section and evaluates the rewritten query, φf,t T , over a MySQL database. This evaluation yields a set of answer tuples with corresponding degrees. The system then returns those of these answers whose degree is ≥ d. 001011100 100100110 110100111 010010110 Streams Timestamp ABox generator Sequence of ABoxes SQL Engine Answers TCQ + Degree SQL Query Separate Temporal Operators from Reintroduce Query Temporal Operators by QuAnTOn Ontology ... ... Add Query Rewriting to Membership SQL by Degrees by ... ... FLite Fig. 3. Schema of the implementation for temporal fuzzy query answering. 6 Conclusions We have presented a pragmatic approach for answering (temporal) fuzzy con- junctive queries over (sequences of) fuzzy ABoxes and with respect to DL-Lite R - ontologies. Our approach uses separate rewriting steps to incorporate ontologi- cal, fuzzy and temporal information. This allows to make use of standard query rewriting engines for the first step. Although described here for DL-Lite R , 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 ap- proach for temporal fuzzy query answering, which combines two rewriting-based query answering algorithms. A thorough investigation of this subject remains future work. References 1. A. Acciarri, D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, M. Palmieri, and R. Rosati. QUONTO: Querying Ontologies. In AAAI, pages 1670–1671, 2005. 2. A. Artale, D. Calvanese, R. Kontchakov, and M. Zakharyaschev. The DL-Lite Family and Relations. Journal of artificial intelligence research, 36(1):1–69, 2009. 3. F. Bobillo, M. Delgado, and J. Gómez-Romero. Reasoning in Fuzzy OWL 2 with DeLorean. In Uncertainty Reasoning for the Semantic Web II, pages 119–138. 2013. 4. F. Bobillo and U. Straccia. fuzzyDL: An Expressive Fuzzy Description logic Rea- soner. In FUZZ-IEEE, pages 923–930, 2008. 5. S. Borgwardt, M. Lippmann, and V. Thost. Temporalizing rewritable query lan- guages over knowledge bases. Journal of Web Semantics, 2015. In press. 6. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, A. Poggi, M. Rodriguez- Muro, and R. Rosati. Ontologies and Databases: The DL-Lite Approach. 2009. 7. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Fam- ily. Journal of Automated reasoning, 39, 2007. 8. D. Lanti, M. Rezk, M. Slusnys, G. Xiao, and D. Calvanese. The NPD Benchmark for OBDA Systems. In 10th International Workshop on Scalable Semantic Web Knowledge Base Systems (SSWS 2014), page 3, 2014. 9. T. Mailis and A.-Y. Turhan. Employing DL-LiteR -Reasoners for Fuzzy Query Answering. In Proceedings of the 4th Joint International Semantic Technology Conference (JIST2014), LNCS, 2014. 10. J. Z. Pan, E. Thomas, and D. Sleeman. Ontosearch2: Searching and querying web ontologies. Proc. of WWW/Internet, 2006:211–218, 2006. 11. A. Poggi, M. Rodriguez, and M. Ruzzi. Ontology-based database access with DIG- Mastro and the OBDA Plugin for Protégé. In Proc. of OWLED, 2008. 12. M. Rodriguez-Muro, J. Hardi, and D. Calvanese. Quest: Efficient SPARQL-to-SQL for RDF and OWL. In 11th International Semantic Web Conference ISWC 2012, page 53, 2012. 13. M. Rodriguez-Muro, R. Kontchakov, and M. Zakharyaschev. Ontology-Based Data Access: Ontop of Databases. In International Semantic Web Conference (1), vol- ume 8218 of LNCS, pages 558–573. Springer, 2013. 14. M. Stocker and M. Smith. Owlgres: A Scalable OWL Reasoner. In OWLED, volume 432, 2008. 15. G. Stoilos, N. Simou, G. Stamou, and S. Kollias. Uncertainty and the Semantic Web. Intelligent Systems, 21(5):84–87, 2006. 16. U. Straccia. SoftFacts: A Top-k Retrieval Engine for Ontology Mediated Access to Relational Databases. In Systems Man and Cybernetics (SMC), 2010 IEEE International Conference on, pages 4115–4122. IEEE, 2010. 17. V. Thost, J. Holste, and O. Özçep. On implementing temporal query answering in dl-lite (extended abstract). In Proceedings of the 28th International Workshop on Description Logics (DL-2015), Athens, Greece, 2015. CEUR Workshop Proceed- ings. 18. V. Thost, J. Holste, and Özgür Özçep. On implementing temporal query answer- ing in DL-Lite. LTCS-Report 15-12, Chair for Automata Theory, TU Dresden, Germany, 2015. See http://lat.inf.tu-dresden.de/research/reports.html. 19. D. Tsatsou, S. Dasiopoulou, I. Kompatsiaris, and V. Mezaris. LiFR: A Lightweight Fuzzy DL Reasoner. In The Semantic Web: ESWC 2014 Satellite Events, pages 263–267. 2014. 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.