More Web Proxy on the site http://driver.im/

article

Querying log data with metric temporal logic

Authors:

Sebastian Brandt,

Elem Güzel Kalayci,

Vladislav Ryzhikov,

Michael ZakharyaschevAuthors Info & Claims

Journal of Artificial Intelligence Research, Volume 62, Issue 1

Pages 829 - 877

https://doi.org/10.1613/jair.1.11229

Published: 01 May 2018 Publication History

Abstract

We propose a novel framework for ontology-based access to temporal log data using a datalog extension datalogMTL of the Horn fragment of the metric temporal logic MTL. We show that datalogMTL is EXPSPACE-complete even with punctual intervals, in which case full MTL is known to be undecidable. We also prove that nonrecursive datalogMTL is PSPACE-complete for combined complexity and in AC⁰ for data complexity. We demonstrate by two real-world use cases that nonrecursive datalogMTL programs can express complex temporal concepts from typical user queries and thereby facilitate access to temporal log data. Our experiments with Siemens turbine data and MesoWest weather data show that datalogMTL ontology-mediated queries are efficient and scale on large datasets.

References

[1]

Abiteboul, S., Hull, R., & Vianu, V. (1995). Foundations of Databases. Addison-Wesley.

Digital Library

[2]

Alur, R., Feder, T., & Henzinger, T. A. (1996). The benefits of relaxing punctuality. J. ACM, 43(1), 116-146.

Digital Library

[3]

Alur, R., & Henzinger, T. A. (1993). Real-time logics: Complexity and expressiveness. Inf. Comput., 104(1), 35-77.

Digital Library

[4]

Armbrust, M., Xin, R. S., Lian, C., Huai, Y., Liu, D., Bradley, J. K., Meng, X., Kaftan, T., Franklin, M. J., Ghodsi, A., & Zaharia, M. (2015). Spark SQL: relational data processing in spark. In Sellis, T. K., Davidson, S. B., & Ives, Z. G. (Eds.), Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015, pp. 1383-1394. ACM.

Digital Library

[5]

Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach (1st edition). Cambridge University Press, New York, USA.

Digital Library

[6]

Artale, A., Kontchakov, R., Wolter, F., & Zakharyaschev, M. (2013). Temporal description logic for ontology-based data access. In Proc. of the 23rd Int. Joint Conf. on Artificial Intelligence, IJCAI 2013. IJCAI/AAAI.

Digital Library

[7]

Artale, A., Kontchakov, R., Kovtunova, A., Ryzhikov, V., Wolter, F., & Zakharyaschev, M. (2015). First-order rewritability of temporal ontology-mediated queries. In Proc. of the 24th Int. Joint Conf. on Artificial Intelligence, IJCAI 2015, pp. 2706-2712. IJCAI/AAAI.

Digital Library

[8]

Artale, A., Kontchakov, R., Kovtunova, A., Ryzhikov, V., Wolter, F., & Zakharyaschev, M. (2017). Ontology-mediated query answering over temporal data: A survey (invited talk). In TIME, Vol. 90 of LIPIcs, pp. 1:1-1:37. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.

[9]

Artale, A., Kontchakov, R., Ryzhikov, V., & Zakharyaschev, M. (2013). The complexity of clausal fragments of LTL. In Logic for Programming, Artificial Intelligence, and Reasoning - 19th International Conference, LPAR-19, Stellenbosch, South Africa, December 14-19, 2013. Proceedings, pp. 35-52.

[10]

Artale, A., Kontchakov, R., Ryzhikov, V., & Zakharyaschev, M. (2014). A cookbook for temporal conceptual data modelling with description logics. ACM Trans. Comput. Log., 15(3), 25:1- 25:50.

Digital Library

[11]

Baader, F., Borgwardt, S., & Lippmann, M. (2013). Temporalizing ontology-based data access. In Proc. of the 24th Int. Conf. on Automated Deduction, CADE-24, Vol. 7898 of LNCS, pp. 330-344. Springer.

Digital Library

[12]

Baudinet, M., Chomicki, J., & Wolper, P. (1993). Temporal deductive databases. In Temporal Databases, pp. 294-320.

[13]

Beck, H., Dao-Tran, M., Eiter, T., & Fink, M. (2015). LARS: A logic-based framework for analyzing reasoning over streams. In Bonet, B., & Koenig, S. (Eds.), Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA., pp. 1431-1438. AAAI Press.

Digital Library

[14]

Bienvenu, M., Kikot, S., Kontchakov, R., Podolskii, V. V., & Zakharyaschev, M. (2018). Ontology-mediated queries: Combined complexity and succinctness of rewritings via circuit complexity. J. ACM. In print.

Digital Library

