Database System Concepts, 6th Ed.Silberschatz, Korth and SudarshanSee www.db-book.com for conditions on re-use 拭延睹第壶傈擦漏癣鱼隙资弱酣泻径星瞳漓疗爆持倡朽气傻夺帐韭蘸厂淆数据库系统概念教学课件appc数据库系统概念教学课件appcAppendix C: Other Relational Languages 茶樟神碳憾异锅史漫尼烦枉奖绒右葡肘渭仇拓旱蹬路节尾屠眯瞅阿巴攻垮数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.2Database System Concepts - 6th EditionAppendix C: Other Relational LanguagesnQuery-by-Example (QBE)nAccessnDatalog镀孟遏劳输翼择宇窍摹涌酉拌圣滨头榆帽操斌粕犊矾巾几男燃金摹们姑黎数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.3Database System Concepts - 6th EditionQuery-by-Example (QBE)nBasic StructurenQueries on One RelationnQueries on Several RelationsnThe Condition BoxnThe Result RelationnOrdering the Display of TuplesnAggregate Operations nModification of the Database棕蘸句锡螺滤吨简溜挽径荣晦圣篡刹扒街甫沦迷饼阳锁腾智邵跨袄走蹭茵数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.4Database System Concepts - 6th EditionQBE Basic StructurenA graphical query language which is based (roughly) on the domain relational calculusnTwo dimensional syntax system creates templates of relations that are requested by usersnQueries are expressed “by example”肮伶瑰赡粳筋奋吻宙窖啥拍必契宠畦瞬自六厅仲毖徽泼钦途玖搁苔梯剁悔数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.5Database System Concepts - 6th EditionQBE Skeleton Tables for the Bank ExampleQBE Skeleton Tables for the Bank Example剖颅叉枪美客窟牵两湃程笺乃暮标蚕坚闰棉持翘抡摘嘱辫玲垒博佃荣咕光数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.6Database System Concepts - 6th EditionQBE Skeleton Tables (Cont.)浦耽时郑蹦钮筏程贝佳胺苛壮夷恭械蝗斟涝唐卿箕携漆追鳃陵抢缝笔钾销数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.7Database System Concepts - 6th EditionQueries on One RelationnFind all loan numbers at the Perryridge branch.l _x is a variable (optional; can be omitted in above query)l P. means print (display)l duplicates are removed by defaultl To retain duplicates use P.ALL P._x瓶侮陈参闽战张蓬刹例埋涎奄袍墓楚岳镣离勤翻卵一筷捍协讽免欧障猩侄数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.8Database System Concepts - 6th EditionQueries on One Relation (Cont.)nDisplay full details of all loansP._xP._yP._zlMethod 1:lMethod 2: Shorthand notation续口支琉顷峡亢视歌揪蔓蝎焰瞻血需抖锁噪巡消徘北己乔互厕像岛蔚倒滋数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.9Database System Concepts - 6th EditionQueries on One Relation (Cont.)nFind names of all branches that are not located in Brooklynn Find the loan number of all loans with a loan amount of more than $700戚斜沿囱料诚校鹃漏揖典烬眶扎初舞焉然殃迹宪分叙纯微魄靛金伙晰睡烈数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.10Database System Concepts - 6th EditionQueries on One Relation (Cont.)nFind the loan numbers of all loans made jointly to Smith and Jones.nFind all customers who live in the same city as Jones.注栋棋扇瞻盼疗尺拎鞘戌搜吗羡摆惭芝愧爱笋悟傣醇铃藩咸苏硕捷体闸靠数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.11Database System Concepts - 6th EditionQueries on Several RelationsnFind the names of all customers who have a loan from the Perryridge branch.储呐爪始租戍申堪困流奄亚境嗣聋澡秒溪违苇廖铭渔怯河捡俏眯藩瓣炯尧数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.12Database System Concepts - 6th EditionQueries on Several Relations (Cont.)nFind the names of all customers who have both an account and a loan at the bank.婿吗缀棵技铝呆内犬歹搔二技锗包伟忍迭绘泣碟偶爱炕乔范符剧吞赔句嚼数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.13Database System Concepts - 6th EditionNegation in QBEnFind the names of all customers who have an account at the bank, but do not have a loan from the bank. means “there does not exist”慕瓦卧今钱吾尿庄暂弛嫌综撑诡否热却毋冷牛部嗓羔跪门箱慑琵绩泼佳舒数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.14Database System Concepts - 6th EditionNegation in QBE (Cont.)nFind all customers who have at least two accounts. means “not equal to”爬辰郴统处磐赠燎睹届初象孰坷当陶属捏萨纬勺日阀材砂跟恶受糯删忧冰数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.15Database System Concepts - 6th EditionThe Condition BoxnAllows the expression of constraints on domain variables that are either inconvenient or impossible to express within the skeleton tables.nComplex conditions can be used in condition boxesnExample: Find the loan numbers of all loans made to Smith, to Jones, or to both jointly烬孝琳卸钱缎欢素獭她珠侩贵狡惶欢胚赋亥炸军荆睡骄摩酋抬肿牵险盖窄数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.16Database System Concepts - 6th EditionCondition Box (Cont.)nQBE supports an interesting syntax for expressing alternative values.屠赡困锗晤畔年对呜阀搅涩宠住懊桔高盐峰葬臭删凤窖识珐致放桃贿厨是数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.17Database System Concepts - 6th EditionCondition Box (Cont.)nFind all account numbers with a balance greater than $1,300 and less than $1,500. nFind all account numbers with a balance greater than $1,300 and less than $2,000 but not exactly $1,500.迈火粥饯诵兹叹展镣诫饭蜀率相练券付鸭盼讫迎捞剧逝娶观求傅股垦脏鞘数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.18Database System Concepts - 6th EditionCondition Box (Cont.)nFind all branches that have assets greater than those of at least one branch located in Brooklyn.宇瓜密铁月驭掖娩纹采褒评佰搏触吵披朴谋渣己谭职兢辙托劝流呼民琴荫数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.19Database System Concepts - 6th EditionThe Result RelationnFind the customer_name, account_number, and balance for all customers who have an account at the Perryridge branch.lWe need to:4Join depositor and account.4Project customer_name, account_number and balance.lTo accomplish this we:4Create a skeleton table, called result, with attributes customer_name, account_number, and balance.4Write the query.样周跋竭槽绳缆川牛佣移奶溯榷号寅倍锋枫虎跳血笼斗糟俺匿核列漳荧窟数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.20Database System Concepts - 6th EditionThe Result Relation (Cont.)nThe resulting query is: 梧直访宇万涅魄便旅颊巨辆皱坚西第疟借剥舱胁罗缚樱露砸橡猾罐匪泊岔数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.21Database System Concepts - 6th EditionOrdering the Display of TuplesnAO = ascending order; DO = descending order.nExample: list in ascending alphabetical order all customers who have an account at the bank.nWhen sorting on multiple attributes, the sorting order is specified by including with each sort operator (AO or DO) an integer surrounded by parentheses.nExample: List all account numbers at the Perryridge branch in ascending alphabetic order with their respective account balances in descending order.王琅澈颂艰筒烽崔鸦冈百嗅业拿匈泌缔跃韵沾攀袱传酝旁汝淄檄冲鸟卫抒数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.22Database System Concepts - 6th EditionAggregate OperationsnThe aggregate operators are AVG, MAX, MIN, SUM, and CNTnThe above operators must be postfixed with “ALL” (e.g., SUM.ALL. or AVG.ALL._x) to ensure that duplicates are not eliminated.nExample: Find the total balance of all the accounts maintained at the Perryridge branch.涵痹译土健白块氰激泄奏溶谊贡砖脸涡宵猜如瞎笼么徒佃佩那淘那栓浦痉数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.23Database System Concepts - 6th EditionAggregate Operations (Cont.)nUNQ is used to specify that we want to eliminate duplicates. nFind the total number of customers having an account at the bank.祁恤鬃塌捆洛很递兵倍配寺戏罗视范源肋礼加藏继铸惑亥避女损邓磋担惑数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.24Database System Concepts - 6th EditionQuery ExamplesnFind the average balance at each branch.nThe “G” in “P.G” is analogous to SQLs group by construct. nThe “ALL” in the “P.AVG.ALL” entry in the balance column ensures that all balances are considered.nTo find the average account balance at only those branches where the average account balance is more than $1,200, we simply add the condition box:叶薛肝贡认碟赖漓重寇谜髓闹您握骏既清兜赎畜挨租柳奔险赊烤脓泡旨捆数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.25Database System Concepts - 6th EditionQuery ExamplenFind all customers who have an account at all branches located in Brooklyn. lApproach: for each customer, find the number of branches in Brooklyn at which they have accounts, and compare with total number of branches in Brooklyn.lQBE does not provide subquery functionality, so both above tasks have to be combined in a single query. 4Can be done for this query, but there are queries that require subqueries and cannot always be expressed in QBE.nIn the query on the next pagelCNT.UNQ.ALL._w specifies the number of distinct branches in Brooklyn. Note: The variable _w is not connected to other variables in the query.lCNT.UNQ.ALL._z specifies the number of distinct branches in Brooklyn at which customer x has an account.椽升揉淑在掩胚侮地蕴物擂被珐剩行蔓蒸呈济丧嗓殃向婚媚葵还塔掷弥臭数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.26Database System Concepts - 6th EditionQuery Example (Cont.)暇吨汪蒜挥袖改迅睦硝攀迪蔬藩命莹宙剐却登踌仇地部躲询尾玖愤鸳特妇数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.27Database System Concepts - 6th EditionModification of the Database DeletionnDeletion of tuples from a relation is expressed by use of a D. command. In the case where we delete information in only some of the columns, null values, specified by , are inserted.nDelete customer SmithnDelete the branch_city value of the branch whose name is “Perryridge”.舒吞悼杉放绣交鲸锐贞靛缄眶贱姬宋顷非奄凤灿峙拒蚌碱吗噬辐聋撤搬赚数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.28Database System Concepts - 6th EditionDeletion Query ExamplesnDelete all loans with a loan amount greater than $1300 and less than $1500.lFor consistency, we have to delete information from loan and borrower tables死抵殆埂湿特西梨忧晌锐询歉罪柠雅祁耍蒙心翘氛拓缎帕劫残棚凝竹致勉数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.29Database System Concepts - 6th EditionDeletion Query Examples (Cont.)nDelete all accounts at branches located in Brooklyn.壕冰钙顾枪赢屎馈惩奖榷渐或男满蓝治磺频画初半绕斗汽衔熬长坐事隅宗数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.30Database System Concepts - 6th EditionModification of the Database InsertionnInsertion is done by placing the I. operator in the query expression. nInsert the fact that account A-9732 at the Perryridge branch has a balance of $700.艳恫住埋反炽乖刘嘶障而高抗林气毫月蛀过赫镊混鼓猩盆寿邢闽列箱囚还数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.31Database System Concepts - 6th EditionModification of the Database Insertion (Cont.)nProvide as a gift for all loan customers of the Perryridge branch, a new $200 savings account for every loan account they have, with the loan number serving as the account number for the new savings account. 宙畜峭抒芭追扇痢漫绊恨徘鹰腻酚鬃丧蚁器学锄侨亩虎搽鹤彝谆菲霸柱盼数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.32Database System Concepts - 6th EditionModification of the Database UpdatesnUse the U. operator to change a value in a tuple without changing all values in the tuple. QBE does not allow users to update the primary key fields.nUpdate the asset value of the Perryridge branch to $10,000,000. nIncrease all balances by 5 percent.滥蓉迄劣耳炭超赞涡势浩童舱槐越串扩碍柔颅惧流芜辅寐嗡滑浮商泞晒瑞数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.33Database System Concepts - 6th EditionMicrosoft Access QBEnMicrosoft Access supports a variant of QBE called Graphical Query By Example (GQBE).nGQBE differs from QBE in the following wayslAttributes of relations are listed vertically, one below the other, instead of horizontally.lInstead of using variables, lines (links) between attributes are used to specify that their values should be the same.4Links are added automatically on the basis of attribute name, and the user can then add or delete links.4By default, a link specifies an inner join, but can be modified to specify outer joins.lConditions, values to be printed, as well as group by attributes are all specified together in a box called the design grid.轰聂声坟锚存豪攫孩妒甲悄泡卉衰裤礼指释俊炉靶贬慎能钦燎裴淡峻收邮数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.34Database System Concepts - 6th EditionAn Example Query in Microsoft Access QBEnExample query: Find the customer_name, account_number and balance for all accounts at the Perryridge branch.呼垛蹭烹耕掩足锨秘购脚赤尚湾蔽交归互止芽篙率兴茨壮摧雏倔形舱阻五数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.35Database System Concepts - 6th EditionAn Aggregation Query in Access QBEnFind the name, street and city of all customers who have more than one account at the bank.稍康骆露亡便赞冶缆惋库泛廊雇坊角隅泄掺崭腕颖赞织若钝馋进精希谬碧数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.36Database System Concepts - 6th EditionAggregation in Access QBEnThe row labeled Total specifies: lwhich attributes are group by attributes.lwhich attributes are to be aggregated upon (and the aggregate function). lFor attributes that are neither group by nor aggregated, we can still specify conditions by selecting where in the Total row and listing the conditions below.nAs in SQL, if group by is used, only group by attributes and aggregate results can be output.糖既粳逢砂庄屁今懊揣令虎技狄雌仅褐宪镜破另展僚触舷谆令罪稻揣纵识数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.37Database System Concepts - 6th EditionDatalognBasic Structure nSyntax of Datalog RulesnSemantics of Nonrecursive DatalognSafety nRelational Operations in DatalognRecursion in DatalognThe Power of Recursion炎育撮暴惨庇诸颗降酥胚壹尧漠妒茅醋潮畏咒坚块翅膘伯松钎及唾穿忽遮数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.38Database System Concepts - 6th EditionBasic StructurenProlog-like logic-based language that allows recursive queries; based on first-order logic.nA Datalog program consists of a set of rules that define views. nExample: define a view relation v1 containing account numbers and balances for accounts at the Perryridge branch with a balance of over $700.v1 (A, B ) : account (A, “Perryridge”, B ), B 700.nRetrieve the balance of account number “A-217” in the view relation v1.? v1 (“A-217”, B ).nTo find account number and balance of all accounts in v1 that have a balance greater than 800 ? v1 (A,B ), B 800柄琅投泉国吼酣覆邹并违魔瑚帘大缕侮铜很筹淖粉咸愚盔醋痒妖谅淀鲜琢数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.39Database System Concepts - 6th EditionExample QueriesnEach rule defines a set of tuples that a view relation must contain.lE.g., v1 (A, B ) : account (A, “ Perryridge”, B ), B 700 is read as: for all A, B if (A, “Perryridge”, B ) account and B 700 then (A, B ) v1nThe set of tuples in a view relation is then defined as the union of all the sets of tuples defined by the rules for the view relation.nExample:interest_rate (A, 5) : account (A, N, B ) , B = 10000鸟澄鲸粤确帽音混半喜误骑真迢暮波软带咳唤伴仲吝从晨淆熟熔桓炮竣崖数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.40Database System Concepts - 6th EditionNegation in DatalognDefine a view relation c that contains the names of all customers who have a deposit but no loan at the bank:c(N) : depositor (N, A), not is_borrower (N).is_borrower (N) :borrower (N,L).nNOTE: using not borrower (N, L) in the first rule results in a different meaning, namely there is some loan L for which N is not a borrower. lTo prevent such confusion, we require all variables in negated “predicate” to also be present in non-negated predicates.俭貌贫隶嫁瘸奇勾漳谨切歇俞廷唐抑疟澜屿葡悟羌淋蛤傅琉寸挽才剪萌进数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.41Database System Concepts - 6th EditionNamed Attribute NotationnDatalog rules use a positional notation that is convenient for relations with a small number of attributes.nIt is easy to extend Datalog to support named attributes. lE.g., v1 can be defined using named attributes as v1 (account_number A, balance B ) : account (account_number A, branch_name “ Perryridge”, balance B ), B 700.楔誉汇藐袖绍英趋定哇捆律器氓次犁点谅矛唯按娩访撰滩增榨需忍烂甘示数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.42Database System Concepts - 6th EditionFormal Syntax and Semantics of DatalognWe formally define the syntax and semantics (meaning) of Datalog programs, in the following steps:1.We define the syntax of predicates, and then the syntax of rules.2.We define the semantics of individual rules.3.We define the semantics of non-recursive programs, based on a layering of rules.4.It is possible to write rules that can generate an infinite number of tuples in the view relation. To prevent this, we define what rules are “safe”. Non-recursive programs containing only safe rules can only generate a finite number of answers.5.It is possible to write recursive programs whose meaning is unclear. We define what recursive programs are acceptable, and define their meaning.膝逝进江酗朵匝使皿舷郑码邻瓜眠袄呸哪猪偶咏昂洽诱胎磊瑞骤球咒孙莎数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.43Database System Concepts - 6th EditionSyntax of Datalog RulesnA positive literal has the formp (t1, t2 ., tn )lp is the name of a relation with n attributesleach ti is either a constant or variablenA negative literal has the form not p (t1, t2 ., tn )nComparison operations are treated as positive predicates lE.g., X Y is treated as a predicate (X,Y )l“” is conceptually an (infinite) relation that contains all pairs of values such that the first value is greater than the second valuenArithmetic operations are also treated as predicateslE.g., A = B + C is treated as +(B, C, A), where the relation “+” contains all triples such that the third value is thesum of the first two非铅瘟蕾梦二渣篮劝巡莽漓赶涩裔政遮愧厂五圆帽融叹押状忿营族鸦私晚数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.44Database System Concepts - 6th EditionSyntax of Datalog Rules (Cont.)nRules are built out of literals and have the form:p (t1, t2, ., tn ) : L1, L2, ., Lm. head bodyleach Li is a literallhead the literal p (t1, t2, ., tn ) lbody the rest of the literalsnA fact is a rule with an empty body, written in the form:p (v1, v2, ., vn ).lindicates tuple (v1, v2, ., vn ) is in relation pnA Datalog program is a set of rules.票簿婆氛开患歉坟侠毁虽谢途本赶辟锣仁婆嗡呈楔矩逆歉寐碍达鹃欠抉锦数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.45Database System Concepts - 6th EditionSemantics of a RulenA ground instantiation of a rule (or simply instantiation) is the result of replacing each variable in the rule by some constant.lE.g., Rule defining v1 v1(A,B) : account (A,“Perryridge”, B ), B 700.lAn instantiation above rule: v1 (“A-217”, 750) :account ( “A-217”, “Perryridge”, 750),750 700.nThe body of rule instantiation R is satisfied in a set of facts (database instance) l if1. For each positive literal qi (vi,1, ., vi,ni ) in the body of R, l contains the fact qi (vi,1, ., vi,ni ).2. For each negative literal not qj (vj,1, ., vj,nj ) in the body of R, l does not contain the fact qj (vj,1, ., vj,nj ).侧氧慑逼穷墓渔援霞厅班强崎畴醒撤戴扳污瞅釜尾神哲沂璃得耘承津矢千数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.46Database System Concepts - 6th EditionSemantics of a Rule (Cont.)nWe define the set of facts that can be inferred from a given set of facts l using rule R as:infer(R, l) = p (t1, ., tn) | there is a ground instantiation R of R where p (t1, ., tn ) is the head of R, and the body of R is satisfied in l nGiven an set of rules = R1, R2, ., Rn, we defineinfer( , l) = infer (R1, l ) infer (R2, l ) . infer (Rn, l )秃饵偷堪否熙云虽咽漳并虫佰雀环耕拟撩它暂被一叁冕雄贝即颁肚知黔欲数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.47Database System Concepts - 6th EditionLayering of RulesnDefine the interest on each account in Perryridgeinterest(A, l) : perryridge_account (A,B), interest_rate(A,R), l = B * R/100.perryridge_account(A,B) : account (A, “Perryridge”, B).interest_rate (A,5) : account (N, A, B), B = 10000.nLayering of the view relations呻看掷榜偶缄奠耽跌拎羹山隋坊办宾况伸裙屯缺剩佣敲葫诌舜无订哦垫焰数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.48Database System Concepts - 6th EditionLayering Rules (Cont.)nA relation is a layer 1 if all relations used in the bodies of rules defining it are stored in the database.nA relation is a layer 2 if all relations used in the bodies of rules defining it are either stored in the database, or are in layer 1.nA relation p is in layer i + 1 if lit is not in layers 1, 2, ., ilall relations used in the bodies of rules defining a p are either stored in the database, or are in layers 1, 2, ., iFormally:呵糠独荔伏玻桔捞殿皑衙覆洱恃托简进瓮牙幅抹落靛揭师晨烷芋烦巢术碘数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.49Database System Concepts - 6th EditionSemantics of a ProgramnDefine I0 = set of facts stored in the database.nRecursively define li+1 = li infer ( i+1, li )nThe set of facts in the view relations defined by the program (also called the semantics of the program) is given by the set of facts ln corresponding to the highest layer n.Let the layers in a given program be 1, 2, ., n. Let i denote theset of all rules defining view relations in layer i.Note: Can instead define semantics using view expansion likein relational algebra, but above definition is better for handlingextensions such as recursion.纱似淫伸骚崎孕比虱燕馈嫡濒卉孩很臻缠兵隋梁宿脯邹哆挠碧惠箔钧漱期数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.50Database System Concepts - 6th EditionSafetynIt is possible to write rules that generate an infinite number of answers.gt(X, Y) : X Ynot_in_loan (B, L) : not loan (B, L)To avoid this possibility Datalog rules must satisfy the following conditions.lEvery variable that appears in the head of the rule also appears in a non-arithmetic positive literal in the body of the rule.4This condition can be weakened in special cases based on the semantics of arithmetic predicates, for example to permit the rulep (A ) :- q (B ), A = B + 1lEvery variable appearing in a negative literal in the body of the rule also appears in some positive literal in the body of the rule.削熏莲垮卢巩嘉谨载秘缅峭萌阴沏彩台壹获氦弘厨腑阶鲜波柠揣矫散瓜舵数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.51Database System Concepts - 6th EditionRelational Operations in DatalognProject out attribute account_name from account.query (A) :account (A, N, B ).nCartesian product of relations r1 and r2.query (X1, X2, ., Xn, Y1, Y1, Y2, ., Ym ) :r1 (X1, X2, ., Xn ), r2 (Y1, Y2, ., Ym ).nUnion of relations r1 and r2. query (X1, X2, ., Xn ) :r1 (X1, X2, ., Xn ), query (X1, X2, ., Xn ) :r2 (X1, X2, ., Xn ), nSet difference of r1 and r2.query (X1, X2, ., Xn ) :r1(X1, X2, ., Xn ), not r2 (X1, X2, ., Xn ), 察炼圈丧绞尖赊好臣喘升砧朱征父祥闪胰太皱小艇汕菱垂怔竣敞疫喉淬穴数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.52Database System Concepts - 6th EditionRecursion in DatalognSuppose we are given a relation manager (X, Y )containing pairs of names X, Y such that Y is a manager of X (or equivalently, X is a direct employee of Y).nEach manager may have direct employees, as well as indirect employees.lIndirect employees of a manager, say Jones, are employees of people who are direct employees of Jones, or recursively, employees of people who are indirect employees of Jones.nSuppose we wish to find all (direct and indirect) employees of manager Jones. We can write a recursive Datalog program. empl_jones (X ) :- manager (X, Jones ). empl_jones (X ) :- manager (X, Y ), empl_jones (Y ).扬饭凹贿叫绒安溉锑纤号提绥溪翌铅黍羚衍迫五猾咕颓视注辈邮葱聘牟行数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.53Database System Concepts - 6th EditionSemantics of Recursion in DatalognAssumption (for now): program contains no negative literalsnThe view relations of a recursive program containing a set of rules are defined to contain exactly the set of facts l computed by the iterative procedure Datalog-Fixpointprocedure Datalog-Fixpointl = set of facts in the databaserepeatOld_l = ll = l infer ( , l )until l = Old_lnAt the end of the procedure, infer ( , l ) llInfer ( , l ) = l if we consider the database to be a set of facts that are part of the programnl is called a fixed point of the program.蔚轮粒父接韭改针找茂嚏妇榆睁出做阉和坠茄某穆们齐母查蝶垄爱孰臣渡数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.54Database System Concepts - 6th EditionExample of Datalog-FixPoint Iteration栽篆吞签疵艘促聊澳量兄拔帧删步宰躁羔假食睁余寐叫膊弓臀肆判跺泻邦数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.55Database System Concepts - 6th EditionA More General ViewnCreate a view relation empl that contains every tuple (X, Y ) such that X is directly or indirectly managed by Y.empl (X, Y ) : manager (X, Y ).empl (X, Y ) : manager (X, Z ), empl (Z, Y ) nFind the direct and indirect employees of Jones.? empl (X, “Jones”).nCan define the view empl in another way too:empl (X, Y ) : manager (X, Y ).empl (X, Y ) : empl (X, Z ), manager (Z, Y ). 稍布巷庶寄驾柜凑靖宣拣扣弘扭耶泉愤俩经院躯散怂癣陪硫域坞妒炳卉幢数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.56Database System Concepts - 6th EditionThe Power of RecursionnRecursive views make it possible to write queries, such as transitive closure queries, that cannot be written without recursion or iteration.lIntuition: Without recursion, a non-recursive non-iterative program can perform only a fixed number of joins of manager with itself.4This can give only a fixed number of levels of managers.4Given a program we can construct a database with a greater number of levels of managers on which the program will not work.魄拈此羞拯市格盐伯匡业阳锥埋褥来暴烯屿师僚寻见席疾铁涌橇芹萧柞箔数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.57Database System Concepts - 6th EditionRecursion in SQLnStarting with SQL:1999, SQL permits recursive view definitionnE.g., query to find all employee-manager pairs with recursive empl (emp, mgr ) as ( select emp, mgr from manager union select manager.emp, empl.mgr from manager, empl where manager.mgr = empl.emp ) select * from empl义百蹿疫谤未搅娇幅俭余设家簇现梭余擅艇出唐栓局绝婿竭炸硬彻回霉铀数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.58Database System Concepts - 6th EditionMonotonicity nA view V is said to be monotonic if given any two sets of facts I1 and I2 such that l1 I2, then Ev (I1) Ev (I2 ), where Ev is the expression used to define V.nA set of rules R is said to be monotonic if l1 I2 implies infer (R, I1 ) infer (R, I2 ), nRelational algebra views defined using only the operations: , |X| and (as well as operations like natural join defined in terms of these operations) are monotonic. nRelational algebra views defined using set difference () may not be monotonic.nSimilarly, Datalog programs without negation are monotonic, but Datalog programs with negation may not be monotonic.芦瓤黎财谭况士鬃尸呼查咽绸淀六窟缨改巍唇答料抽蚀恼测碍吾喊褂确骤数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.59Database System Concepts - 6th EditionNon-MonotonicitynProcedure Datalog-Fixpoint is sound provided the rules in the program are monotonic.lOtherwise, it may make some inferences in an iteration that cannot be made in a later iteration. E.g., given the rules a :- not b. b :- c. c. Then a can be inferred initially, before b is inferred, but not later.nWe can extend the procedure to handle negation so long as the program is “stratified”: intuitively, so long as negation is not mixed with recursion租珠亡孟柱拧概悠鸿瘸川窒佰沛宣捣倚票寥消橱驹碌罢忍傍茂个贤潍炬漱数据库系统概念教学课件appc数据库系统概念教学课件appcSilberschatz, Korth and Sudarshanc.60Database System Concepts - 6th EditionNon-Monotonicity (Cont.)nThere are useful queries that cannot be expressed by a stratified programlExample: given information about the number of each subpart in each part, in a part-subpart hierarchy, find the total number of subparts of each part.lA program to compute the above query would have to mix aggregation with recursionlHowever, so long as the underlying data (part-subpart) has no cycles, it is possible to write a program that mixes aggregation with recursion, yet has a clear meaninglThere are ways to evaluate some such classes of non-stratified programs辖碘唁逐洲床唐瓣赛戳执毋惠葵梳锹姑伟尘条茂诸堡放咙钠瓤弊派莱健泛数据库系统概念教学课件appc数据库系统概念教学课件appcDatabase System Concepts, 6th Ed.Silberschatz, Korth and SudarshanSee www.db-book.com for conditions on re-use 拭延睹第壶傈擦漏癣鱼隙资弱酣泻径星瞳漓疗爆持倡朽气傻夺帐韭蘸厂淆数据库系统概念教学课件appc数据库系统概念教学课件appcEnd of Appendix C刽歼厅乾哑肺罢垮繁向福侦纤晃窝朗亩盐横革降言云芬抑揽芒傅盅夜拴究数据库系统概念教学课件appc数据库系统概念教学课件appc