《演绎数据库》PPT课件.ppt

《《演绎数据库》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《演绎数据库》PPT课件.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、LOGO第第4 4部分部分 其它高级主题其它高级主题第第1414章章 演绎数据库演绎数据库高级数据库系统及其应用高级数据库系统及其应用第第14章章 演绎数据库演绎数据库递归查询递归查询14.1演绎数据库理论基础演绎数据库理论基础14.2含否定的递归查询含否定的递归查询14.3有效赋值递归查询有效赋值递归查询14.42023/2/6214.1 递归查询递归查询v一种包含递归的复杂数据结构关系示例一种包含递归的复杂数据结构关系示例三轮车三轮车零配件库存关系表零配件库存关系表Assembly有三个字段：有三个字段：part(配件配件)/subpart(子配件子配件)/qty(数量数量)。关系的每个元

2、组表示一配件中含某类子配件的数量。关系的每个元组表示一配件中含某类子配件的数量。显然，显然，SQL-92对表达类似：对表达类似：“一个一个strike(三轮车三轮车)总共总共有哪些配件？有哪些配件？”这样的查询无能为力。这样的查询无能为力。【注注】若若Assembly关系中只有几个固定元组，或许可通过关系中只有几个固定元组，或许可通过写多个自连接并将这些自连接用写多个自连接并将这些自连接用union组合起来的方式勉强组合起来的方式勉强处理，但这种特定、非通用查询表达并不是我们感兴趣的。处理，但这种特定、非通用查询表达并不是我们感兴趣的。2023/2/63Datalog基本知识基本知识(1)vD

3、atalog是一个特别构造的专业名词是一个特别构造的专业名词它是一个专业构造词，表达数据data、逻辑logic的含义。它是一种受著名逻辑编程语言Prolog启发而发展起来的关系语言，并基本遵循Prolog的标记法。v由多条由多条Datalog规则有机组合可形成逻辑程序规则有机组合可形成逻辑程序例如，为查询每个配件的构成组件（即子配件），可能会先定义一个名为Components的中间结果关系，并构造如下包含两条Datalog规则的逻辑程序:Components(Part,SubPart):-Assembly(Part,Subpart,Qty).Components(Part,SubPart):

4、-Assembly(Part,Part2,Qty),Components(Part2,SubPart)r1:r2:2023/2/64Datalog基本知识基本知识(2)vDatalog规则规则Components(Part,SubPart):-Assembly(Part,Subpart,Qty).Components(Part,SubPart):-Assembly(Part,Part2,Qty),Components(Part2,SubPart)符号“:-”表示逻辑蕴含，其右边部分称为规则规则体体(body)、左边部分称为规则头规则头(head)。如果“规则体中提及的元组存在于DB关系中”，则

5、蕴含着“规则头中的元组也必定在提及它DB关系中”。r1:r2:因为，基于因为，基于Componenets和和Assembly关系中已有的关系中已有的元组，通过应用这两条规则，我们就能推理元组，通过应用这两条规则，我们就能推理(infer/deduct)出一些属于出一些属于Components的新元组。的新元组。所以，支持所以，支持Datalog规则的规则的DBMS常被称为常被称为演绎数据库演绎数据库2023/2/65Datalog基本知识基本知识(3)vDatalog规则与关系代数规则与关系代数应用Datalog规则也可由关系代数的有关概念来理解。(r1)相当于简单对Assembly关系运用投

6、影投影结果加到最初为空的Components关系中。(r2)连接Assembly关系和Components，并执行一次含part,subpart字段的投影。投影结果以union方式加入到Components关系中。唯一的、不能用关系代数解释的一个Datalog操作，是反复应用规则来定义Components，直到没有新元组产生为止。重复应用一规则集操作，称为不动点不动点(fixpoint)操作。vDatalog与一阶谓词逻辑关系与一阶谓词逻辑关系一阶谓词逻辑(First Order Logic,FOL)2023/2/66Datalog基本知识基本知识(4)vDatalog规则与关系代数规则与关系

7、代数vDatalog与一阶谓词逻辑与一阶谓词逻辑(FOL)关系关系本质上，Datalog是FOL中Horn子句表示法的子集，是通过对FOL的Horn子句进一步限定而发展起来的，并主要用于演绎数据库的一种简单知识表达语言。Datalog规则的一般形式为：2023/2/67利用利用Datalog规则进行推理规则进行推理 v示例：以图示例：以图14.1(a)中的中的Assembly实例为输入，利用实例为输入，利用由规则由规则r1/r2构成的逻辑程序进行推理构成的逻辑程序进行推理,具体推理步如下具体推理步如下:1）应用规则(r1)，将获得图14.2（a）所示的Components元组集。2）应用规则(

8、r2)后，将产生如图14.2（b）所示的一组Components新元组。新元组由粗矩形框特别标识，共有6个元组。3）再次应用(r2)后，除了会重复产生（发现）首次应用规则(r2)所产生的那6个元组外，还将额外产生如图14.2（c）中粗矩形框内标识的两个新元组。4）第三次应用(r2)，将不会再产生任何新元组。这说明，推理工作已完成。2023/2/68利用规则利用规则(r1-r2)进行推理的结果示例进行推理的结果示例(图图14.2)有了这个推理结果，仅通过使有了这个推理结果，仅通过使用一个极简单的用一个极简单的SQL语句，就可语句，就可获得获得strike的所有配件：的所有配件：SELECT *F

9、ROM Components C2 WHERE C2.part=trike Components基于基于Datalog定义的定义的SQL99扩展表达扩展表达：WITH RECURSIVE Components(part,Subpart)AS (SELECT A1.Part,A1,Subpart FROM Assembly A1)UNION (SELECT A2.Part,C1,Subpart FROM Assembly A2,Components C1 WHERE A2.Subpart=C1.Part).2023/2/6914.2 演绎数据库理论基础演绎数据库理论基础14.4.1 最小模型语义

10、 14.2.2 安全Datalog程序14.2.3 不动点操作14.2.4 最小模型与不动点模型关系 2023/2/610Datalog程序语义程序语义v可将可将Datalog程序中的关系分为输入关系和输出关系两程序中的关系分为输入关系和输出关系两类。当我们理解了已有输入关系实例如何通过类。当我们理解了已有输入关系实例如何通过Datalog程序与输出关系关联后，一个查询的含义程序与输出关系关联后，一个查询的含义(语义）就会清语义）就会清晰起来。晰起来。输出关系指由规则定义的关系，故也被称为计算关系，如规则(r1-r2)中的Components。输入关系一般对应DB中已有的实关系表，也称为外部关

11、系。给定所有输入关系的一个实例，我们必须计算出输出关系的实例。v可通过独立理解每条规则的含义来理解一个可通过独立理解每条规则的含义来理解一个Datalog程序。程序。每条规则的语义是：如果规则体为真，则规则头也必为真。如果给定了所有出现在规则体中关系的元组，则在规则头提及的关系必包含特定元组集。2023/2/611最小模型语义最小模型语义(least model semantics)v模型(model)定义一个模型是通过一个程序关联的一组关系实例集合。当对程序中的每个规则，用一组常数替换规则中的变量时，以下断言为真：“如果（通过用常数替换规则变量）得到的规则体表示元组属于相应关系的实例，则由规

12、则头产生的元组也应出现在提及它的对应关系实例中。”在给定了所有输入关系的实例后，一个模型定义实质上限制了输出关系实例。v最小模型定义最小模型定义一个程序的最小模型是这样一个模型M，对同样程序的任何其它模型M2，以及对程序中的每个关系R，R在M中的实例将属于R在M2中的实例。v最小模型定义给用户提供了一种不需要了最小模型定义给用户提供了一种不需要了解程序如何执行就可理解程序的方式。解程序如何执行就可理解程序的方式。它是一种声明性的语义，就象关系演算一样不需要了解任何具体的关系操作或操作实现。这一点非常重要，由于递归规则的存在，以赋值策略概念来理解程序有时往往会非常困难。2023/2/61214.

13、2.2 安全安全Datalog程序程序v如果一个程序的最小模型不是有限的，就称该程如果一个程序的最小模型不是有限的，就称该程序是不安全的序是不安全的(unsafed)。DB系统不允许不安全的程序。系统不允许不安全的程序。v如果所有输入关系是有限的，且每个出现在规则如果所有输入关系是有限的，且每个出现在规则头中的每个变量，都至少在规则体中出现过，则头中的每个变量，都至少在规则体中出现过，则程程Datalog程序是范围限制的。程序是范围限制的。每个范围限制的肯定都有一个有限的最小模型。每个范围限制的肯定都有一个有限的最小模型。v示例示例一个安全的Datalog程序：Complex_Parts(Pa

14、rt):-Assembly(Part,Subpart,Qty),Qty2 一个不安全的Datalog程序：Price_Parts(Part,Price):-Assembly(Part,Subpart,Qty),Qty2(r3):(r4):2023/2/61314.2.3 不动点不动点（least fixpoint）操作操作v函数函数f的最小不动点（的最小不动点（least fixpoint）是f的一个不动点，且该不动点小于f的任何其它不动点。通常一个函数并不能保证总有最小不动点。举例double(v1,v2,vn)=2*v1,2*v2,2*vn。double+(v1,v2,vn)=double

15、(v1,v2,vn)v1,v2,vn。例如，例如，double(1,2,5)=2,4,10；double+(1,2,5)=1,2,4,5,10。显然，所有偶整数集（显然，所有偶整数集（even_ints）和所有整数集）和所有整数集（all_ints）都是都是double+函数的一个不动点，且有函数的一个不动点，且有even_ints2,not Small(Part)Small(Part):-Assembly(Part,Subpart,Qty),not Big(Part).如果我们应用规则(r5-r6)到图14.1(a)的Assembly关系实例，并假设初始时Small/Big关系为空集。会发现

16、：按先(r5)后(r6)，与按先(r6)后(r5)的顺序应用规则，会得到不同的结果！v显然，为确保程序的安全性，如果规则允许在其显然，为确保程序的安全性，如果规则允许在其body中中包含包含not，则必须增加范围限制定义。，则必须增加范围限制定义。如果在规则体中出现的某个关系之前有如果在规则体中出现的某个关系之前有not，我们就称它是该关，我们就称它是该关系的一个否定出现，否则，则称它该关系的一个肯定出现。系的一个否定出现，否则，则称它该关系的一个肯定出现。称一个程序是范围限制的，如果出现在规则头的每个变量，都曾称一个程序是范围限制的，如果出现在规则头的每个变量，都曾出现在一些肯定出现的规则体

17、关系中。出现在一些肯定出现的规则体关系中。（r5:）（r6:）图图14.3 Big/Small程序的两个不动点程序的两个不动点 2023/2/61814.3.2 分层概念（分层概念（1）v处理含否定问题的常用方案处理含否定问题的常用方案在程序上施加特定的语法限制。这个限制很容易检查，且满足该限制的程序具有很自然的含义。v称一个表称一个表T依赖于表依赖于表S，如果存在这样的规则：，如果存在这样的规则：在其head中含有T，且在其body中或含有S或含有可递归依赖于S的谓词。一个递归定义的谓词总是依赖于自己。例如，Big依赖于Small，而Small又依赖Bigv称一个表称一个表T否定依赖于表否定

18、依赖于表S，如果存在这样的规则：，如果存在这样的规则：在其head中含有T，且在其body中或含有not S或含有可递归依赖于not S的谓词 2023/2/61914.3.2 分层概念（分层概念（2）v变换变换/分类一个程序中的所有关系，使它们形成一个层次分类一个程序中的所有关系，使它们形成一个层次化结构的一般步骤：化结构的一般步骤：将不依赖于其它任何表的表安排在第将不依赖于其它任何表的表安排在第0层。层。将只依赖于将只依赖于0/1层的表，或只否定依赖于层的表，或只否定依赖于0层表的那些表，安排在层表的那些表，安排在第第1层。层。一般地，我们将只依赖于一般地，我们将只依赖于(i-1)/i以下

19、层的表，或只否定依赖于以下层的表，或只否定依赖于(i-1)以下层中表的那些表，安排在第以下层中表的那些表，安排在第i层。层。v一个专门的分层程序，是指能按上述算法对任何逻辑程序一个专门的分层程序，是指能按上述算法对任何逻辑程序进行分层的程序。进行分层的程序。v分层化逻辑程序，给了我们一个赋值规则的自然顺序。分层化逻辑程序，给了我们一个赋值规则的自然顺序。分层的程序可采用由低到高的顺序逐层进行赋值。当规则按分层顺序赋值时，结果是一个唯一的不动点，它也是程序的一个最小不动点（即使程序可能有不止一个最小不动点)。2023/2/62014.3.2 分层概念（分层概念（3）v示例：一个经过分层改进的示例

20、：一个经过分层改进的Big/Small程序：程序：Big2(Part):-Assembly(Part,Subpart,Qty),Qty2Small2(Part):-Assembly(Part,Subpart,Qty),not Big(Part).显然,这个改进程序是分层的。Small2依赖于Big2，但Big2不依赖Small2。分层结构：Assembly在层0;Big2在层1;Small2在层2。（r7:）（r8:）2023/2/62114.3.3 聚合操作聚合操作v有些有些Datalog程序可扩展为带程序可扩展为带SQL-风格的分组和聚合操风格的分组和聚合操作。考虑下面的程序：作。考虑下面

21、的程序：NumParts(Part,Sum():-Assembly(Part,Subpart,Qty).这个程序等价于下面的SQL查询：SELECT A.Part,SUM(A.Qty)FROM Assembly AGROUP BY A.Part这类这类Datalog程序的赋值过程通常可分两步进行：程序的赋值过程通常可分两步进行：先为每个被聚合项(即part)收集计算值;并将多值集存储在临时关系的一个单独列上；然后应用SUM函数到这个存储多集值的临时列上（r9）2023/2/622含分组聚合操作含分组聚合操作Datalog程序的赋值过程示例程序的赋值过程示例1)先为每个先为每个part值收集对应

22、的值收集对应的Qty数量值数量值;2)然后应用然后应用SUM函数到该列的每个多集值上函数到该列的每个多集值上2023/2/62314.3.3 聚合操作聚合操作v利用聚合函数时也可能导致类似利用聚合函数时也可能导致类似not所导致的问题，分层所导致的问题，分层思想也可被用到带有聚合操作的程序中。思想也可被用到带有聚合操作的程序中。v考虑下面的程序：考虑下面的程序：NumComps(Part,COUNT():-Components(Part,Subpart).Components(Part,SubPart):-Assembly(Part,Subpart,Qty).Components(Part,S

23、ubPart):-Assembly(Part,Part2,Qty),Components(Part2,SubPart).该程序的基本思想是要计算每个配件的子配件数量该程序的基本思想是要计算每个配件的子配件数量。须等待直到须等待直到Components赋值全部完成之后，才能应赋值全部完成之后，才能应用用NumComps规则。否则，就可能得到不完全的计数。规则。否则，就可能得到不完全的计数。这个情况非常类似于面对否定时遇到的问题。这个情况非常类似于面对否定时遇到的问题。在应用一个包含使用在应用一个包含使用not的规则之前，我们不得不先完全赋值的规则之前，我们不得不先完全赋值带否定的关系。带否定的关

24、系。2023/2/62414.4 有效赋值递归查询有效赋值递归查询14.4.1 没有重复推导的不动点赋值 14.4.2 魔集算法2023/2/625用质朴法赋值递归查询用质朴法赋值递归查询v质朴不动点赋值法质朴不动点赋值法(naive fixpoint evaluation)通过简单的反复应用规则来计算不动点。所有程序规则的一次应用称为一次循环。为到达不动点，我们通常需要执行多次循环。为到达不动点，我们通常需要执行多次循环。v这个方法有两个主要缺陷：这个方法有两个主要缺陷：存在重复推理存在重复推理同一个元组，会在同一规则、同一方式下被多次导同一个元组，会在同一规则、同一方式下被多次导出。出。存

25、在不必要推理存在不必要推理每次推理总是进行完全的计算，未能利用查询信息每次推理总是进行完全的计算，未能利用查询信息（如选择条件）限制推理范围。（如选择条件）限制推理范围。2023/2/62614.4.1 没有重复推导的不动点赋值（半质朴法）没有重复推导的不动点赋值（半质朴法）v记住前次应用规则时已进行过的推理，以便在下记住前次应用规则时已进行过的推理，以便在下次应用规则时，不再执行这些推理。具体做法：次应用规则时，不再执行这些推理。具体做法：跟踪最新一次应用递归规则所产生的新元组。比如，可通过将最新一次应用递归规则(r1-r2)所产生的Components新元组，存储到一个临时关系Delt_C

26、omponents中。再次应用规则进行推理时，只使用前一次导出的、递归谓词中的新元组比如，只用Delt_Components中的元组结合Assembly进行推理。v这种改进的不动点赋值法，称为半质朴不动点赋这种改进的不动点赋值法，称为半质朴不动点赋值法值法(seminaive fixpoint evaluation)。2023/2/62714.4.1 没有重复推导的不动点赋值（半质朴法）没有重复推导的不动点赋值（半质朴法）v与质朴法相比，半质朴法有以下重要特征：与质朴法相比，半质朴法有以下重要特征：需要为每个递归谓词(如Component元组)维持一个增量版本，以跟踪最新一次循环产生的该谓词对

27、应元组。每个递归谓词增量版本应在每次循环结束后更新一次。原程序规则被重写为确保每次推理只使用最新增量元组，即需将规则中递归谓词用增量版本的递归谓词替代。Components(trike,rim):-Assembly(trike,wheel,1),delta_Components(wheel,rim).Components(trike,tube):-Assembly(trike,wheel,1),delta_Components(wheel,tube).2023/2/62814.4.2 魔集算法魔集算法v对非递归查询赋值，通过在查询表达中指定的额对非递归查询赋值，通过在查询表达中指定的额外选择，

28、可限制计算的范围，从而提高赋值效率。外选择，可限制计算的范围，从而提高赋值效率。v在含有递归定义的查询中，这个方法仍然有效，在含有递归定义的查询中，这个方法仍然有效，但问题处理将变得更加复杂。但问题处理将变得更加复杂。考虑下面这个查询考虑下面这个查询三轮车同层次配件三轮车同层次配件的程序的程序,并假设并假设我们希望查的是我们希望查的是S1值限制为值限制为spoke的所有的所有SameLevel元组：元组：SameLevel(S1,S2):-Assembly(P1,S1,Q1),Assembly(P1,S2,Q2)SameLevel(S1,S2):-Assembly(P1,S1,Q1),Same

29、Level(P1,P2),Assembly(P2,S2,Q2)在“配件层次树”中，如果从S1沿向上最短路径到达根节点需要穿越的边数，与从根节点沿向下最短路径到达S2需穿越的边数相同，则认为S1和S2是“同层次配件”。2023/2/62914.4.2 魔集算法魔集算法v处理查询：在处理查询：在“配件层次树中检索三轮车同层次配件配件层次树中检索三轮车同层次配件”SameLevel(S1,S2):-Assembly(P1,S1,Q1),Assembly(P1,S2,Q2)SameLevel(S1,S2):-Assembly(P1,S1,Q1),SameLevel(P1,P2),Assembly(P2

30、,S2,Q2)直观上看，我们必须计算所有SameLevel元组，它们的首字段值在从spoke到根的最短路径上。每个这样元组对本例查询结果都有潜在的贡献。但另一方面，如果计算所有的SameLevel表元组，则显然会很浪费。为了既不浪费，又不遗漏潜在有用的中间元组，我们定义一个称为定义一个称为Magic_SameLevel的新表的新表，在该表的每个元组中存储一个对计算给定查询有用值本例：存储从spoke到根的最短路径上Samelevel:S1值。2023/2/63014.4.2 魔集算法魔集算法v处理查询：在处理查询：在“配件层次树中检索三轮车同层次配件配件层次树中检索三轮车同层次配件”SameL

31、evel(S1,S2):-Assembly(P1,S1,Q1),Assembly(P1,S2,Q2)SameLevel(S1,S2):-Assembly(P1,S1,Q1),SameLevel(P1,P2),Assembly(P2,S2,Q2)按魔集处理思想改进，可得到如下新程序：Magic_SameLevel(spoke)Magic_SameLevel(P1):-Assembly(P1,S1,Q1),Magic_SameLevel(S1)SameLevel(S1,S2):-Magic_SameLevel(S1),Assembly(P1,S1,Q1),Assembly(P1,S2,Q2)Sam

32、eLevel(S1,S2):-Magic_SameLevel(S1),Assembly(P1,S1,Q1),SameLevel(P1,P2),Assembly(P2,S2,Q2)这个修改后的程序常被称为修改后的程序常被称为魔集魔集(magic sets)程序程序。2023/2/63114.4.2 魔集算法魔集算法v从一般从一般Datalog程序获得魔集程序的改写算法描述程序获得魔集程序的改写算法描述算法的输入与输出算法输入：包括程序本身和一个查询形式。可由查询形式，获得要查询的关系，以及一个具体的查询字段限制值（查询常数）。当重写程序被赋值时，查询常数被用来限制计算范围。算法输出：是一个重写的魔集程序。在原始程序中增加魔集过滤器修改程序的每条规则在规则体中增加魔集过滤条件，以过滤该规则产生的元组集。定义魔集关系为定义作为过滤器的魔集关系，为此，必须创建一个新规则。直观上看，通过分析输出关系R在程序规则体的每次出现，有助于我们确定魔集关系。2023/2/632