数据库概论 第七章递归查询

数据库概论第7章递归查询提纲层次结构递归查询简介层次结构的关系表示方式递归查询在SQL中的实现HierachyidProlog与Datalog层次结构数据结构树：职工之间的领导联系有向图：零件之间的构成联系无向图：交通网络操作需求返回指定节点的所有子(父)节点，显示格式改变隶属关系环路检测生成传递闭包最短路径层次结构的例子trikewheelframespoketireseatpedalrimtubeAssemblypartsubpartqtytrikewheel3trikeframe1frameseat1framepedal1wheelspoke2wheeltire1tirerim1tiretube1组成trike的零件有哪些？R.part,S.subpart(Assemble)R.part,S.subpart(R.subpart=S.part(R(Assemble)S(Assemble))AssemblypartsubparttrikewheeltrikeframeframeseatframepedalwheelspokewheeltiretirerimtiretubeAssemblypartsubparttrikeseattrikepedaltrikespoketriketirewheelrimwheeltubeR.part,T.subpart(R.subpart=S.partS.subpart=T.part(R(Assemble)S(Assemble)T(Assemble))Assemblypartsubparttrikerimtriketube对于树、图等数据结构，其关系存储有以下三种方式：邻接表 adjacent(child,parent)物化路径 materialize_path(node,path)嵌套集合 nested_net(node,left_value,right_value)层次结构的关系表示方式ABDECF层次结构的关系表示方式：邻接表Adjacent(child,parent)childparentBACADBEBFC层次结构的关系表示方式：物化路径materialize_path(node,path)nodepathA.AB.A.BC.A.CD.A.B.DE.A.B.EF.A.C.FABDECF层次结构的关系表示方式：嵌套集合A(1-12)B(2-7)D(3-4)E(5-6)C(8-11)F(9-10)nested_net(node,left_value,right_value):nodeLeft_valueRight_valueA112B27C811D34E56F910递归查询：OracleConnectBySelect part,subpartFrom ComponentsStartwith part=‘trike’Connectby priorsubart=part(上一条的subpart是本条的part)递归查询：SQLServerWITHRecursiveCTEAS(SELECTFROMBaseTableUNIONALLSELECTFROMRecursiveCTE)SELECT*FROMRecursiveCTE;定位点成员AnchorMember递归成员RecursiveMember递归查询：SQLServerwithComponents(part,subpart)as

(select part,subpart from Assembly) unionall

(select A.part,C.subpart from AssemblyA,ComponentsC where A.subpart=C.part)select*fromComponentswherepart=‘trike’declare@rootasINT;set@root=3;withSubsCTEas(select empid,ename,0aslvlfrom empwhere empid=@rootunionallselect C.empid,C.ename,P.lvl+1from SubsCTEasPjoinempASConC.mgrid=P.empid)select*fromSubsCTE;emp(empid,ename,mgrid)createfunctiondbo.fn_subordinates(@rootasint)returns@SubsTable( empid intnotnullprimarykey, level intnotnull)asbegin declare @lvlasint; set @lvl=0;--Initializelevelcounterwith0 insertinto@Subs(empid,level)--Insertrootnodeto@Subs select empid,@lvl from emp where empid=@root;while@@rowcount>0--whilepreviouslevelhadrowsbegin set@lvl=@lvl+1;--Incrementlevelcounter --Insertnextlevelofsubordinatesto@Subs insertinto@Subs(empid,level) select C.empid,@lvl from @SubsASP--P=Parent joinempASC --C=Child onP.lvl=@lvl-1--Filterparentsfrompreviouslevel and C.mgrid=P.empid;endreturn;endHierachyidhierarchyid表示层次结构中的位置，由应用程序来生成和分配hierarchyid值，使行与行之间的所需关系反映在这些值中createtableemp( NodeIDhierarchyidprimarykeyclustered, NodeLevelasNodeID.GetLevel(), enoint, enamechar(20), titlechar(20))Hierarchyiddeclare@roothierarchyid,@child1hierarchyid, @child2hierarchyid,@grandchild1hierarchyidinsertintoemp(NodeID,eno,ename,title)values(hierarchyid::GetRoot(),1,‘tom’,‘CEO’)set@root=hierarchyid::GetRoot()set@child1=@root.GetDescendant(null,null)insertintoemp(NodeID,eno,ename,title)values(@child1,2,‘bob’,‘VP’)Hierarchyidset@child2=@root.GetDescendant(@child1,null)insertintoemp(NodeID,eno,ename,title)values(@child2,3,‘Arm’,‘MS’)set@grandchild1=@child1.GetDescendant(null,null)insertintoemp(NodeID,eno,ename,title)values(@grandchild1,4,‘jerry’,‘PM’)Hierarchyid selectNodeID.ToString()asNodePath,*fromemp

selectNodeID.GetAncestor(2)asGrandPa,enamefromempwhereeno=4Hierarchyid其他方法IsDescendantOf(parentHierarchyid)如果当前节点的祖先是parentHierarchyid，则返回1GetReparentedValue(OldParent,NewParent)将节点从层次结构中的旧位置移到新位置层次结构索引深度优先：基于hierarchyid创建索引广度优先：基于GetLevel()列创建索引Prolog程序不是一系列动作，而是一组事实与规则的集合是说明性语言，而非过程性语言基于逻辑谓词事实：对象间的一种关系，或对象的属性规则：从一事实推出另一事实自然语言AfastcarisfunBilllikesacarifthecarisfun逻辑谓词fun(fast-car)likes(bill,car)iffun(car)Prolog程序规则likes(cindy,

Something)

iflikes(bill,Something)

事实likes(bill,cindy)likes(cindy,bill)likes(bill,dog)查询用户：likes(bill,cindy)系统：yes用户：likes(bill,What)系统：What=dog

What=cindy查询用户：likes(cindy,What)系统：What=bill

What=dog

What=cindyDatalog基本结构Datalog由一组规则构成Datalog规则用来定义视图Datalog规则使用位置来识别关系的属性名PROF(P#,PNAME,SAL,AGE,D#)给出退休了的老师的姓名和年龄v1(A,B):–PROF(O,A,P,B,Q),B>60？v1(A,B)，B>80v1中所有年龄大于80的老师？v1(“王明”,B)v1中王明老师的年龄Datalog基本结构视图可以由多条规则来定义，视图中元组集合为所有规则所定义的元组集合的并tax-rate(A,0):–PROF(A,B,C,D,E),C<800tax-rate(A,5):–PROF(A,B,C,D,E),C>=800工资超过800的老师缴纳5%所得税，低于800的免缴v2(A):–S(A,B,C,D,E),notv3(A)v3(A):–SC(A,M,N)给出所有没有选课的学生学号Datalog规则可以使用否定Datalog中的递归Components(part,subpart):-Assembly(part,subpart,Qty)Components(part,su