全部版块 我的主页
› 论坛 › 经济学人 二区 › 外文文献专区
数据库和逻辑程序设计中递归查询的实验 系统
kedemingshi
1085 26
2022-04-15
摘要翻译：
本文研究了对大量（可能是分布式）数据进行推理的问题。目前，已有的方法存在一些局限性：{\\em(i)}由于推理一般是在主存中进行的，可同时处理的数据量有限；{\\em(ii)}与外部（和独立的）DBMSs的交互并不简单，在某些情况下，根本不允许；{\\em(iii)}对于涉及大量数据的复杂推理任务，现有实现的效率仍然不够。本文在这一背景下提供了一个贡献；本文提出了一个新的系统，称为DLV$^{DB}$，旨在解决这些问题。此外，本文还报告了我们在一些经典演绎问题上与几个最先进的系统（逻辑和数据库）进行了深入的实验分析的结果；其他测试的系统是:LDL++、XSB、Smodels和三个顶级商业DBMSs。DLV$^{DB}$在递归查询上的性能甚至明显优于商业数据库系统。出现在逻辑程序设计理论与实践中
---
英文标题：
《Experimenting with recursive queries in database and logic programming
  systems》
---
作者：
Giorgio Terracina, Nicola Leone, Vincenzino Lio, Claudio Panetta
---
最新提交年份：
2007
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Databases        数据库
分类描述：Covers database management, datamining, and data processing. Roughly includes material in ACM Subject Classes E.2, E.5, H.0, H.2, and J.1.
涵盖数据库管理、数据挖掘和数据处理。大致包括ACM学科类E.2、E.5、H.0、H.2和J.1中的材料。
--

---
英文摘要：
  This paper considers the problem of reasoning on massive amounts of (possibly distributed) data. Presently, existing proposals show some limitations: {\\em (i)} the quantity of data that can be handled contemporarily is limited, due to the fact that reasoning is generally carried out in main-memory; {\\em (ii)} the interaction with external (and independent) DBMSs is not trivial and, in several cases, not allowed at all; {\\em (iii)} the efficiency of present implementations is still not sufficient for their utilization in complex reasoning tasks involving massive amounts of data. This paper provides a contribution in this setting; it presents a new system, called DLV$^{DB}$, which aims to solve these problems. Moreover, the paper reports the results of a thorough experimental analysis we have carried out for comparing our system with several state-of-the-art systems (both logic and databases) on some classical deductive problems; the other tested systems are: LDL++, XSB, Smodels and three top-level commercial DBMSs. DLV$^{DB}$ significantly outperforms even the commercial Database Systems on recursive queries. To appear in Theory and Practice of Logic Programming (TPLP)
---
PDF下载：
-->
English_Paper.pdf
大小:(669.46 KB)

 马上下载

二维码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

