On the Complexity of Temporal Query Answering
On the Complexity of Temporal Query Answering
复制标题
关于时态查询应答的复杂性
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
M. Lippmann
中科院分区：
文献类型：
--
作者：
F. Baader;Stefan Borgwardt;M. Lippmann
基于本体的数据访问（OBDA）将数据库中的查询回答推广到了演绎，因为（i）不假定事实库包含完整的知识（即，没有封闭世界假设），并且（ii）查询中出现的谓词的解释受到本体的公理约束。对于本体由适当的描述逻辑（DL）表达且查询为合取查询的情况，OBDA已被详细研究。受态势感知应用的推动，我们研究将OBDA扩展到时态情况。作为查询语言，我们考虑著名的命题时态逻辑LTL的一种扩展，其中合取查询可以替代命题变量出现，并且作为本体语言我们使用原型的表达性描述逻辑ALC。对于所得的时态化OBDA实例，我们研究查询蕴含问题的数据复杂性和组合复杂性。
Ontology-based data access (OBDA) generalizes query answering in databases towards deduction since (i) the fact base is not assumed to contain complete knowledge (i.e., there is no closed world assumption), and (ii) the interpretation of the predicates occurring in the queries is constrained by axioms of an ontology. OBDA has been investigated in detail for the case where the ontology is expressed by an appropriate Description Logic (DL) and the queries are conjunctive queries. Motivated by situation awareness applications, we investigate an extension of OBDA to the temporal case. As query language we consider an extension of the well-known propositional temporal logic LTL where conjunctive queries can occur in place of propositional variables, and as ontology language we use the prototypical expressive DL ALC. For the resulting instance of temporalized OBDA, we investigate both data complexity and combined complexity of the query entailment problem.