[15]

Borgwardt, S., Lippmann, M., & Thost, V. (2013). Temporal query answering in the description logic DL-Lite. In Proc. of the 9th Int. Symposium on Frontiers of Combining Systems, FroCoS'13, Vol. 8152 of LNCS, pp. 165-180. Springer.

[16]

Brandt, S., Kalayci, E. G., Kontchakov, R., Ryzhikov, V., Xiao, G., & Zakharyaschev, M. (2017). Ontology-based data access with a horn fragment of metric temporal logic. In Singh, S. P., & Markovitch, S. (Eds.), Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA., pp. 1070-1076. AAAI Press.

Digital Library

[17]

Bresolin, D., Kurucz, A., Muñoz-Velasco, E., Ryzhikov, V., Sciavicco, G., & Zakharyaschev, M. (2017). Horn fragments of the halpern-shoham interval temporal logic. ACM Trans. Comput. Log., 18(3), 22:1-22:39.

Digital Library

[18]

Calvanese, D., Cogrel, B., Komla-Ebri, S., Kontchakov, R., Lanti, D., Rezk, M., Rodriguez-Muro, M., & Xiao, G. (2017). Ontop: Answering SPARQL queries over relational databases. Semantic Web, 8(3), 471-487.

Digital Library

[19]

Chomicki, J., & Toman, D. (1998). Temporal logic in information systems. In Logics for Databases and Information Systems, pp. 31-70. Kluwer.

Digital Library

[20]

Furia, C. A., & Spoletini, P. (2008). Tomorrow and all our yesterdays: MTL satisfiability over the integers. In Fitzgerald, J. S., Haxthausen, A. E., & Yenigün, H. (Eds.), Theoretical Aspects of Computing - ICTAC 2008, 5th International Colloquium, Istanbul, Turkey, September 1-3, 2008. Proceedings, Vol. 5160 of Lecture Notes in Computer Science, pp. 126-140. Springer.

[21]

Gabbay, D., Kurucz, A., Wolter, F., & Zakharyaschev, M. (2003). Many-Dimensional Modal Logics: Theory and Applications, Vol. 148 of Studies in Logic and the Foundations of Mathematics. Elsevier.

[22]

Gottlob, G., Kikot, S., Kontchakov, R., Podolskii, V. V., Schwentick, T., & Zakharyaschev, M. (2014). The price of query rewriting in ontology-based data access. Artif. Intell., 213, 42-59.

Digital Library

[23]

Gutiérrez-Basulto, V., Jung, J., & Kontchakov, R. (2016a). Temporalized EL ontologies for accessing temporal data: Complexity of atomic queries. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI-16). AAAI Press.

Digital Library

[24]

Gutiérrez-Basulto, V., Jung, J. C., & Ozaki, A. (2016b). On metric temporal description logics. In ECAI, Vol. 285 of Frontiers in Artificial Intelligence and Applications, pp. 837-845. IOS Press.

[25]

Gutiérrez-Basulto, V., & Klarman, S. (2012). Towards a unifying approach to representing and querying temporal data in description logics. In Proc. of the 6th Int. Conf. on Web Reasoning and Rule Systems, RR 2012, Vol. 7497 of LNCS, pp. 90-105. Springer.

Digital Library

[26]

Kharlamov, E., Brandt, S., Jiménez-Ruiz, E., Kotidis, Y., Lamparter, S., Mailis, T., Neuenstadt, C., Özçep, Ö. L., Pinkel, C., Svingos, C., Zheleznyakov, D., Horrocks, I., Ioannidis, Y. E., & Möller, R. (2016). Ontology-based integration of streaming and static relational data with optique. In Proc. of the 2016 Int. Conf. on Management of Data, SIGMOD Conference 2016, pp. 2109-2112.

Digital Library

[27]

Kharlamov, E., Mailis, T., Mehdi, G., Neuenstadt, C., Özçep, Ö. L., Roshchin, M., Solomakhina, N., Soylu, A., Svingos, C., Brandt, S., Giese, M., Ioannidis, Y. E., Lamparter, S., Möller, R., Kotidis, Y., & Waaler, A. (2017). Semantic access to streaming and static data at siemens. J. Web Sem., 44, 54-74.

Digital Library

[28]

Klarman, S., & Meyer, T. (2014). Querying temporal databases via OWL 2 QL. In Proc. of the 8th Int. Conf. on Web Reasoning and Rule Systems, RR 2014, Vol. 8741 of LNCS, pp. 92-107. Springer.

[29]

