Abstract
Stream reasoning considers continuously deriving conclusions on streaming data. While traditional stream processing approaches focus on throughput and are often based on operational grounds, reasoning approaches aim at high expressiveness based on declarative semantics; yet according theoretical underpinning in the streaming area has been lacking. To fill this gap, we provide LARS, a Logic-based Framework for Analytic Reasoning over Streams. It provides generic window operators to limit reasoning to recent snapshots of data, and modalities to control the temporal information of data. Building on resulting formulas, a rule-based language is presented which can be seen as extension of Answer Set Programming (ASP) for streams. We study semantic properties and the computational complexity of LARS, its relation to other formalisms and mention various work that builds on it.
This work has been supported by the Austrian Science Fund (FWF) projects P26471, P27730, and W1255-N23.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Several workshops on this subject have been held in the recent years, e.g. in Vienna 2015 and in Berlin 2016 apart from further workshops at major conferences.
- 2.
An extended version with details, examples, and further results is online available [9].
- 3.
References
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)
Allen, J.F.: Maintaining knowledge about temporal intervals. Commun. ACM 26(11), 832–843 (1983)
Anicic, D., Fodor, P., Rudolph, S., Stühmer, R., Stojanovic, N., Studer, R.: A rule-based language for complex event processing and reasoning. In: Hitzler, P., Lukasiewicz, T. (eds.) RR 2010. LNCS, vol. 6333, pp. 42–57. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15918-3_5
Arasu, A., Babu, S., Widom, J.: The CQL continuous query language: semantic foundations and query execution. VLDB J. 15(2), 121–142 (2006)
Barbieri, D.F., Braga, D., Ceri, S., Della Valle, E., Grossniklaus, M.: C-SPARQL: a continuous query language for RDF data streams. Int. J. Semant. Comput. 4(1), 3–25 (2010)
Bazoobandi, H.R., Beck, H., Urbani, J.: Expressive stream reasoning with laser. In: Proceeding of ISWC (2017) (to appear). http://arxiv.org/abs/1707.08876
Beck, H., Bierbaumer, B., Dao-Tran, M., Eiter, T., Hellwagner, H., Schekotihin, K.: Stream reasoning-based control of caching strategies in CCN routers. In: Mao, S., Marina, M.K., Senouci, S.M. (eds.) IEEE ICC 2017 Next Generation Networking and Internet Symposium (2017).https://arxiv.org/abs/1610.04005
Beck, H., Dao-Tran, M., Eiter, T.: Equivalent stream reasoning programs. In: Kambhampati, S., Brewka, G. (eds.) Proceeding of 25th International Joint Conference on Artificial Intelligence, IJCAI 2016, pp. 929–935. AAAI Press/IJCAI (2016)
Beck, H., Dao-Tran, M., Eiter, T.: LARS: A Logic-Based Framework for Analytic Reasoning over Streams. Technical report INFSYS RR-1843-17-03, Institute of Information Systems, TU Wien, October 2017. http://www.kr.tuwien.ac.at/research/reports/rr1703.pdf
Beck, H., Dao-Tran, M., Eiter, T., Fink, M.: LARS: a logic-based framework for analyzing reasoning over streams. In: Bonet, B., Koenig, S. (eds.) Proceeding of 28th Conference on Artificial Intelligence, AAAI 2015, pp. 1431–1438. AAAI Press (2015)
Beck, H., Eiter, T., Folie, C.: Ticker: a system for incremental ASP-based stream reasoning. Theory and Practice of Logic Programming (2017) (to appear). special issue on ICLP 2017
Brewka, G., Eiter, T.: Equilibria in heterogeneous nonmonotonic multi-context systems. In: Proceeding of 22nd Conference on Artificial Intelligence, AAAI 2007, pp. 385–390. AAAI Press (2007)
Brewka, G., Eiter, T., Truszczyński, M. (eds.): AI Magazine: special issue on Answer Set Programming, vol. 37, no. 3. AAAI Press (2016) (Fall issue)
Dao-Tran, M., Eiter, T.: Streaming multi-context systems. In: Sierra, C., Bacchus, F. (eds.) Proceeding of 26th International Joint Conference on Artificial Intelligence, IJCAI 2017, pp. 1000–1007. IJCAI (2017)
Della Valle, E., Ceri, S., van Harmelen, F., Fensel, D.: It’s a streaming world! reasoning upon rapidly changing information. IEEE Intell. Syst. 24, 83–89 (2009)
Doyle, J.: A truth maintenance system. Artif. Intell. 12(3), 231–272 (1979)
Eiter, T., Ianni, G., Fink, M., Krennwallner, T., Redl, C., Schüller, P.: A model building framework for ASP with external computations. Theory Pract. Logic Program. 16(4), 418–464 (2016)
Elkan, C.: A rational reconstruction of nonmonotonic truth maintenance systems. Artif. Intell. 43(2), 219–234 (1990)
Faber, W., Pfeifer, G., Leone, N.: Semantics and complexity of recursive aggregates in answer set programming. Artif. Intell. 175(1), 278–298 (2011)
Garcia-Molina, H., Ullman, J.D., Widom, J.: Database Systems - The Complete Book, 2nd edn. Pearson Education, London (2009)
Gebser, M., Grote, T., Kaminski, R., Obermeier, P., Sabuncu, O., Schaub, T.: Stream reasoning with answer set programming. Preliminary report. In: KR, pp. 613–617 (2012)
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Multi-shot ASP solving with clingo. CoRR abs/1705.09811 (2017). http://arxiv.org/abs/1705.09811
Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Gener. Comput. 9, 365–385 (1991)
Beck, H., Dao-Tran, M., Eiter, T.: Answer update for rule-based stream reasoning. In: Yang, Q., Wooldridge, M. (eds.) Proceeding of 24th International Joint Conference on Artificial Intelligence, IJCAI 2015, pp. 2741–2747. AAAI Press/IJCAI (2015)
Heyting, A.: Die formalen Regeln der intuitionistischen Logik. In: Sitzungsberichte der Preußischen Akademie der Wissenschaften, phys.-math. Klasse, pp. 42–65, 57–71, 158–169 (1930)
Koymans, R.: Specifying real-time properties with metric temporal logic. Real-Time Syst. 2(4), 255–299 (1990)
Mileo, A., Abdelrahman, A., Policarpio, S., Hauswirth, M.: StreamRule: a nonmonotonic stream reasoning system for the semantic web. In: Faber, W., Lembo, D. (eds.) RR 2013. LNCS, vol. 7994, pp. 247–252. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39666-3_23
Mileo, A., Dao-Tran, M., Eiter, T., Fink, M.: Stream reasoning. In: Liu, L., Özsu, M.T. (eds.) Encyclopedia of Database Systems, 2nd edn. Springer, New York (2017). https://doi.org/10.1007/978-1-4899-7993-3_80715-1
Pearce, D.: Equilibrium logic. Annals Math. Artif. Intell. 47(1–2), 3–41 (2006)
Le-Phuoc, D., Dao-Tran, M., Xavier Parreira, J., Hauswirth, M.: A native and adaptive approach for unified processing of linked streams and linked data. In: Aroyo, L., Welty, C., Alani, H., Taylor, J., Bernstein, A., Kagal, L., Noy, N., Blomqvist, E. (eds.) ISWC 2011. LNCS, vol. 7031, pp. 370–388. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25073-6_24
Phuoc, D.L., Nguyen-Mau, H.Q., Parreira, J.X., Hauswirth, M.: A middleware framework for scalable management of linked streams. J. Web Sem. 16, 42–51 (2012)
Woltran, S.: Characterizations for relativized notions of equivalence in answer set programming. In: Alferes, J.J., Leite, J. (eds.) JELIA 2004. LNCS (LNAI), vol. 3229, pp. 161–173. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30227-8_16
Zaniolo, C.: Logical foundations of continuous query languages for data streams. In: Barceló, P., Pichler, R. (eds.) Datalog 2.0 2012. LNCS, vol. 7494, pp. 177–189. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32925-8_18
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Beck, H., Dao-Tran, M., Eiter, T. (2018). LARS: A Logic-Based Framework for Analytic Reasoning over Streams. In: Tjoa, A., Bellatreche, L., Biffl, S., van Leeuwen, J., Wiedermann, J. (eds) SOFSEM 2018: Theory and Practice of Computer Science. SOFSEM 2018. Lecture Notes in Computer Science(), vol 10706. Edizioni della Normale, Cham. https://doi.org/10.1007/978-3-319-73117-9_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-73117-9_6
Published:
Publisher Name: Edizioni della Normale, Cham
Print ISBN: 978-3-319-73116-2
Online ISBN: 978-3-319-73117-9
eBook Packages: Computer ScienceComputer Science (R0)