On Bounded-Memory Stream Data Processing with Description Logics

Özgür Lütfü Özçep*, Ralf Möller

*Corresponding author for this work
1 Citation (Scopus)


Various research groups of the description logic community, in particular the group of Franz Baader, have been involved in recent efforts on temporalizing or streamifying ontology-mediated query answering (OMQA). As a result, various temporal and streamified extensions of query languages for description logics with different expressivity were investigated. For practically useful implementations of OMQA systems over temporal and streaming data, efficient algorithms for answering continuous queries are indispensable. But, depending on the expressivity of the query and ontology language, finding an efficient algorithm may not always be possible. Hence, the aim should be to provide criteria for easily checking whether an efficient algorithm exists at all and, possibly, to describe such an algorithm for a given query. In particular, for stream data it is important to find simple criteria that help deciding whether a given OMQA query can be answered with sub-linear space w.r.t. the length of a growing stream prefix. An important special case dealt with under the term “bounded memory” is that of testing for constant space. This paper discusses known syntactical criteria for bounded-memory processing of SQL queries over relational data streams and describes how these criteria from the database community can be lifted to criteria of bounded-memory query answering in the streamified OMQA setting. For illustration purposes, a syntactic criterion for bounded-memory processing of queries formulated in a fragment of the stream-temporal query language STARQL is given.

Original languageEnglish
Title of host publicationDescription Logic, Theory Combination, and All That
Number of pages22
PublisherSpringer Verlag
Publication date01.06.2019
ISBN (Print)978-3-030-22101-0
ISBN (Electronic)978-3-030-22102-7
Publication statusPublished - 01.06.2019

Research Areas and Centers

  • Centers: Center for Artificial Intelligence Luebeck (ZKIL)
  • Research Area: Intelligent Systems


Dive into the research topics of 'On Bounded-Memory Stream Data Processing with Description Logics'. Together they form a unique fingerprint.

Cite this