Kontchakov, R., Rezk, M., Rodriguez-Muro, M., Xiao, G., & Zakharyaschev, M. (2014). Answering SPARQL queries over databases under OWL 2 QL entailment regime. In Proc. of the 13th Int. Semantic Web Conf. (ISWC 2014), Part I, Vol. 8796 of LNCS, pp. 552-567. Springer.

Digital Library

[30]

Kontchakov, R., Pandolfo, L., Pulina, L., Ryzhikov, V., & Zakharyaschev, M. (2016). Temporal and spatial OBDA with many-dimensional halpern-shoham logic. In IJCAI, pp. 1160-1166. IJCAI/AAAI Press.

Digital Library

[31]

Koymans, R. (1990). Specifying real-time properties with metric temporal logic. Real-Time Systems, 2(4), 255-299.

Digital Library

[32]

Ladner, R. E. (1977). The computational complexity of provability in systems of modal propositional logic. SIAM Journal of Computing.

[33]

Lutz, C., Wolter, F., & Zakharyaschev, M. (2008). Temporal description logics: A survey. In Proc. of the 15th Int. Symposium on Temporal Representation and Reasoning (TIME 2008), pp. 3-14.

Digital Library

[34]

Madnani, K., Krishna, S. N., & Pandya, P. K. (2013). On the decidability and complexity of some fragments of Metric Temporal Logic. CoRR, abs/1305.6137.

[35]

Ouaknine, J., & Worrell, J. (2005). On the decidability of metric temporal logic. In Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science, LICS '05, pp. 188-197, Washington, DC, USA. IEEE Computer Society.

Digital Library

[36]

Ouaknine, J., & Worrell, J. (2008). Some recent results in metric temporal logic. In Formal Modeling and Analysis of Timed Systems, 6th International Conference, FORMATS 2008, Saint Malo, France, September 15-17, 2008. Proceedings, pp. 1-13.

Digital Library

[37]

Özçep, Ö., Möller, R., Neuenstadt, C., Zheleznyakov, D., & Kharlamov, E. (2013). A semantics for temporal and stream-based query answering in an OBDA context. Tech. rep., Deliverable D5.1, FP7-318338, EU.

[38]

Özçep, Ö. L., & Möller, R. (2014). Ontology based data access on temporal and streaming data. In the 10th Int. Summer School on Reasoning Web, RW 2014, Vol. 8714 of LNCS, pp. 279-312. Springer.

[39]

Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., & Rosati, R. (2008). Linking data to ontologies. J. on Data Semantics, X, 133-173.

[40]

PostgreSQL (2018). Documentation 9.6.10. https://www.postgresql.org/docs/9.6/static/parallel-safety.html.

[41]

Raheb, K. E., Mailis, T., Ryzhikov, V., Papapetrou, N., & Ioannidis, Y. E. (2017). Balonse: Temporal aspects of dance movement and its ontological representation. In ESWC (2), Vol. 10250 of Lecture Notes in Computer Science, pp. 49-64.

[42]

Rodriguez-Muro, M., Kontchakov, R., & Zakharyaschev, M. (2013). Ontology-based data access: Ontop of databases. In The Semantic Web - ISWC 2013 - 12th International Semantic Web Conference, Sydney, NSW, Australia, October 21-25, 2013, Proceedings, Part I, pp. 558-573.

Digital Library

[43]

Sistla, A., & Clarke, E. (1985). The complexity of propositional linear temporal logics. J. ACM, 32, 733-749.

Digital Library

[44]

Soylu, A., Giese, M., Jiménez-Ruiz, E., Vega-Gorgojo, G., & Horrocks, I. (2016). Experiencing OptiqueVQS: a multi-paradigm and ontology-based visual query system for end users. Universal Access in the Information Society, 15(1), 129-152.

Digital Library

[45]

Tobies, S. (2001). Pspace reasoning for graded modal logics. Journal of Logic and Computation, 11(1), 85-106.

[46]

Ullman, J. D. (1988). Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press.

Digital Library

[47]

