专栏首页arxiv.org翻译专栏利用数据库管理系统和Treewidth进行计数(CS AI)
原创

利用数据库管理系统和Treewidth进行计数(CS AI)

有界树宽是最常被引用的组合不变量之一,它在文献中被用于有效地解决几个计数问题。一个典型的计数问题是#SAT,它要求计数布尔公式的令人满意的分配。最近的研究表明,#SAT的基准测试实例的树宽通常比较小。本文讨论了小树宽实例的计数问题。介绍了一种基于数据库管理系统(DBMS)解决计数问题的通用框架。我们的框架通过在树分解(TD)上使用动态规划(DP)解决实例,明确地利用了小树宽的优势。因此,我们将DP的概念实现到数据库管理系统(PostgreSQL)中,因为DP算法在理论上已经经常以表操作的形式给出。这允许DP算法的优雅规范和使用SQL操作记录和表,这为我们提供了一种将DP算法付诸实践的自然方法。就我们所知,我们提出了第一种方法,将DBMS用于TDs上的算法。我们的方法的一个主要优点是,DBMS自然允许使用有限的主内存(RAM)处理大型表、并行化以及挂起计算。

原文标题:Database Management Systems and Treewidth for Counting

原文:Bounded treewidth is one of the most cited combinatorial invariants, which was applied in the literature for solving several counting problems efficiently. A canonical counting problem is #SAT, which asks to count the satisfying assignments of a Boolean formula. Recent work shows that benchmarking instances for #SAT often have reasonably small treewidth. This paper deals with counting problems for instances of small treewidth. We introduce a general framework to solve counting questions based on state-of-the-art database management systems (DBMS). Our framework takes explicitly advantage of small treewidth by solving instances using dynamic programming (DP) on tree decompositions (TD). Therefore, we implement the concept of DP into a DBMS (PostgreSQL), since DP algorithms are already often given in terms of table manipulations in theory. This allows for elegant specifications of DP algorithms and the use of SQL to manipulate records and tables, which gives us a natural approach to bring DP algorithms into practice. To the best of our knowledge, we present the first approach to employ a DBMS for algorithms on TDs. A key advantage of our approach is that DBMS naturally allow to deal with huge tables with a limited amount of main memory (RAM), parallelization, as well as suspending computation.

原文作者:Johannes K. Fichte,Markus Hecher,Patrick Thier,Stefan Woltran

原文链接:https://arxiv.org/abs/2001.04191

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 从头到尾:医疗保健中人工智能产品开发的实用框架(CS AI)

    医疗保健中的人工智能(AI)具有巨大的潜力,可以提高获得高质量医疗保健的机会,同时降低总体系统成本。尽管这定期成为头条新闻,并且有许多证明概念的出版物,但有关的...

    RockNPeng
  • 关于救护车路线和位置问题的全面调查(cs AI)

    在这项研究中,广泛的文献综述了救护车路径问题(ARP)和救护车位置问题(ALP)的最新发展。这两个问题分别是对车辆路径问题(VRP)和最大覆盖问题(MCP)的修...

    RockNPeng
  • 有界CTL的充要条件(CS AI)

    计算树逻辑(CTL)是形式验证中的主要形式主义之一。作为一种规范语言,它用于表示预期现有系统可以满足的属性。从验证和系统设计的角度来看,由于各种原因,这种特性的...

    RockNPeng
  • Python Algorithms - C2 The basics

    本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。

    宅男潇涧
  • [计算机视觉论文速递] 2018-03-05

    通知:这篇推文有16篇论文速递信息,涉及目标检测、图像分割、风格迁移和GAN等方向。 [1]《Hashing with Mutual Information》 ...

    Amusi
  • regularized negative binomial regression对单细胞数据进行标准化

    由于技术因素,scRNA-seq数据可能由于每个细胞中检测到的分子数量不同导致细胞与细胞间的差异。为了解决区分生物学异质性与技术造成的差异,本文提出正则化负二项...

    生信编程日常
  • Decolonial AI:人工智能社会技术预见的Decolonial理论(CS Computers and Society)

    本文探讨了批判性科学,特别是后殖民和非殖民理论在理解和塑造人工智能不断进步方面的重要作用。人工智能(AI)被视为将重塑现代社会及其关系的技术进步之一。 尽管设计...

    Rosalie
  • 强化文本风格转移奖励框架(CS CL)

    样式转换处理的算法,以转移的风格属性的一段文本到另一个,同时确保核心内容是保留。 文本风格转换因其在文本裁剪生成中的广泛应用而受到人们的广泛关注。 现有作品基于...

    用户7095611
  • 开发网络数据管理系统的无编码软件框架(CS SE)

    最近越来越多的企业打算在云中部署数据管理系统。由于软件开发的专业性,对于非程序员来说,开发这种系统仍然很困难,即使是开发一个小系统。然而,SaaS的发展带来了无...

    Elva
  • 面向模型检验的真实软件定义网络(CS NI)

    在软件定义的网络(sdn)中,控制器程序负责跨大量交换机部署不同的网络功能,但这样做的风险很大: 部署有缺陷的控制器代码可能导致网络和服务中断和安全漏洞。 因此...

    用户7095611

扫码关注云+社区

领取腾讯云代金券