• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>ACM transactions on database systems >Guarded-Based Disjunctive Tuple-Generating Dependencies
【24h】

Guarded-Based Disjunctive Tuple-Generating Dependencies

机译：基于保护的析取元组生成依赖项

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

摘要

We perform an in-depth complexity analysis of query answering under guarded-based classes of disjunctive tuple-generating dependencies (DTGDs), focusing on (unions of) conjunctive queries ((U) CQs). We show that the problem under investigation is very hard, namely 2EXPTIME-complete, even for fixed sets of dependencies of a very restricted form. This is a surprising lower bound that demonstrates the enormous impact of disjunction on query answering under guarded-based tuple-generating dependencies, and also reveals the source of complexity for expressive logics such as the guarded fragment of first-order logic. We then proceed to investigate whether prominent subclasses of (U) CQs (i.e., queries of bounded treewidth and hypertree-width, and acyclic queries) have a positive impact on the complexity of the problem under consideration. We show that queries of bounded treewidth and bounded hypertree-width do not reduce the complexity of our problem, even if we focus on predicates of bounded arity or on fixed sets of DTGDs. Regarding acyclic queries, although the problem remains 2EXPTIME-complete in general, in some relevant settings the complexity reduces to EXPTIME-complete. Finally, with the aim of identifying tractable cases, we focus our attention on atomic queries. We show that atomic queries do not make the query answering problem easier under classes of guarded-based DTGDs that allow more than one atom to occur in the body of the dependencies. However, the complexity significantly decreases in the case of dependencies that can have only one atom in the body. In particular, we obtain a PTIME-completeness if we focus on predicates of bounded arity, and AC0-membership when the set of dependencies and the query are fixed. Interestingly, our results can be used as a generic tool for establishing complexity results for query answering under various description logics.
机译：我们在析取元组生成依赖项（DTGD）的基于保护的类下执行查询应答的深入复杂性分析，重点是（联合）联合查询（（U）CQ）。我们表明，所研究的问题非常棘手，即2EXPTIME-complete，即使对于格式非常严格的固定依赖性集也是如此。这是一个令人惊讶的下限，它说明了在基于保护的元组生成依赖项下，析取对查询应答的巨大影响，并且还揭示了表达逻辑（例如，一阶逻辑的保护片段）的复杂性来源。然后，我们继续研究（U）CQ的重要子类（即有界树宽和超树宽查询和非循环查询）是否对所考虑问题的复杂性产生积极影响。我们显示出，即使我们关注于有限Arity谓词或DTGD的固定集合，对有限树宽和有限超树宽的查询也不会降低问题的复杂性。关于非循环查询，尽管通常问题仍然是2EXPTIME-complete，但是在某些相关设置中，复杂度降低到EXPTIME-complete。最后，为了确定易处理的案例，我们将注意力集中在原子查询上。我们表明，在基于受保护的DTGD的类下，原子查询不会使查询回答问题变得更容易，该类允许在依赖项的主体中出现多个原子。但是，如果依赖项在体内只能有一个原子，则复杂度会大大降低。尤其是，如果我们专注于有限Arity的谓词，并且在依赖项和查询集固定的情况下为AC0成员，则将获得PTIME完整性。有趣的是，我们的结果可以用作建立复杂度结果的通用工具，以便在各种描述逻辑下进行查询回答。

著录项

  • 来源
    《ACM transactions on database systems》 |2016年第4期|27.1-27.45|共45页
  • 作者

    Bourhis Pierre; Manna Marco; Morak Michael; Pieris Andreas;

  • 作者单位

    Univ Lille 1, CNRS CRIStAL, Parc Sci Haute Borne 40,Ave Halley Bat B, F-59650 Villeneuve Dascq, France|INRIA Lille, Parc Sci Haute Borne 40,Ave Halley Bat B, F-59650 Villeneuve Dascq, France;

    Univ Calabria, Dept Math & Comp Sci, Via Pietro Bucci,Cubo 31B, I-87036 Arcavacata Di Rende, CS, Italy;

    Vienna Univ Technol, Database & Artificial Intelligence Grp, Inst Informat Syst, 9-11 Favoritenstr, A-1040 Vienna, Austria;

    Univ Edinburgh, Informat Forum, 10 Crichton St, Edinburgh EH8 9AB, Midlothian, Scotland;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    Algorithms; Theory; Languages;

    机译：算法;理论;语言;

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号