...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Theory and Practice of Logic Programming >Disjunctive datalog with existential quantifiers: Semantics, decidability, and complexity issues
【24h】

Disjunctive datalog with existential quantifiers: Semantics, decidability, and complexity issues

机译：存在量词的析取数据日志：语义，可判定性和复杂性问题

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Datalog is one of the best-known rule-based languages, and extensions of it are used in a wide context of applications. An important Datalog extension is Disjunctive Datalog, which significantly increases the expressivity of the basic language. Disjunctive Datalog is useful in a wide range of applications, ranging from Databases (e.g., Data Integration) to Artificial Intelligence (e.g., diagnosis and planning under incomplete knowledge). However, in recent years an important shortcoming of Dafalog-based languages became evident, e.g. in the context of data-integration (consistent query-answering, ontology-based data access) and Semantic Web applications: The language does not permit any generation of and reasoning with unnamed individuals in an obvious way. In general, it is weak in supporting many cases of existential quantification. To overcome this problem, Datalog~3 has recently been proposed, which extends traditional Datalog by existential quantification in rule heads. In this work, we propose a natural extension of Disjunctive Datalog and Datalog3~, called Datalog~(BV), which allows both disjunctions and existential quantification in rule heads and is therefore an attractive language for knowledge representation and reasoning, especially in domains where ontology-based reasoning is needed. We formally define syntax and semantics of the language Datalog~(3v), and provide a notion of instantiation, which we prove to be adequate for Datalog~(3v). A main issue of Datalog3 and hence also of Datalog~(3v) is that decidability is no longer guaranteed for typical reasoning tasks. In order to address this issue, we identify many decidable fragments of the language, which extend, in a natural way, analog classes defined in the non-disjunctive case. Moreover, we carry out an in-depth complexity analysis, deriving interesting results which range from Logarithmic Space to Exponential Time.
机译：Datalog是最著名的基于规则的语言之一，它的扩展用于广泛的应用程序上下文中。重要的Datalog扩展是Disjunctive Datalog，它大大提高了基本语言的表达能力。从数据库（例如，数据集成）到人工智能（例如，在知识不完全的情况下进行诊断和计划）的广泛应用中，析取数据日志非常有用。但是，近年来，基于Dafalog的语言的一个重要缺点变得很明显，例如在数据集成（一致的查询回答，基于本体的数据访问）和语义Web应用程序的上下文中：该语言不允许以明显的方式对未命名的个人进行任何生成和推理。通常，它在支持许多存在量化的情况下是薄弱的。为了克服这个问题，最近提出了Datalog〜3，它通过规则头中的存在量化来扩展传统的Datalog。在这项工作中，我们提出了分离数据记录和数据记录3〜的自然扩展，称为数据记录〜（BV），它允许规则头中的分离和存在量化，因​​此是用于知识表示和推理的一种有吸引力的语言，尤其是在本体论领域需要基于推理的。我们正式定义了语言Datalog〜（3v）的语法和语义，并提供了实例化概念，我们证明该实例足以用于Datalog〜（3v）。 Datalog3以及Datalog〜（3v）的一个主要问题是，对于典型的推理任务而言，可确定性已不再得到保证。为了解决此问题，我们确定了该语言的许多可确定的片段，这些片段以自然的方式扩展了非析取情况下定义的模拟类。此外，我们进行了深入的复杂性分析，得出了从对数空间到指数时间的有趣结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号