全部回复
何人来此
2022-4-15 09:55:32
出现在逻辑程序设计的理论与实践(TPLP)中，在数据库和逻辑程序设计系统中进行递归查询的实验。TERRACINA,N.LEONE,V.LIO,C.PANETTADipartimento di Matematica,Universit`a della Calabria,Via P.Bucci,87030,Rende(CS),意大利（电子邮件：{TERRACINA,LEONE,LIO,panetta}@mat.unical.it)2006年10月16日提交；2007年3月12日修订；本文考虑了对大量（可能是分布式）数据进行推理的问题。目前，已有的方法存在一些局限性：（一）由于推理一般是在主存中进行的，可同时处理的数据量有限；(ii)与外部（和独立的）DBMSs的交互并不是微不足道的，在某些情况下，根本不允许；(iii)它们在涉及大量数据的复杂推理任务中的应用还不够成熟。本文在这一背景下提供了一个贡献；提出了一种新的系统DLVDB，旨在解决这些问题。此外，本文还报告了我们在一些经典演绎问题上与几个最先进的系统（逻辑系统和数据库系统）进行了深入的实验分析的结果；其他的测试系统是:LDL++、XSB、Smodels和三个toplevel商用DBMSS。DLVDBSigni在递归查询方面的性能甚至超过了商业数据库系统。出现在逻辑程序设计理论与实践(TPLP)中。关键词：演绎数据库系统，答案集编程/声明逻辑编程，递归查询，基准测试1引言在电子数据库管理系统的开发中，处理大量数据的问题受到了广泛的关注。在这种情况下，数据挖掘、数据仓库和联机分析处理等数据密集型和基于知识的应用浪潮日益高涨，对功能更强大的数据库语言和系统产生了强烈的需求。随着SQL最新标准SQL99(SQL1999)的引入，这方面的一个重要方面已经开始实施，该标准提供了对面向对象数据库和递归查询的支持，但SQL99的采用还远远不是一个“标准”；事实上，目前所有的DBMSs都不完全支持SQL99A，在某些情况下，它们采用专有（没有n个标准）语言c onstructs和functions来实现部分DBMSs。此外，SQL99 COSTR uc ts2 G.Terracina,N.Leone,V.Lio,C.Panetta的现有实现及其表达能力还不能满足在大量数据上执行复杂推理任务的要求，而逻辑BAS ed系统可以提供推理任务所需的表达能力。事实上，声明式逻辑编程提供了一种强大的形式，可以轻松地建模和解决复杂的问题。最近发展起来的基于逻辑的系统，如DLV（Leone et al.2004)、Smodels（Niemel-a et al.2000)、XSB(Rao et al.1997)、ASSAT（Lin and Zhao 2002；Lin and Zhao 2004)、Cmodels（Giunchiglia et al.2004；Giunchiglia et al.2006)、CLASP（Gebser et al.2007)等，在许多应用领域重新引起了人们对非单调推理和陈述性逻辑编程的兴趣。过去，演绎数据库系统(DDS)的提出是为了将基于逻辑的系统的表达能力与DBMSS的电子数据管理结合起来（Arni et al.2003；Gallaire et al.1984；Ce ri et al.1990；Grant and Minker，1992)；基本上，它们是试图通过与一些DBMSS的智能交互，将具有“小数据”世界观的典型Datalog system调整为具有“大数据”世界观的典型Datalog system。
二维码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

nandehutu2022
2022-4-15 09:55:38
最近出现的应用程序上下文，如theones，这些上下文来自于Internet中跨节点的自然递归，或者来自于XML(Winslett2006)，重新引起了人们对这类系统的兴趣（Abiteboul et al.2005；Loo et al.2005)。然而，目前存在的DDSs的主要局限性在于，推理仍然是在主存中进行的--这限制了可以处理的数据量--以及它们提供的通用的、外部的DBMSs之间的互操作性有限。事实上，这些系统的推理能力通常是根据特定的（商业或特殊的）DBMS而定制的。总结如下：(i)当今的数据库系统具有足够的鲁布和可移植性，可以容纳大量的数据，可能是分布式的；然而，它们的查询语言并不具有很强的表达能力来支持对这些数据的推理任务。(ii)基于逻辑的系统被赋予了高度表达能力的语言，使它们能够支持复杂的推理任务，但它们工作在主存储器中，因此只能处理有限数量的数据。(iii)演绎数据库系统不能访问和管理存储在DBMSs中的数据，但它们主要在主存中执行计算，与外部（可能是分布式的）DBMSs之间的互操作能力有限。它提出了一种新的系统DLVDB，它是基于逻辑的（类似于DDS)，但可以在大容量存储器中完成所有的工作，并且在实际应用中没有任何输入数据的限制；此外，它还可以利用数据库管理系统中的ptimization技术（如join orderings（Garcia-Mo lina et al.））。2000））和DDS理论（例如，魔术集（Beeri and Ramakrisnhan，1991；Mumick et al.dlvdballow用于两种类型的执行：（一）直接数据库执行，它直接在数据库上评估逻辑程序，使用非常有限的usag eof主内存，但对查询的表达性有一些限制，逻辑程序设计的理论和实践3；（二）主内存执行，它从（可能分布式的）数据库加载输入数据，并直接在主内存中执行逻辑程序。在这两种情况下，与数据库的互操作都是通过ODBC连接提供的；这使得通过网络以相当简单的方式处理驻留在各种数据库上的数据。为了避免可能的混淆，在下面我们使用thesymbol dlvdbb来指示整个系统，当讨论与执行方式无关时；然而，当需要在这两种执行方式之间切换时，我们使用符号DLVIOto来表示主存储器执行，而使用符号DLVDBB来表示直接数据库执行。概括地说，本工作的主要贡献如下：（一）开发一个完整的边缘系统，以更好地解决基于逻辑的系统与DBMSS之间的交互。（ii）开发了一种面向纯数据库的逻辑progra ms评估策略，该策略最大限度地减少了主存的占用，并最大限度地利用了现有DBMSS中实现的优化技术。(iii)建立了一个框架，用于对最先进的系统和DLVDB的性能进行实验比较分析。(iv)对经典演绎问题（Bancilhon和Ramakrishnan，1988)进行了一次深入的实验，结果表明，在运行时间和处理数据量方面，DLVDBB往往以数量级的速度超过逻辑系统(LDL++、XSB和Smodels）甚至商业DBMSs。
二维码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

可人4
2022-4-15 09:55:44
第2节介绍了s系统支持的推理语言，第3节描述了它提供的功能，第4节讨论了DLVDB开发中采用的主要实现原则，第5节说明了它的总体结构。第6节概述了与DLVDB相关的最新系统，然后描述了我们在经典DDS问题上对DLVDB与这些系统进行比较的实验分析。系统的推理语言在这一部分中，我们主要描述了DLVDBSystem所采用的推理语言的语法和语义。这基本上是DLP的Agg regate函数在答案集的范围内；werefer将这种语言作为DLPAin如下所示。感兴趣的读者了解关于DLPAin的所有细节（Faber et al.2004)。在开始演示之前，值得指出的是，direct databaseexecution模态只支持主存exe c ution支持的推理语言的一个严格子集。特别是，虽然DLVIO支持DLV的整个语言（包括析取、无限neg和strati编辑值得注意的是，由于基准程序是strati的，它们完全由Smodels的接地层（LParse）解决。这就是为什么我们没有用SSAT、Cmodels和CLASP进行实验，因为它们也使用LParse进行接地。4 G.Terracina,N.Leone,V.Lio,C.Panettaaggre gates）,DLVDB支持带有strati的否定和聚合的或自由的程序。2.1语法我们假设读者熟悉标准DLP；我们将DLP的原子、文字、规则和程序分别称为标准原子、标准文字、标准规则和标准程序。关于进一步的背景，见(Baral，2002；Gelfond和Lifschitz，1991)。一个DLPA集合项是一个符号集或一个基础集。符号集是一对{Vars：Conj}，其中Vars是变量s的列表，Conj是standa rd原子的连合。groun d集是形式为ht：Conj i的对集，其中tis是常数列表，Conj是standardatoms.聚合函数的gro und（variable fre e）连合。集合函数的形式为f(S)，其中S是设置项，f是集合函数符号。直观地说，聚合函数可以被认为是一个将多个常数集映射到一个常数集的函数（可能是部分的）。目前支持的聚合函数有:#count（项数）、#sum（非负有理数的和）、#min（最小项，空集未定义）、#max（最大项，空集未定义）、#avg（非负有理数的平均值）。聚合原子是f(S)T,其中f(S)是一个聚合函数，∈{=,<,≤>,>,≥}是一个预先定义的比较算子，T是aterm（变量或常数）,称为guard.agg regate原子的一个例子是:#max{Z：r(Z),a（Z,V）}>Y.一个原子既可以是S tandard(DLP)原子，也可以是聚合原子。一个字面L是原子A或一个tom A前面有缺省的否定符号not；如果A是anaggre门原子，则L是聚合的literal.dlpaprograms。一个DLPArule r是一个构造AV···v AN:-b,···,bk,不是bk+1,···,不是BM。.A是标准原子，b,···，bmare原子，n≥0,m≥k≥0。取析av···v anis是r的头，取连词b，...，bk，而不是bk+1，...，bmis是r的体。我们用H(r)表示头原子的集合{a,....,an}，用b(r)表示体原子的集合{b,...,bk,而不是bk+1,...,而不是bm}。
二维码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

可人4
2022-4-15 09:55:50
B+(r)和B-(r)表示，DLPAprogram P是一组dlparules。注意DLPAprogram P也允许内建谓词（Faber and Pfeifer 1996）内嵌规则，如c谓词相等，les s-than和gre ater-than(=,<,>)和算术谓词如加法或乘法(+,*)。直观地说，符号集{X:a(X,Y)，P(Y)}代表使a(X,Y)，P(Y)为真的X-值集，即{X}Y s.t.a（X,Y）,p（Y）是t rue}。这两个集合分别对应于cardinali ty和wift约束。逻辑程序设计理论与实践5安全。规则r的全局变量是出现在规则r的标准d原子中的变量；所有其他变量都是局部变量。规则r是安全的，如果满足以下条件:(i)r的全局变量出现在r的体中的正的标准字面上；(ii)出现在符号集{Vars：Conj}中的r的每个局部变量出现在Conj的一个原子上；(iii)r的聚合原子的ea ch保护是一个常数或aglobal变量。如果所有的r∈P都是安全的，则程序P是安全的。下面我们证明DLPA程序是安全的：设一个程序的级映射从P中的pr e dic ates到n序数的函数；另外，给定一个原子A=p(t,...,tn)，我们用Pred（A）表示它的谓词p.stratiefinednotprograms。一个DLPAprogram P称为Strati firednot（Apt et al.1988；Przymusinski，1988)，如果存在一个leve l映射，对于每个标尺：（1）对于任意l∈B+(r),并且对于任意l′∈H(r),P red(l)s≤P red(l\')s；（2）对于任意l∈b-(r),并且对于任意l′∈H(r),P red(l)S<P red(l\')S；（3）对于anyl,l′∈H(r),P red(l)S=P red(l\')S。一个DLPAprogram P称为Stratioffiedaggr(Dell\'Armi et al.2003b)，如果e是P s的一个能级映射，对于每一个规则r:(1)l出现在r的头部，l\'出现在r的主体中的一个聚合原子中，则P red(l\')A<P red(l)A；（2）如果l app e出现在r的头部，l′出现在r体的astandard原子中，则P red(l′)A≤P red(l)A。（3）如果l和l′都出现在r的头上，则P red(l′)a=P red(l)a。例2.1考虑程序为谓词a和b的一组事实加上以下两个规则:Q(X):-P(X)，#count{Y:a(Y,X）,b(X)}≤2。p(X):-q(X),b(X)。由于层次映射a=b=1,p=q=2满足了所需的条件，该程序是stratiefuledaggr。如果我们添加规则b(X):-p(X)，那么就不存在levelmapping，程序就不是stratiefilyedaggr。直观地说，属性stratioffiedaggrs禁止通过聚合进行递归。支持的语言。direct database e xecution moda fility(DLVDB)curre ntly只支持无析取、stratiefinednot和stratiefinedaggr的DLPA程序。注意，内置谓词和聚合都是支持的。相反，主存exe c ution modality(DLVIO)的uppo rts所有Strati foundedaggr的DLPA程序。因此，无限制的否定门、析取门和非递归的aggr门都是可行的。2.2答案集语义论域和基。给定一个DLPAprogram P，设Updenture出现在P中的常数集，BPbe是由P的（标准）预测tes构造的标准原子集，常数在up中。给定一个集合X，给出X的元素上所有多组集的集合G.Terracina,N.Leone,V.Lio,C.Panettao。在不失一般性的前提下，我们假定Gre门函数映射到Q（有理数集）。实例化。替换是从一组变量s到up的映射。从规则r（到上）的全局变量集的替换是r的全局子化；符号集s（toUP）的局部变量的s et的替换是s的局部替换。
二维码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

kedemingshi
2022-4-15 09:55:57
给定一个无全局可变的符号集={Vars:Conj},S的实例化是以下对集S(S)的基集：{hγ(Vars):γ(Conj)iγ是S}的局部代换。通过两个步骤得到规则r的基实例：（1）在r上应用r的全局代换σ；(2)σ(r)中的每一个符号集S都用它的实例化在st(S)中代替。程序P的实例化基础(P)是P的规则的所有可能实例的集合。例2.2考虑fo lowing程序P:Q(1)vP(2，2)。q(2)v p(2，1)。t(X):-q(X),#sum{Y:p(X，Y)}>1。实例化基础(p)是fo lowing:q(1)vp(2，2)。t(1):-q(1),#和{h1:p(1，1)i,h2:p(1，2)i}>1.q(2)v p(2，1)。t(2):-q(2)，#sum{h1:p(2，1)i,h2:p(2，2)i}>1.解释。DLPAprogram的解释P是一组标准原子，tha t是I BP。正字面A是真的。如果A∈I，I，则是假的。否定字面不是A是真的。如果A6∈I，它是假的。一个解释也为集合文字提供了一个意义。设I是一个解释。一个标准的地面连接是真的（re sp.false）W.R.T.如果它的所有字面都是tr ue。集合的意义，集合的意义，集合的意义，集合的意义，集合的意义，集合的意义，集合的意义，集合的意义，集合的意义，集合的意义，集合的意义，集合的意义，集合的意义，集合的意义，集合的意义，集合的意义，集合的意义，集合的意义。设f(S)是一个聚合函数。S W.R.T.的估值I(S)。Iis是S中合取为truew.r.t的元素的figurst常数的多集。I.更确切地说，设I(S)表示多集[t ht,...,TN:Conj I∈SConj为真W.R.t.I]。集合函数f(S)W.R.T.I的估值I（f(S))是f在I(S)上应用的结果。如果多集I(S)不在f的域中，则I(f(S))=0（其中，0是一个不存在于P中的固定符号）。一个实例化的集合原子a=f(S)k是真的W.R.T。如果:(I)I(f(S))6=，且，(ii)I(f(S))k成立；否则，A为假。一个实例化的聚合文字alnot A=not(f(S)k)是真的W.R.T。I如果:(I)I(f(S))6=，且，(ii)I(f(S))K不成立；另一个是假的。最小模型。给出一个解释I，规则r是W.r.T。如果某个headatom是真的，W.R.T。每当所有的身体文字都是真的时，w.R.T。I.一个解释M是DLPAprogram P的一个模型，如果所有的r∈Ground(P)都满足W.r.T。如果P的模型N不是ts的，那么N是最小的。给定一个代换σ和一个DLPAObj(rule，set，等），我们用σ(Obj)表示用σ(X)替换Obj中的每个变量X而得到的对象。逻辑程序设计理论与实践7答案集。我们现在回想一下Gelfond-Lifschitz变换对集合程序的推广（Faber et al.2004)，definition 2.3（Faber et al.2004)给出了一个groun d DLPAprogram P和一个t otal解释I,让PIdenote从P得到的转换程序通过删除所有体字面为假W.R.t.I.I是程序P的一个答案集，如果它是地面(P)的极小模型。例2.4考虑两个程序：P：{P(a):-#计数{X:P(X)}>0p：{p(a):-#计数{X:p(X)}<1.}地(p)={p(a):-#计数{ha:p(a)i}>0.}且地(P)={P(a):-#计数{ha:P(a)i}<1.}；还考虑解释i={p(a)}和i=.那么，Gr ound(p)i=Groun d(p)，Ground(p)i=，Ground(p)i=，Ground(p)i=Ground(p)成立。ii是P的唯一答案集（因为ii不是地(P)I的最小l模型），而pads没有答案集（ii不是地(P)I的最小l模型，并且ii不是地(P)=地(P)I的模型）。注意，任何答案集A o f P都是一个lso P的模型，因为Gr在（P）中是一个地（P），而地（P）中的规则在d（P）中是W.R.T.
二维码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

点击查看更多内容…
相关推荐
栏目导航
热门文章
推荐文章

说点什么

分享

微信QQ空间QQ微博
扫码加好友，拉您进群
各岗位、行业、专业交流群