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

,第4部分 其它高级主题第14章 演绎数据库,高级数据库系统及其应用,2023/7/19,2,第14章 演绎数据库,递归查询,14.1,演绎数据库理论基础,14.2,含否定的递归查询,14.3,有效赋值递归查询,14.4,2023/7/19,3,14.1 递归查询,一种包含递归的复杂数据结构关系示例三轮车零配件库存关系表Assembly有三个字段：part(配件)/subpart(子配件)/qty(数量)。关系的每个元组表示一配件中含某类子配件的数量。,显然，SQL-92对表达类似：“一个strike(三轮车)总共有哪些配件？”这样的查询无能为力。【注】若Assembly关系中只有几个固定元组，或许可通过写多个自连接并将这些自连接用union组合起来的方式勉强处理，但这种特定、非通用查询表达并不是我们感兴趣的。,2023/7/19,4,Datalog基本知识(1),Datalog是一个特别构造的专业名词它是一个专业构造词，表达数据data、逻辑logic的含义。它是一种受著名逻辑编程语言Prolog启发而发展起来的关系语言，并基本遵循Prolog的标记法。由多条Datalog规则有机组合可形成逻辑程序例如，为查询每个配件的构成组件（即子配件），可能会先定义一个名为Components的中间结果关系，并构造如下包含两条Datalog规则的逻辑程序:Components(Part,SubPart):-Assembly(Part,Subpart,Qty).Components(Part,SubPart):-Assembly(Part,Part2,Qty),Components(Part2,SubPart),r1:,r2:,2023/7/19,5,Datalog基本知识(2),Datalog规则Components(Part,SubPart):-Assembly(Part,Subpart,Qty).Components(Part,SubPart):-Assembly(Part,Part2,Qty),Components(Part2,SubPart)符号“:-”表示逻辑蕴含，其右边部分称为规则体(body)、左边部分称为规则头(head)。如果“规则体中提及的元组存在于DB关系中”，则蕴含着“规则头中的元组也必定在提及它DB关系中”。,r1:,r2:,因为，基于Componenets和Assembly关系中已有的元组，通过应用这两条规则，我们就能推理(infer/deduct)出一些属于Components的新元组。所以，支持Datalog规则的DBMS常被称为演绎数据库,2023/7/19,6,Datalog基本知识(3),Datalog规则与关系代数应用Datalog规则也可由关系代数的有关概念来理解。(r1)相当于简单对Assembly关系运用投影投影结果加到最初为空的Components关系中。(r2)连接Assembly关系和Components，并执行一次含part,subpart字段的投影。投影结果以union方式加入到Components关系中。唯一的、不能用关系代数解释的一个Datalog操作，是反复应用规则来定义Components，直到没有新元组产生为止。重复应用一规则集操作，称为不动点(fixpoint)操作。Datalog与一阶谓词逻辑关系一阶谓词逻辑(First Order Logic,FOL),2023/7/19,7,Datalog基本知识(4),Datalog规则与关系代数Datalog与一阶谓词逻辑(FOL)关系本质上，Datalog是FOL中Horn子句表示法的子集，是通过对FOL的Horn子句进一步限定而发展起来的，并主要用于演绎数据库的一种简单知识表达语言。Datalog规则的一般形式为：,2023/7/19,8,利用Datalog规则进行推理,示例：以图14.1(a)中的Assembly实例为输入，利用由规则r1/r2构成的逻辑程序进行推理,具体推理步如下:1）应用规则(r1)，将获得图14.2（a）所示的Components元组集。2）应用规则(r2)后，将产生如图14.2（b）所示的一组Components新元组。新元组由粗矩形框特别标识，共有6个元组。3）再次应用(r2)后，除了会重复产生（发现）首次应用规则(r2)所产生的那6个元组外，还将额外产生如图14.2（c）中粗矩形框内标识的两个新元组。4）第三次应用(r2)，将不会再产生任何新元组。这说明，推理工作已完成。,2023/7/19,9,利用规则(r1-r2)进行推理的结果示例(图14.2),有了这个推理结果，仅通过使用一个极简单的SQL语句，就可获得strike的所有配件：SELECT*FROM 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/7/19,10,14.2 演绎数据库理论基础,14.4.1 最小模型语义,14.2.2 安全Datalog程序,14.2.3 不动点操作,14.2.4 最小模型与不动点模型关系,2023/7/19,11,Datalog程序语义,可将Datalog程序中的关系分为输入关系和输出关系两类。当我们理解了已有输入关系实例如何通过Datalog程序与输出关系关联后，一个查询的含义(语义）就会清晰起来。输出关系指由规则定义的关系，故也被称为计算关系，如规则(r1-r2)中的Components。输入关系一般对应DB中已有的实关系表，也称为外部关系。给定所有输入关系的一个实例，我们必须计算出输出关系的实例。可通过独立理解每条规则的含义来理解一个Datalog程序。每条规则的语义是：如果规则体为真，则规则头也必为真。如果给定了所有出现在规则体中关系的元组，则在规则头提及的关系必包含特定元组集。,2023/7/19,12,最小模型语义(least model semantics),模型(model)定义一个模型是通过一个程序关联的一组关系实例集合。当对程序中的每个规则，用一组常数替换规则中的变量时，以下断言为真：“如果（通过用常数替换规则变量）得到的规则体表示元组属于相应关系的实例，则由规则头产生的元组也应出现在提及它的对应关系实例中。”在给定了所有输入关系的实例后，一个模型定义实质上限制了输出关系实例。最小模型定义一个程序的最小模型是这样一个模型M，对同样程序的任何其它模型M2，以及对程序中的每个关系R，R在M中的实例将属于R在M2中的实例。,最小模型定义给用户提供了一种不需要了解程序如何执行就可理解程序的方式。它是一种声明性的语义，就象关系演算一样不需要了解任何具体的关系操作或操作实现。这一点非常重要，由于递归规则的存在，以赋值策略概念来理解程序有时往往会非常困难。,2023/7/19,13,14.2.2 安全Datalog程序,如果一个程序的最小模型不是有限的，就称该程序是不安全的(unsafed)。DB系统不允许不安全的程序。如果所有输入关系是有限的，且每个出现在规则头中的每个变量，都至少在规则体中出现过，则程Datalog程序是范围限制的。每个范围限制的肯定都有一个有限的最小模型。示例一个安全的Datalog程序：Complex_Parts(Part):-Assembly(Part,Subpart,Qty),Qty2 一个不安全的Datalog程序：Price_Parts(Part,Price):-Assembly(Part,Subpart,Qty),Qty2,(r3):,(r4):,2023/7/19,14,14.2.3 不动点（least fixpoint）操作,函数f的最小不动点（least fixpoint）是f的一个不动点，且该不动点小于f的任何其它不动点。通常一个函数并不能保证总有最小不动点。举例double(v1,v2,vn)=2*v1,2*v2,2*vn。double+(v1,v2,vn)=double(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_ints all_ints模型的最小不动点,2023/7/19,15,14.2.3 不动点（least fixpoint）操作,函数f的最小不动点（least fixpoint）模型的最小不动点以元组集作为值集、用关系代数表达作为函数，对应到函数的最小不动点定义，不难得到关于模型的最小不动点定义。例如，对前面Components关系，也可按如下来定义：Components=1,5(Assembly 2=1Components)1,2(Assembly)=f(Components,Assembly)这个函数不动点是一个满足以上等式的Components实例。如果不断应用规则（r1-r2），总能不断产生新的、不在原Components实例中的元组，则当前Components实例就不是不动点。,2023/7/19,16,14.2.4 最小模型与不动点模型关系,结论：每个基于关系代数表达定义的、不包含集合差（或not）操作符的函数都可确保有一个最小不动点，且最小不动点可通过反复赋值函数来求解。更进一步结论：每个不含否定的Datalog程序可确保有一个最小模型，且最小模型等于该程序的最小不动点。这些结论为我们提供了Datalog查询处理的理论基础。基于最小模型理论，用户可用“如果规则体为true，则规则头亦为true”的概念术语来理解一个程序；而根据不动点理论，DBMS可通过反复应用程序规则来求解不动点。对这些结论的证明已超出本书范围。但如果规则体中包含了集合差或否定运算，逻辑程序就不再能保证有最小模型或最小不动点。,2023/7/19,17,14.3 含否定的递归查询,14.3.1 范围限制与否定,14.3.2 分层概念,14.3.3 聚合操作,2023/7/19,18,14.3.1 范围限制与否定,考虑下面含有否定的逻辑程序,规则(r5-r6)：Big(Part):-Assembly(Part,Subpart,Qty),Qty2,not Small(Part)Small(Part):-Assembly(Part,Subpart,Qty),not Big(Part).如果我们应用规则(r5-r6)到图14.1(a)的Assembly关系实例，并假设初始时Small/Big关系为空集。会发现：按先(r5)后(r6)，与按先(r6)后(r5)的顺序应用规则，会得到不同的结果！显然，为确保程序的安全性，如果规则允许在其body中包含not，则必须增加范围限制定义。如果在规则体中出现的某个关系之前有not，我们就称它是该关系的一个否定出现，否则，则称它该关系的一个肯定出现。称一个程序是范围限制的，如果出现在规则头的每个变量，都曾出现在一些肯定出现的规则体关系中。,（r5:）,（r6:）,2023/7/19,19,14.3.2 分层概念（1）,处理含否定问题的常用方案在程序上施加特定的语法限制。这个限制很容易检查，且满足该限制的程序具有很自然的含义。称一个表T依赖于表S，如果存在这样的规则：在其head中含有T，且在其body中或含有S或含有可递归依赖于S的谓词。一个递归定义的谓词总是依赖于自己。例如，Big依赖于Small，而Small又依赖Big称一个表T否定依赖于表S，如果存在这样的规则：在其head中含有T，且在其body中或含有not S或含有可递归依赖于not S的谓词,2023/7/19,20,14.3.2 分层概念（2）,变换/分类一个程序中的所有关系，使它们形成一个层次化结构的一般步骤：将不依赖于其它任何表的表安排在第0层。将只依赖于0/1层的表，或只否定依赖于0层表的那些表，安排在第1层。一般地，我们将只依赖于(i-1)/i以下层的表，或只否定依赖于(i-1)以下层中表的那些表，安排在第i层。一个专门的分层程序，是指能按上述算法对任何逻辑程序进行分层的程序。分层化逻辑程序，给了我们一个赋值规则的自然顺序。分层的程序可采用由低到高的顺序逐层进行赋值。当规则按分层顺序赋值时，结果是一个唯一的不动点，它也是程序的一个最小不动点（即使程序可能有不止一个最小不动点)。,2023/7/19,21,14.3.2 分层概念（3）,示例：一个经过分层改进的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/7/19,22,14.3.3 聚合操作,有些Datalog程序可扩展为带SQL-风格的分组和聚合操作。考虑下面的程序：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/7/19,23,含分组聚合操作Datalog程序的赋值过程示例,1)先为每个part值收集对应的Qty数量值;2)然后应用SUM函数到该列的每个多集值上,2023/7/19,24,14.3.3 聚合操作,利用聚合函数时也可能导致类似not所导致的问题，分层思想也可被用到带有聚合操作的程序中。考虑下面的程序：NumComps(Part,COUNT():-Components(Part,Subpart).Components(Part,SubPart):-Assembly(Part,Subpart,Qty).Components(Part,SubPart):-Assembly(Part,Part2,Qty),Components(Part2,SubPart).该程序的基本思想是要计算每个配件的子配件数量。须等待直到Components赋值全部完成之后，才能应用NumComps规则。否则，就可能得到不完全的计数。这个情况非常类似于面对否定时遇到的问题。在应用一个包含使用not的规则之前，我们不得不先完全赋值带否定的关系。,2023/7/19,25,14.4 有效赋值递归查询,14.4.1 没有重复推导的不动点赋值,14.4.2 魔集算法,2023/7/19,26,用质朴法赋值递归查询,质朴不动点赋值法(naive fixpoint evaluation)通过简单的反复应用规则来计算不动点。所有程序规则的一次应用称为一次循环。为到达不动点，我们通常需要执行多次循环。这个方法有两个主要缺陷：存在重复推理同一个元组，会在同一规则、同一方式下被多次导出。存在不必要推理每次推理总是进行完全的计算，未能利用查询信息（如选择条件）限制推理范围。,2023/7/19,27,14.4.1 没有重复推导的不动点赋值（半质朴法）,记住前次应用规则时已进行过的推理，以便在下次应用规则时，不再执行这些推理。具体做法：跟踪最新一次应用递归规则所产生的新元组。比如，可通过将最新一次应用递归规则(r1-r2)所产生的Components新元组，存储到一个临时关系Delt_Components中。再次应用规则进行推理时，只使用前一次导出的、递归谓词中的新元组比如，只用Delt_Components中的元组结合Assembly进行推理。这种改进的不动点赋值法，称为半质朴不动点赋值法(seminaive fixpoint evaluation)。,2023/7/19,28,14.4.1 没有重复推导的不动点赋值（半质朴法）,与质朴法相比，半质朴法有以下重要特征：需要为每个递归谓词(如Component元组)维持一个增量版本，以跟踪最新一次循环产生的该谓词对应元组。每个递归谓词增量版本应在每次循环结束后更新一次。原程序规则被重写为确保每次推理只使用最新增量元组，即需将规则中递归谓词用增量版本的递归谓词替代。Components(trike,rim):-Assembly(trike,wheel,1),delta_Components(wheel,rim).Components(trike,tube):-Assembly(trike,wheel,1),delta_Components(wheel,tube).,2023/7/19,29,14.4.2 魔集算法,对非递归查询赋值，通过在查询表达中指定的额外选择，可限制计算的范围，从而提高赋值效率。在含有递归定义的查询中，这个方法仍然有效，但问题处理将变得更加复杂。考虑下面这个查询三轮车同层次配件的程序,并假设我们希望查的是S1值限制为spoke的所有SameLevel元组：SameLevel(S1,S2):-Assembly(P1,S1,Q1),Assembly(P1,S2,Q2)SameLevel(S1,S2):-Assembly(P1,S1,Q1),SameLevel(P1,P2),Assembly(P2,S2,Q2)在“配件层次树”中，如果从S1沿向上最短路径到达根节点需要穿越的边数，与从根节点沿向下最短路径到达S2需穿越的边数相同，则认为S1和S2是“同层次配件”。,2023/7/19,30,14.4.2 魔集算法,处理查询：在“配件层次树中检索三轮车同层次配件”SameLevel(S1,S2):-Assembly(P1,S1,Q1),Assembly(P1,S2,Q2)SameLevel(S1,S2):-Assembly(P1,S1,Q1),SameLevel(P1,P2),Assembly(P2,S2,Q2)直观上看，我们必须计算所有SameLevel元组，它们的首字段值在从spoke到根的最短路径上。每个这样元组对本例查询结果都有潜在的贡献。但另一方面，如果计算所有的SameLevel表元组，则显然会很浪费。为了既不浪费，又不遗漏潜在有用的中间元组，我们定义一个称为Magic_SameLevel的新表，在该表的每个元组中存储一个对计算给定查询有用值本例：存储从spoke到根的最短路径上Samelevel:S1值。,2023/7/19,31,14.4.2 魔集算法,处理查询：在“配件层次树中检索三轮车同层次配件”SameLevel(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)SameLevel(S1,S2):-Magic_SameLevel(S1),Assembly(P1,S1,Q1),SameLevel(P1,P2),Assembly(P2,S2,Q2)这个修改后的程序常被称为魔集(magic sets)程序。,2023/7/19,32,14.4.2 魔集算法,从一般Datalog程序获得魔集程序的改写算法描述算法的输入与输出算法输入：包括程序本身和一个查询形式。可由查询形式，获得要查询的关系，以及一个具体的查询字段限制值（查询常数）。当重写程序被赋值时，查询常数被用来限制计算范围。算法输出：是一个重写的魔集程序。在原始程序中增加魔集过滤器修改程序的每条规则在规则体中增加魔集过滤条件，以过滤该规则产生的元组集。定义魔集关系为定义作为过滤器的魔集关系，为此，必须创建一个新规则。直观上看，通过分析输出关系R在程序规则体的每次出现，有助于我们确定魔集关系。,