...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Annals of Mathematics and Artificial Intelligence >The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs
【24h】

The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs

机译：传递闭包对未标记图上导航查询语言表达能力的影响

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

摘要

Several established and novel applications motivate us to study the expressive power of navigational query languages on graphs, which represent binary relations. Our basic language has only the operators union and composition, together with the identity relation. Richer languages can be obtained by adding other features such as intersection, difference, projection and coprojection, converse, and the diversity relation. The expressive power of the languages thus obtained cannot only be evaluated at the level of path queries (queries returning binary relations), but also at the level of Boolean or yeso queries (expressed by the nonemptiness of an expression). For the languages considered above, adding transitive closure augments the expressive power not only at the level of path queries but also at the level of Boolean queries, for the latter provided that multiple input relations are allowed. This is no longer true in the context of unlabeled graphs (i.e., in the case where there is only one input relation), however. In this paper, we prove that this is indeed not the case for the basic language to which none, one, or both of projection and the diversity relation are added, a surprising result given the limited expressive power of these languages. In combination with earlier work (Fletcher et al. 2011, 2012), this result yields a complete understanding of the impact of transitive closure on the languages under consideration.
机译：几个已建立且新颖的应用程序促使我们研究导航查询语言在表示二进制关系的图形上的表达能力。我们的基本语言只有操作员并集和组成，以及身份关系。可以通过添加其他特征（例如交集，差异，投影和共投影，逆和分集关系）来获得更丰富的语言。这样获得的语言的表达能力不仅可以在路径查询（返回二进制关系的查询）级别进行评估，而且可以在布尔或是/否查询（通过表达式的非空表达）级别进行评估。对于上面考虑的语言，添加传递闭包不仅可以在路径查询级别而且可以在布尔查询级别提高表达能力，因为后者允许多个输入关系。但是，在未标记图的情况下（即在只有一个输入关系的情况下），这不再成立。在本文中，我们证明，对于基本语言而言，确实没有这样的情况，在基本语言中未添加投影，多样性关系中的一个，一个或两个都添加了投影和多样性关系，鉴于这些语言的有限表达力，这是令人惊讶的结果。结合早期的工作（Fletcher等人，2011，2012），该结果可以使您完全理解传递闭包对所考虑语言的影响。

著录项

  • 来源
  • 作者

    George H. L. Fletcher; Marc Gyssens; Dirk Leinders; Jan Van den Bussche; Dirk Van Gucht; Stijn Vansummeren; Yuqing Wu;

  • 作者单位

    Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, Netherlands;

    School for Information Technology, Hasselt University and Transnational University of Limburg, Martelarenlaan 42, 3500 Hasselt, Belgium;

    School for Information Technology, Hasselt University and Transnational University of Limburg, Martelarenlaan 42, 3500 Hasselt, Belgium;

    School for Information Technology, Hasselt University and Transnational University of Limburg, Martelarenlaan 42, 3500 Hasselt, Belgium;

    School of Informatics and Computing, Indiana University, Lindley Hall, 150 S. Woodlawn Ave., Bloomington, IN 47405, USA;

    Department of Computer and Decision Engineering (CoDE), Universite Libre de Bruxelles, CP165/15, av. F. D. Roosevelt 50, 1050 Brussels, Belgium;

    School of Informatics and Computing, Indiana University, Lindley Hall, 150 S. Woodlawn Ave., Bloomington, IN 47405, USA;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    Boolean query; Transitive closure; Relation algebra; Unlabeled graph; Expressiveness;

    机译：布尔查询;传递闭包;关系代数未标记图;表现力;

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号