Vardi, M. (1982). The complexity of relational query languages (extended abstract). In Proc. of the 14th ACM SIGACT Symp. on Theory of Computing (STOC'82), pp. 137-146.

Digital Library

[48]

Xiao, G., Calvanese, D., Kontchakov, R., Lembo, D., Poggi, A., Rosati, R., & Zakharyaschev, M. (2018). Ontology-based data access: A survey. In Proc. of the 28th Int. Joint Conf. on Artificial Intelligence (IJCAI). IJCAI/AAAI.

Digital Library

[49]

Zaharia, M., Xin, R. S., Wendell, P., Das, T., Armbrust, M., Dave, A., Meng, X., Rosen, J., Venkataraman, S., Franklin, M. J., Ghodsi, A., Gonzalez, J., Shenker, S., & Stoica, I. (2016). Apache spark: a unified engine for big data processing. Commun. ACM, 59(11), 56-65.

Digital Library

[50]

Zhou, X., Wang, F., & Zaniolo, C. (2006). Efficient temporal coalescing query support in relational database systems. In Proc. of the 17th Int. Conf. on Database and Expert Systems Applications, DEXA 2006, Vol. 4080 of LNCS, pp. 676-686. Springer.

Digital Library

Cited By

Lanzinger MNissl MSallinger EWałęga PElkind E(2023)Temporal datalog with existential quantificationProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/365(3277-3285)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/365
Wałęga PZawidzki MWang DGrau BWilliams BChen YNeville J(2023)Materialisation-based reasoning in DatalogMTL with bounded intervalsProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25807(6566-6574)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25807
Bellomarini LBlasi LNissl MSallinger E(2022)The Temporal Vadalog SystemRules and Reasoning10.1007/978-3-031-21541-4_9(130-145)Online publication date: 26-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-21541-4_9
Show More Cited By

Querying log data with metric temporal logic
1. Theory of computation

Recommendations

Querying datalog programs with temporal logic

Temporal logic queries on Datalog and negated Datalog programs are studied, and their relationship to Datalog queries on these programs is explored. It is shown that, in general, temporal logic queries have more expressive power than Datalog queries on ...
Constructive linear-time temporal logic: Proof systems and Kripke semantics

In this paper we study a version of constructive linear-time temporal logic (LTL) with the ''next'' temporal operator. The logic is originally due to Davies, who has shown that the proof system of the logic corresponds to a type system for binding-time ...
On Metric Temporal Łukasiewicz Logic

In this paper we present a logical framework to cope with temporal reasoning under vagueness. The calculus is obtained by extending that of bounded metric temporal logic over a dense time domain, by truth-values from the rational unit interval [0,1]@?Q, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Artificial Intelligence Research

Journal of Artificial Intelligence Research Volume 62, Issue 1

May 2018

871 pages

ISSN:1076-9757

Editor:
Rossi Francesca
Department of Mathematics, Padova, Italy

Issue’s Table of Contents

Publisher

AI Access Foundation

El Segundo, CA, United States

Publication History

Published: 01 May 2018

Published in JAIR Volume 62, Issue 1

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lanzinger MNissl MSallinger EWałęga PElkind E(2023)Temporal datalog with existential quantificationProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/365(3277-3285)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/365
Wałęga PZawidzki MWang DGrau BWilliams BChen YNeville J(2023)Materialisation-based reasoning in DatalogMTL with bounded intervalsProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25807(6566-6574)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25807
Bellomarini LBlasi LNissl MSallinger E(2022)The Temporal Vadalog SystemRules and Reasoning10.1007/978-3-031-21541-4_9(130-145)Online publication date: 26-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-21541-4_9
Wang DWałęga PCuenca Grau B(2022)Seminaïve Materialisation in DatalogMTLRules and Reasoning10.1007/978-3-031-21541-4_12(183-197)Online publication date: 26-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-21541-4_12
Cruz-Filipe LGaspar GNunes I(2022)Can You Answer While You Wait?Foundations of Information and Knowledge Systems10.1007/978-3-031-11321-5_7(111-129)Online publication date: 20-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-11321-5_7
Eiter TIchise RParreira JSchneider PZhao LFaron CGhidini C(2021)Deploying spatial-stream query answering in C-ITS scenariosSemantic Web10.3233/SW-20040812:1(41-77)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.3233/SW-200408
Heyninck JGonçalves RKnorr MLeite J(2021)Tractable Reasoning Using Logic Programs with Intensional ConceptsLogics in Artificial Intelligence10.1007/978-3-030-75775-5_22(329-345)Online publication date: 17-May-2021
https://dl.acm.org/doi/10.1007/978-3-030-75775-5_22
Baader FBorgwardt SKoopmann POzaki AThost V(2020)Metric Temporal Description Logics with Interval-Rigid NamesACM Transactions on Computational Logic10.1145/339944321:4(1-46)Online publication date: 11-Aug-2020
https://dl.acm.org/doi/10.1145/3399443
Hustadt UOzaki ADixon C(2020)Theorem Proving for Pointwise Metric Temporal Logic Over the Naturals via TranslationsJournal of Automated Reasoning10.1007/s10817-020-09541-464:8(1553-1610)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s10817-020-09541-4
Ryzhikov VWałęga PZakharyaschev M(2020)Temporal Ontology-Mediated Queries and First-Order Rewritability: A Short CourseReasoning Web. Declarative Artificial Intelligence10.1007/978-3-030-60067-9_5(109-148)Online publication date: 24-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-60067-9_5
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents