数据库和逻辑程序设计中递归查询的实验 系统

前者允许分析不同系统在几种数据结构上的基本递归能力，而后者则实现了一个更复杂的问题，从而允许测试所考虑的系统执行更多重新设计的推理任务的能力。对于每个问题，我们测量了不同系统在计算三种查询时的性能，即：未绑定查询（以下由符号秦表示）；具有一个绑定参数(Q)的查询；具有所有绑定参数(Q)的查询。考虑到这三种情况是重要的，因为EDBMSS和演绎数据库通常从查询绑定（通过关系alg优化、魔术集技术或对XSB而言，自顶向下求值“pushing down”选择）中获得，而ASP system通常更适合于非绑定查询（因为它们通常计算整个模型）；因此，在有利和不利的上下文中测试所有这些系统都是很有趣的。值得指出的是，一些被测试的系统实现了优化策略\'A la magic set\'(Bancilhon et al.1986；Beeri and Ramakrisnhan，1991；Mumick et al.，1996；Ross，1990)（例如，DLVDBandLDL++)，演绎数据库的典型，或其他pro gram重写技术；结果表明，实际评估的程序是这些系统自动导出的优化程序，但这些重写的代价一直被考虑在系统性能的度量中。下面我们将介绍两个考虑的问题；interesterdreader可以在（Bancilhon和Ramakrishnan 1988）中找到关于它们的所有细节。6.2.1可达性给定一个有向图G=(V，E）可达性问题的解决方案可达性(a，b）确定从节点a∈V到28 G.Terracina是否可以到达节点b∈V，n.Leone,V.Lio,C.Panettaa e中的边序列。输入由关系边（X,Y）提供，其中afact edg e（a,b）指出b是由a的n条边直接可达的。用数据库术语来说，确定G中所有可达结点对相当于计算存储边的re的传递闭包。6.2.2同代给定一个父子关系（树），同代问题的目的是找出属于同一基因配比的人对。如果两个人是兄弟姐妹，或者如果他们是同一世代的两个人的孩子，他们就属于这个世代。输入由关系父（X,Y）提供，其中事实父（thomas,moritz）意味着thomas是moritz的父。6.3基准数据集对于每个被考虑的pro ble m我们构造了几组基准数据结构。对于每种数据结构，都构造了incr宽松维度的各种实例；6.3.1可达性对于可达性问题，我们考虑了：(i)完全二元tr e es,(ii)无环图（以下为a-图）,(iii)循环图（以下为c-g图）,和(iv)cy linders（Bancilhon和Ramakrishnan，1988)。图的密度δ可以用可能的弧的图#中的弧的δ=#来度量。我们生成了各种类型的图实例，其特征分别是δequalto值为0.20、0.50和0.75。由于空间的限制，本文只给出了δ=0.20的结果。柱面是一类特殊的无圈图，可以分层；每个层具有相同数量的节点。figurrst层的每个节点有两个传出弧，没有传出弧，而最后一层的每个节点有两个传出弧，没有传出弧；实际上，一个内部层的每个节点都有两个传入和两个传出的弧线。一个圆柱的例子如图8所示。圆柱体有宽有高；因此，可以利用比ρ=宽度高度来表征圆柱。

我们生成了ρ=0.5、1.0和1.5的各类柱面。由于篇幅的限制，本文只给出了ρ=1的结果。图是用Stanford GraphBase(Knuth1994)libr来生成的，而树和柱面是用特殊的程序生成的，因为它们具有规则的结构。逻辑程序设计理论与实践29fig。6.3.2相同生成对于相同生成问题，我们给出了完整的二进制树输入数据结构。6.4问题编码我们对所考虑的两个问题使用了一般编码，其方法是在一般条件下对各种系统进行编码；具体来说，我们使用了“统一”查询，即其结构不能根据绑定参数的数量和位置进行调整的查询。对于各种pro ble ms来说，可能会有几种替代编码，还取决于底层数据结构；但是，由于许多其他实际相关的问题可以回到我们所考虑的问题，我们更喜欢使用那些适用于最广泛应用的编码。由于空间限制，我们无法在这里列出我们测试中使用的编码。感兴趣的读者可以在地址http://www.mat.unical.it/terracina/tplp-dlvdb/encodings.pdf找到它们。注意，由于DB-C不支持标准的SQL99语言，而只是简单的递归形式，我们没有将此系统与其他系统一起测试。我们将讨论DB-C在separ ate切片中的编码和结果。6.5结果和讨论在我们的测试中，我们测量了ea ch系统为回答各种查询所查询的时间r e。我们在foreach测试中设置了12000秒（约3 ho urs）的最大运行时间。在下面的代码中，当so me查询在这个时间限制内没有被解决时，系统的线就停止（注意，图在垂直轴上有一个对数刻度）。更详细地说，图9-11显示了各种测试的结果；通过对这些数据的分析，我们可以发现，在几个数量级上，D LVDB（图中的黑三角）的性能优于其他所有系统，而且DLVDB几乎总是处理最大量的数据；在某些测试中，XSB表现出良好的性能（例如在30 G.Terracina,N.Leone,V.Lio,C.Panettasamegen(X，Y)samegen(b1，Y)samegen(b1，b2)在a-图上可达(X，Y)在a-图上可达(b1，Y)在a-图上可达(b1，b2)在a-图上可达(b1，b2)在a-图上可达(b1，b2)。9.在树s和无环图和柱面上的可达性上的结果是相同的，但即使在那些阳性测试中，它也比LVDB更早“死亡”（除了柱面上的可达(b1,Y)外），可能是因为它超过了主存储器。LDL++在循环图和柱面上的可达(b1,Y)上与DLVDBonly竞争，而在所有其他查询中的性能都超过了一个数量级。DB-B在samegen（X,Y）上的性能接近DLVDBonly；在所有其他情况下，它的线都接近垂直轴。DB-A仅在tre es上显示了非常好的可达性（参见下面介绍的Alsotable1）。本系统中的优化机制特别适用于简单数据结构（如树）上的闭包计算，但不适用于其他（更复杂的）查询/数据结构。逻辑程序设计的理论与实践31在c-图上可达(X，Y)在c-图上可达(b1，Y)在c-图上可达(b1，b2)在圆柱上可达(X，Y)在圆柱上可达(b1，Y)在圆柱上可达(b1，b2)在圆柱上可达(b1，b2)在圆柱上可达(b1，b2)。10.

对于循环图和圆柱体的可达性，DBMSs通常具有最差的性能（它们的时间与垂直轴的距离），它们可以处理非常有限的输入数据。最后，不出所料，DLVIOs能够处理更少的数据量W.R.T.DLVDB；然而，在某些情况下，它是性能最好的三个系统之一，尤其是在绑定查询上。这主要归功于它所实现的魔术集优化技术，一个令人惊讶的结果是，即使在输入数据不是很大的情况下，DLVIO的执行时间几乎总是比DLVDB高。这一结果的动机可以通过以下推理得到。两个DLVDBand DLVIObene都来自DLV项目中开发的所有pr图重写优化技术；此外，这两种方法都实现了一种对正常程序的评价方法。然而，当dlvioreason-a tuple-at-time的方式来描述它的底层数据时，dlvdbb利用了一个tet-at-time32 G.Terracina,N.Leone,V.Lio,C.Panettareachable（X,Y）在树上可达（b 1,Y）在树上可达（b 1,b2)在树上可达（b 1,b2)。11.使用treesstrategy（通过SQL查询实现）实现可达性；在c语言中，由于底层工作数据库实现了先进的面向数据的优化策略，使得即使所有数据都存储在主存储器中，DLVDB也比DLVIO更有活力。正如（Bancilhon and Ramakrishnan 1988）中所指出的，在这种情况下，另一个重要的衡量参数是系统处理大量数据的能力。为了进行这个验证，我们考虑了每个系统对于我们在每个查询中使用的最大输入数据集的时间间隔。表1显示了对于那些可以在规定的12000se cond的时间限制内解决查询的系统测量的执行时间；表中的secondcolumn显示了每个查询的输入数据大小（以输入事实（元组）的数量为单位测量的）和处理的数据总量（以Mbytes为单位测量的），这些数据是由DLVDbinanswing该查询产生的答案集的大小给出的。通过对该表的分析，我们可以观察到:(i)DLVDba总是可以解决最大数据大小的查询；(ii)在15次查询中的11次中，DLVDB（一次与DLVIO一起）是唯一能够在时限内完成计算的系统；(iii)dlvdballow可以处理多达6.7Gbytes的samegen(X，Y)和1.6Gbytes的可达(X，Y)数据，注意dlvdbb为回答查询而产生的所有事实都考虑到了逻辑编程的理论和实践33table 1。

