  Bounded-memory computability continues to be in the focus of those areas of
AI and databases that deal with feasible computations over streams---be it
feasible arithmetical calculations on low-level streams or feasible query
answering for declaratively specified queries on relational data streams or
even feasible query answering for high-level queries on streams w.r.t. a set of
constraints in an ontology such as in the paradigm of Ontology-Based Data
Access (OBDA). In classical OBDA, a high-level query is answered by
transforming it into a query on data source level. The transformation requires
a rewriting step, where knowledge from an ontology is incorporated into the
query, followed by an unfolding step with respect to a set of mappings. Given
an OBDA setting it is very difficult to decide, whether and how a query can be
answered efficiently. In particular it is difficult to decide whether a query
can be answered in bounded memory, i.e., in constant space w.r.t. an infinitely
growing prefix of a data stream. This work presents criteria for bounded-memory
computability of select-project-join (SPJ) queries over streams with
application time. Deciding whether an SPJ query can be answered in constant
space is easier than for high-level queries, as neither an ontology nor a set
of mappings are part of the input. Using the transformation process of
classical OBDA, these criteria then can help deciding the efficiency of
answering high-level queries on streams.
