专栏首页arxiv.org翻译专栏通过DL-Lite知识库计算查询答案(扩展版本)(CS DB)
原创

通过DL-Lite知识库计算查询答案(扩展版本)(CS DB)

统计查询的答案是几乎所有数据库管理系统都支持的操作。在本文中,我们关注的是在知识库(KB)上计算答案,知识库可以看作是一个丰富了所考虑领域背景知识的数据库。特别是,我们将工作放在本体介导的查询应答/基于本体的数据访问(OMQA/OBDA)的上下文中,其中用于本体的语言是DL-Lite家族的成员,数据是一组(通常是虚拟的)断言。我们研究了查询应答的数据复杂性,针对包含数字限制的DL-Lite家族的不同成员,以及针对具有不同形状(连接、分支、根)计数的连接查询的变体。我们通过在optime和LOGSPACE中提供一个PTIME和coNP下界以及上界来改进现有的结果。对于后一种情况,我们定义了一种新的查询重写技术到一阶计数逻辑。

原文题目:Counting Query Answers over a DL-Lite Knowledge Base (extended version)

原文:Counting answers to a query is an operation supported by virtually all database management systems. In this paper we focus on counting answers over a Knowledge Base (KB), which may be viewed as a database enriched with background knowledge about the domain under consideration. In particular, we place our work in the context of Ontology-Mediated Query Answering/Ontology-based Data Access (OMQA/OBDA), where the language used for the ontology is a member of the DL-Lite family and the data is a (usually virtual) set of assertions. We study the data complexity of query answering, for different members of the DL-Lite family that include number restrictions, and for variants of conjunctive queries with counting that differ with respect to their shape (connected, branching, rooted). We improve upon existing results by providing a PTIME and coNP lower bounds, and upper bounds in PTIME and LOGSPACE. For the latter case, we define a novel query rewriting technique into first-order logic with counting.

原文作者:Julien Corman

原文地址:https://arxiv.org/abs/2005.05886

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 如何扩展DL-Lite族中的时间连接查询(CS AI)

    基于本体的查询应答(OBQA)通过在本体中编码的领域知识来增加数据库中的经典查询应答。 OBQA系统可以使用本体论知识来推断数据中没有明确给出的新信息。 此外,...

    时代在召唤
  • 3分钟速读原著《高性能MySQL》(四)

    Induction是一款用于理解数据关系的开源管理工具,它可用来探索行/列,运行查询和数据可视化等方面。该工具支持多种数据库,包括PostgreSQL,My...

    cwl_java
  • 一份最新的、全面的NLP文本分类综述

    Paper:Deep Learning Based Text Classification: A Comprehensive Review(Computer S...

    NewBeeNLP
  • 知识图谱入门(三)

    作为人类,我们可以基于图 1 推断出一些新的信息,例如 EID15 的举办地点是 Santiago、有航班相连的城市必定存在机场等。在这些情况下,给定图中的数据...

    口仆
  • 知识图谱入门 ,语义搜索

    什么是语义搜索,借用万维网之父Tim Berners-Lee的解释 “语义搜索的本质是通过数学来拜托当今搜索中使用的猜测和近似,并为词语的含义以及它们如何关联到...

    机器学习AI算法工程
  • MTDDL——美团点评分布式数据访问层中间件

    背景 2016年Q3季度初,在美团外卖上单2.0项目上线后,商家和商品数量急速增长,预估商品库的容量和写峰值QPS会很快遇到巨大压力。随之而来也会影响线上服务的...

    美团技术团队
  • 《亿级流量网站架构核心技术》概要 《亿级流量网站架构核心技术》目录一览

    本书暂定名称为《亿级流量网站架构核心技术——跟开涛学搭建高可用高并发系统》,如有好的书名建议欢迎留言,必当重谢。内容已交由出版社编辑,相信很快就会和大家见面。主...

    大道七哥
  • 【资源】吴恩达 AI 完整课程资源超级大汇总!

    吴恩达(Andrew Ng),毫无疑问,是全球人工智能(AI)领域的大 IP!随着近些年来 AI 越来越火的大趋势下,吴恩达一直致力于普及、宣传、推广 AI 教...

    yuquanle
  • Paddle Lite特性全解读,多硬件支持、轻量化部署等亮点频现

    在技术革新的浪潮下,智能硬件结合人工智能越来越广地进入了我们的生活。小到智能手机、手表,大到智能交通系统、工业自动检测平台等,无不渗透了人工智能的威力。此外,为...

    用户1386409

扫码关注云+社区

领取腾讯云代金券