上海交通大学 数据库原理 陆朝俊 课件08xRADatalog概要1.pptVIP

Multiple Operations in Datalog Create IDB predicates for intermediate relations Example A(x,y,z) ? R(x,y,z) AND x 10 B(x,y,z) ? R(x,y,z) AND y = ‘ok’ C(x,y,z) ? A(x,y,z) AND B(x,y,z) D(x,z) ? C(x,y,z) * Lu Chaojun, SJTU Expressive Power of Datalog Non-recursive Datalog = RA Datalog simulates SQL SELECT-FROM-WHERE without aggregation and grouping Recursive Datalog is more powerful than RA and SQL None is full in expressive power (Turing completeness) * Lu Chaojun, SJTU End * Lu Chaojun, SJTU Lu Chaojun, SJTU Lu Chaojun, SJTU * Extended Relational Algebra Bag Semantics A relation (in SQL, at least) is really a bag (or multiset). It may contain the same tuple more than once There is no specified order (unlike a list). Select, project, and join work for bags as well as sets. Just work on a tuple-by-tuple basis, and dont eliminate duplicates. Lu Chaojun, SJTU * Why Bags? Efficient implementation e.g. projection, union Q: How to eliminate duplicates? Some queries use bags e.g. Aggregate Find the average grades Lu Chaojun, SJTU * Bag Union R ? S: Sum the times an element appears in the two bags, i.e. if t appears n/m times in R/S, then t appears n+m times in R ? S. Example {1,2,1}?{1,2,3} = {1,1,1,2,2,3}. * Lu Chaojun, SJTU Bag Intersection R ? S: Take the minimum of the number of occurrences in each bag, i.e. t appears min(n,m) times in R ? S. Example {1,2,1} ? {1,2,3,3} = {1,2}. * Lu Chaojun, SJTU Bag Difference R ? S: Proper-subtract the number of occurrences in the two bags, i.e. t appears max(0, n ? m) times in R ? S. Example {1,2,1} ? {1,2,3,3} = {1}. * Lu Chaojun, SJTU Other Operators on Bags Projection, selection, product, join No duplicate elimination * Lu Chaojun, SJTU Extensions to Relational Model Not a part of the formal relational model, but appear in real query languages like SQL. Modification: insert, delete, update. Aggregation: count, sum, average Views Null values * Lu Chaojun, SJTU Extended RA Duplicate-elimination operator Sorting oper