论文标题
具有应用时间的流的有限内存标准
Bounded-Memory Criteria for Streams with Application Time
论文作者
论文摘要
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.在本体论中的一组约束，例如基于本体的数据访问（OBDA）的范式。在经典的OBDA中，通过将其转换为数据源级别的查询来回答高级查询。转换需要一个重写步骤，其中将本体学的知识纳入查询中，然后在一组映射方面做出了不断发展的步骤。鉴于OBDA设置，很难决定是否有效地回答查询以及如何进行查询。特别是很难确定是否可以在有界内存中回答查询，即在恒定的空间W.R.T.中回答查询。数据流的无限生长前缀。这项工作介绍了随着应用时间时间的流上选择的限制内存计算（SPJ）查询的标准。决定是否可以在恒定空间中回答SPJ查询要比高级查询更容易，因为本体论和一组映射都不是输入的一部分。使用经典OBDA的转换过程，这些标准可以帮助确定在流上回答高级查询的效率。
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.
