论文标题
本体性时间逻辑中本体介导的查询的一阶重写能力
First-Order Rewritability of Ontology-Mediated Queries in Linear Temporal Logic
论文作者
论文摘要
我们研究基于本体的数据访问时间数据。我们考虑在离散时间（z，<）中解释的线性时间逻辑LTL中给出的时间本体。查询以LTL或MFO（<）为内置线性顺序（<），Monadic的一阶逻辑。我们关注的是由时间本体学和查询组成的本体介导的查询（OMQ）的一阶重写。通过考虑在本体论中使用的临时操作员并区分全体LTL中给出的本体论及其核心，Krom和号角碎片，我们确定了具有原子质查询的OMQ层次结构，通过证明将fo（<）重写为fo（<），一阶逻辑，并用内置的序列，fo（<，e）的标准x（<，e）（<，e），<mm <mm <mm对于任何固定的n> 1或FO（RPR），相当于0 modulo n“，该固定n> 1（rpr）延伸了fo（<），并以关系原始的递归。就电路复杂度而言，FO（<，e）和FO（RPR） - 剥夺性可以分别在均匀的AC0和NC1中回答OMQ。 我们获得了更具表现力类型的查询类型的类似层次结构：阳性LTL形式，单调MFO（<）和任意MFO（<） - 公式。如果要访问的时间数据是一维的，我们的结果将直接适用；此外，他们奠定了基础，用于研究基于本体的访问，使用时间和描述逻辑在二维时间数据上的访问。
We investigate ontology-based data access to temporal data. We consider temporal ontologies given in linear temporal logic LTL interpreted over discrete time (Z,<). Queries are given in LTL or MFO(<), monadic first-order logic with a built-in linear order. Our concern is first-order rewritability of ontology-mediated queries (OMQs) consisting of a temporal ontology and a query. By taking account of the temporal operators used in the ontology and distinguishing between ontologies given in full LTL and its core, Krom and Horn fragments, we identify a hierarchy of OMQs with atomic queries by proving rewritability into either FO(<), first-order logic with the built-in linear order, or FO(<,E), which extends FO(<) with the standard arithmetic predicates saying that "x is equivalent to 0 modulo n", for any fixed n > 1, or FO(RPR), which extends FO(<) with relational primitive recursion. In terms of circuit complexity, FO(<,E)- and FO(RPR)-rewritability guarantee OMQ answering in uniform AC0 and, respectively, NC1. We obtain similar hierarchies for more expressive types of queries: positive LTL-formulas, monotone MFO(<)- and arbitrary MFO(<)-formulas. Our results are directly applicable if the temporal data to be accessed is one-dimensional; moreover, they lay foundations for investigating ontology-based access using combinations of temporal and description logics over two-dimensional temporal data.