能够为输入数据的最大考虑大小/输入大小（元组）/DB-B dlviodlvdbldl++Smodels DB-A XSBData类型输出大小（Mbytes）（秒）（秒）（秒）（秒）（秒）（秒）（秒）（秒）samegen（X,Y）32766-–5552––––树6716 Mbsamegen(b1,Y）4194302––64––––树78 Mbsamegen(b1,b2)4194302––102––––树78 Mbreachable（X,Y）929945––11820––––A-graph 103 MB可达(b1,Y)929945--1191----A-graph38 MB可达(b1,b2)929945--4----A-Graph 17 MB可达(X，Y)612150--11936---C-Graph 68 MB可达(b1,Y)612150--11933---C-Graph 68 MB可达(b1,Y)612150-981 8-----C-Graph 11 MB可达(X，Y)23980--11784----柱体465 MB可达(b1,Y)145260--11654 2284--157柱体279 MB可达(b1,b2)582120--388----柱体13 MB可达(X，Y)4194302--1116 1-7280-树1634Mbreachable(b1,Y)4194302--76--6438-tree 79 Mbreachable(b1,b2)4194302--60--12-tree 78 mbtree在规定的12000 s econds时间限制内，并且从未像其他系统那样由于内存不足而结束计算。6.6与前面指出的DB-CAs相比，DB-C不支持递归查询的标准SQL99编码，但它利用专有的语言e来实现递归的m。对于递归，这种语言的表达能力不如SQL99；例如，非绑定的递归查询不能在DB-C中实现；类似地，以“统一”的方式（即独立于指定的绑定参数）编写重复视图也不是一件难事。对于本文中的proble ms地址，无论是为了可达性，还是为了与DB-C的同时代，都不可能编写非绑定的查询。其他查询的编码与我们为其他系统采用的通用版本不同。作为一个示例，查询q=reachable(b1,Y)可以在DB-C中用以下语句表示：select b1,edge.attfrom edgeSTART WITH att=b1 CONNECT BY priore att=attwhit，然而，它等效于datalog程序:reach(b1).reach(X):-reach(Y),edge(Y，X).reachable(b1,Y):-reach(Y)。34 G.Terracina,N.Leone,V.Lio,C.Panetta这显然是一个比通用编码更容易计算的pr图，因为它涉及一个递归规则，有一个单独的attr ibute和递归的唯一starting点（事实然而，这个查询（和等效程序）比第6.4节中介绍的查询不那么通用，因为它的结构必须修改，例如，如果我们需要绑定两个参数，或者如果我们想绑定第二个参数而不是参数，显然，用其他更通用的编码来测试这样的编码是不公平的。不管怎样，我们进行了一些涉及DB-C的测试，通过对各种查询的最大数据实例应用其编码，相应的datalog程序，以便对性能有一个roug h概念。例如，对于上述查询Q=可达(b1,Y)，在大小为929945（612150）元组的a-graphs（C-Graphs）上，我们测量了DBC需要22.5（re SP.15.9）秒，而DLVDB需要6.4（Resp.5.6）秒。类似地，对于查询Q=samegen(b1,Y)，在大小为4194302元组的树上，DB-C需要1329.4秒来终止计算，w他reas DLVDB需要500.0秒。8秒。对于树的可达性，DB-C优于DLVDBonly；同样在这种情况下，正如我们对DB-A所做的那样，我们可以推测这种行为是由系统中实现的特定优化技术所驱动的。这些结果在我们的基准测试中对DB-C测量的整体perfo rmance中具有代表性；一方面，他们支持我们的说法，即DB-C可解决的编码是非常直接的，也从性能的角度来看，W.R.T。

在我们的b enchmarks中使用的一般的（作为一个例子，这是由标准e nc oding中为D LVDBin可达(b1，Y)W.R.T.thesame查询测量的明显较低的定时所证明的）；另一方面，它们允许我们得出结论，与第6.5节中关于DLVDBperformance的相同的推理仍然有效。7结论在本文中，我们提出了DLVDB，一个新的对大量数据进行推理的演绎系统。它提供了e-cient DDS的特点，但也将处理驻留在外部数据库中的数据的能力扩展到dis连接逻辑编程系统。通过深入的实验验证，DLVDBB不仅在典型演绎查询的运行时间上有明显的提高，而且具有处理更大数据量的能力。现有系统。实验结果表明，DLVDBSigni在递归查询的计算方面明显优于商业DBMSs和其他基于逻辑的系统。我们的系统获得相关性能提高的关键原因是集成了以下几个因素：（一）利用商业DBMS的e-Cient工程进行规则计算的思想，通过转换SQLstatements中的逻辑规则（然后由DBMS执行），使我们能够利用面向数据的关系数据库优化技术。(ii)在逻辑程序设计的理论与实践35中开发的先进优化技术，用于逻辑查询的定性分析（例如，魔术集）。(iii)对上述构想进行适当的组合和精心设计的实施。此外，纯海量内存计算策略的使用，改进了以往演绎系统在实际应用中对输入数据维度的任何限制。未来，我们计划扩展直接数据库执行所支持的语言，并在数据集成和数据仓库等有趣的研究领域进行开发。此外，本文还提出了一种混合的方法，利用bothDLVDBand DLVIOexecutions来评估大容量内存上的难问题，部分地评估内存中的难问题。这项工作得到了意大利“探索农场”项目B01/0297/P42749-13和BYM.I.U.R.的大力支持。项目“Oton-DLV：Un ambiente basato sulla Programmazione LogicaDisgiuntiva per il trattamento di Ontologie”2521。参考资料纽约，纽约，1999年。美国国家标准协会:ANSI/ISO/IEC 9075-1999(SQL:1999,Parts 1-5）。Abiteboul,S.,Abrams,Z.,Haar,S.和Milo,T.2005。异步离散事件系统诊断：datalog的拯救！第二十四届ACMSIGACT-SIGMOD-SIGART数据库系统原理研讨会会议录(PODS2005)。巴尔的摩，马里兰州，美国，358-367。Apt,K.R.,Blair,H.A.和Walker,A.1988。走向声明知识的理论。《演绎数据库和逻辑程序设计的基础》。摩根·考夫曼出版社，华盛顿特区，第89-148页。Arni,F.,Ong,K.,Tsur,S.,Wang,H.和Zaniolo,C.2003。演绎数据库系统LDL++。逻辑c程序设计的理论与实践学报3,1,61-94。Balbin,I.和Ramamohanarao,K.1987。递归查询求值的一个推广。逻辑c编程学报4,3,259-262.班西尔洪,F.,Maier,F.,Sagiv,Y.和Ullman,J.1986.神奇的集合和其他奇怪的方式来实现逻辑程序。正在进行中。ACM数据库系统原理研讨会(PODS\'86)。ACM出版社，马萨诸塞州剑桥，1-16。Bancilhon,F.和Ramakrishnan,1988年。数据集约化程序的性能评估。演绎数据库和逻辑程序设计的基础。MorganKaufmann,439-517.Baral,C.2002。知识表示、推理和陈述性问题的解决。剑桥大学出版社，Beeri,C.和Ramakrisnhan,R.1991。

关于魔法的力量。逻辑程序设计杂志10,1-4,255-259。Ben-Eliyahu,R.和Dechter,R.1994。析取逻辑程序的命题语义。数学和艺术情报年鉴12,53-87.Ben-Eliyahu,R.和Dechter,R.1996。关于计算最小模型。《数学与艺术智能年鉴》18，1，3-27。塞里，S.，Gottlob，G.，Tanca，L.1990。逻辑程序设计和数据库。SpringerVerlag,New York,Dell\'Armi,T.,Faber,W.,Ielpa,G.,Leone,N.和Pfeifer,G.2003年a。D等值逻辑程序设计中的AggregateFunctions：语义、复杂性和在DLV中的实现。载于2003年第18届国际情报艺术会议录。Morgan Kaufmann出版社，墨西哥阿卡普尔科，847-852.36 G.Terracina,N.Leone,V.Lio,C.Panettadell\'Armi,T.,Faber,W.,Ielpa,G.Leone,N.和Pfeifer,G.2003年b。DLV中的ggregateFunctions。在论文集ASP03-回答集编程：理论和实现的进展，M.de Vos和A.Provetti编辑。意大利墨西拿，274-288。网上网址：http://ceur-ws.org/vol-78/.Faber,W.,Leone,N.,Mateis,C.和Pfeifer,G.1999a。利用数据库优化技术进行非单调推理。第7届演绎数据库与逻辑程序设计国际研讨会会议录(DDLP\'99),I.O.委员会编。日本Prolog协会，135-139，W.Faber，N.Leone，N.和Pfeifer，G.1999b.在DLP计算中推动目标派生。第5届国际逻辑程序设计与非单调推理会议论文集(LPNMR\'99),M.Gelfond,n.Leone,G.Pfeifer,第1730号载于AI课堂讲稿(LNAI)。Springer Verlag,El Paso,Texas,美国，177-191。Faber,W.,Leone,N.和Pfeifer,G.2001。对AnswerSet编程的启发式实验。载于2001年第十七届国际情报联合会议录。摩根考夫曼出版社，西雅图，华盛顿州，美国，635-640.费伯，西，利昂，北，和普费弗，G.2004。析取逻辑程序中的递归聚合：语义和复杂性。在进行中。JELIA的2004年。200-212.Faber,W.和Pfeifer,G.自1996年以来。DLV主页。http://www.dlvsystem.com/.Gallaire,H.,Minker,J.和Nicolas,J.1984年。逻辑和数据库：一个扣除IVEprocess。ACM计算调查16（2）,153-186.Garcia-Molina,H.,Ullman,J.D.和Widom,J.2000.数据库系统实现。Prentice Hall.Gebser,M.,Kaufmann,B.,Neumann,A.和Schaub,T.2007。Con Craict驱动的答案集求解。《接受国际艺术情报联合会议(IJCAI\'07)》，Gelfond,M.和Lifschitz诉1991年。逻辑程序和析取数据库中的经典运算。新一代计算9,365-385.Giunchiglia,E.,Lierler,Y.和Maratea,M.2006。基于命题可选性的答案集编程。接受自动推理的Jornal。Giunchiglia,E.Maratea,M.和Lierler,Y.2004。基于SAT的答案集编程。在美国艺术情报协会。AAAI出版社，61-66。格兰特，J.和明克，J.1992。逻辑编程对数据库的影响。ACM的来文35（3）,66-81。GRECO,S.2003。Boun d析取查询优化的绑定传播技术。IEEE知识与数据工程学报15,2,368-385.Knuth,D.E.1994。Stanford GraphBase：一个组合计算的平台。纽约ACM出版社。Leone,N.,Pfeifer,G.,Faber,W.,Eiter,T.,Gottlob,G.,Perri,S.和Scarcello,F.2004。知识表示和推理的DLV系统。C计算逻辑上的ACM事务。出现。可查阅：//www.arxiv.org/ps/cs.ai/0211004.Lin,F.和Zhao,Y.2002。ASS AT：用Satsolvers计算逻辑程序的答案集。在美国艺术情报协会。中国农业学会出版社，112-118.林福、赵勇，2004。ASS AT：用Satsolvers计算逻辑程序的答案集。

《艺术情报》157,1-2,115-137.Loo,B.,Hellerstein,J.,Stoica,I.和Ramakrishnan,R.2005。声明性路由：带有声明性查询的可扩展路由。在ACM SIGCOMM2005关于C计算机通信的应用、技术、体系结构和协议的会议记录中。美国宾夕法尼亚州费城，289-300.逻辑程序设计的理论与实践37Lu，J.，Nerode，A.，Subrahmanian,V.1996。混合知识库。IEEETRANS.诺尔。数据工程。8,5,773-785.Mumick,I.,Finkelstein,S.,Pirahesh,H.和Ramakrishnan,R.1996。MagicConditions.ACM反式。数据库系统21（1）,107-155。Niemel-a,I.和Simons,P.1997。Smodels-一个稳定模型的实现和正常逻辑程序的有根据的语义。第4届国际逻辑程序设计与非单调推理会议论文集(LPNMR\'97)。Dix，U.Furbach和A.Nerode编辑。AI课堂讲稿(LNAI),Vol.1265.德国，达格斯图尔，SpringerVerlag,420-429。Niemel-a,I.，Simons,P.和Syrj-anen,T.2000。smodels：一个用于回答设置编程的系统。《第八届非单调推理国际研讨会论文集》(NMR\'2000),C.Baral和M.Truszczy\'nski编辑。Breckenridge,Colorado,Usa.Przymusinski,T.C.1988。关于演绎数据库和逻辑程序的D扩展语义。在演绎数据库和逻辑程序设计的基础中，J。明克，艾德。摩根考夫曼出版社，193-216。Rao,P.,Sagonas,K.,Swift,T.,Warren,D.和Friere,J.1997。XSB：一个能够计算有充分基础语义的系统。我正在进行。第四届国际逻辑程序设计与非单调推理会议(LPNMR\'97)。斯普林格，林奈，430-440，罗斯，K，1990。带否定的datalog程序的模块化Strati和magic集。ACM数据库系统原理专题讨论会。Ullman,J.1989。数据库和知识库系统的原理。《计算机科学》，M.Winslett，2006。Raghu Ramakrishnan直言不讳。SIGMOD记录35,2,77-85.Zaniolo,C.,Ceri,S.,C.Faloutsos,Snodgrass,R.T.,Subrahmanian,V.S.,Andicari,R.1997.先进的数据库系统。摩根·考夫曼出版社。