...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Systems >Approximation algorithms for querying incomplete databases
【24h】

Approximation algorithms for querying incomplete databases

机译：查询不完整数据库的近似算法

获取原文
获取原文并翻译 | 示例
   

获取外文期刊封面封底 >>

       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Certain answers are a widely accepted semantics of query answering over incomplete databases. As their computation is a coNP-hard problem, recent research has focused on developing (polynomial time) evaluation algorithms with correctness guarantees, that is, techniques computing a sound but possibly incomplete set of certain answers. The aim is to make the computation of certain answers feasible in practice, settling for under-approximations.In this paper, we present novel evaluation algorithms with correctness guarantees, which provide better approximations than current techniques, while retaining polynomial time data complexity. The central tools of our approach are conditional tables and the conditional evaluation of queries. We propose different strategies to evaluate conditions, leading to different approximation algorithms- more accurate evaluation strategies have higher running times, but they pay off with more certain answers being returned. Thus, our approach offers a suite of approximation algorithms enabling users to choose the technique that best meets their needs in terms of balance between efficiency and quality of the results. (C) 2019 Elsevier Ltd. All rights reserved.
机译：某些答案是通过不完整数据库的广泛接受的查询语义。随着他们的计算是一个康复的问题，最近的研究专注于开发（多项式时间）评估算法，其具有正确的保证，即计算声音但可能不完整的某些答案的技术。目的是在实践中计算某些答案的计算，解决欠克的问题。本文提出了一种具有正确保证的新型评估算法，其提供比当前技术的更好近似，同时保持多项式时间数据复杂性。我们方法的中央工具是有条件的表和查询的条件评估。我们提出了评估条件的不同策略，从而导致不同的近似算法 - 更准确的评估策略具有更高的运行时间，但它们会及时偿还更多答案。因此，我们的方法提供了一套近似算法，使用户能够选择最能在结果之间的平衡方面符合其需求的技术。 （c）2019 Elsevier Ltd.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号