数据库第二章5节

1、lDEFINITION 2.6.1 Compatible TableslTable R and S are compatible if they have the same headings,with attributes chosen from the same domains and with the same meanings.l R SABCa1b1c1a1b2c2a2b2c1ABCa1b2c2a1b3c2a2b2c1EXAMPLElThe Union, Intersection, and Difference Operations Only tables that are compa

2、tible can be involved in Union, Intersection, and differences.并运算差运算交运算DEFINITION 2.6.2lUnion, Intersection, and Difference Let table R and S are compatible, where Head( R) = Head( S) =A1An. The union of R and S is the table R S, with the same heading, consisting of all rows that are in R or in S or

3、 in both. Similarly, the Intersection of R and S is the table R S, consisting of those rows that are in both R and S . l R SlRS RS ?ABCa1b1c1a1b2c2a2b2c1ABCa1b2c2a1b3c2a2b2c1EXAMPLE 2.6.1l R S RSABCa1b1c1a1b2c2a2b2c1ABCa1b2c2a1b3c2a2b2c1ABCa1b1c1a1b2c2a2b2c1a1b3c2The union of R and S is the table R

4、S, with the same heading, consisting of all rows that are in R or in S or in both.l R S RSABCa1b1c1a1b2c2a2b2c1ABCa1b2c2a1b3c2a2b2c1ABCa1b2c2a2b2c1The Intersection of R and S is the table R S, consisting of those rows that are in both R and S . lThe Difference of R and S is the table R - S, consisti

5、ng of all rows that appear in R but do not appear in S. l l R Sl R-S S - R?ABCa1b1c1a1b2c2a2b2c1ABCa1b2c2a1b3c2a2b2c1l R S R - S ABCa1b1c1a1b2c2a2b2c1ABCa1b2c2a1b3c2a2b2c1ABCa1b1c1ABCa1b3c2S - RThe Difference of R and S is the table R - S, consisting of all rows that appear in R but do not appear in

6、 S. Assignment and AliaslDuring evaluation of relational algebra expression, it is sometimes useful to be able to save certain intermediate results. We next introduce a notation meant to add this capability to relational algebra.lDEFINITION 2.6.3 Assignment and Alias Let R be a table and let Head( R

7、) = A1An. Assume that B1,Bn are n attributes such that Domain(Bi)= Domain(Ai) for all i, 1in.We define a new table S, whose heading is Head(S) = B1Bn, by writing the assignment S(B1,Bn):= R(A1,An). The content of the new table S is exactly the same as the content of the old table R. The symbol := us

8、ed in this assignment is called the assignment operation.lAlias S := R We refer to S as an alias of the table R. Note that the table R on the right can result from an evaluation of relational algebra expression, and thus gives us an opportunity to “save” intermediate results of evaluation, much as w

9、e do with assignment statements used in programming language. The table S on the left of the assignment operation must always be a named table, however it cannot be an expression. lEXAMPLE 2.6.3lConsider the tables R and S . Using assignment operation , we can define a new table: T := (RS)-(RS) lWe

10、could also have define the table T by first defining two intermediate tables: T1 := (RS) T2 := (R S) T := T1- T2l2.4 relational operations.set-theoretic operations relational algebranative relational operations.UnionIntersectionDifferenceProductProjectionSelectionJoindivisionlDEFINITION 2.6.4 Produc

11、t The product of the tables R and S is a table T whose heading is Head(T) = R.A1R.An S.B1S.Bm. We say t is a row in T if and only if there are two rows u in R and v in S such that t is the concatenation of u with v, u | v .The product T of R and S is denoted by RS. 笛卡尔积笛卡尔积 RSABCa1b1c1a1b2c2a2b2c1AD

12、Ea1b2c2a1b3c2a2b2c1RST =? RSR.A BCa1b1c1a1b1c1a1b1c1a1b2c2S.ADEa1b2c2a1b3c2a2b2c1a1b2c2a1b2c2a1b2c2a2b2c1a2b2c1a2b2c1a1b3c2a2b2c1a1b2c2a1b3c2a2b2c1ABCa1b1c1a1b2c2a2b2c1ADEa1b2c2a1b3c2a2b2c1RST =l2.4.2 Native relational operations.set-theoretic operations We will use CAP database to illustrate the Na

13、tive relational operations.relational algebranative relational operations.UnionIntersectionDifferenceProductProjectionSelectionJoindivisionThe Projection OperationDEFINITION 4 The projection of R on attributes Ai,., Ak, whereAi,., Ak A1,., An, is a table T whose heading is Head(T) = Ai,., Ak, with t

14、he following content. For every row r in the table R there will be a single row t in the table T such that rAi = tAi for every Ai contained in Ai,., Ak. The projection of R on Ai,., Ak is denoted by R Ai,., Ak or Ai,., Ak(R) .l投影运算投影运算other books uselThe projection operation wipes out the columns of

15、 a table that are not named in the list of attributes.R Ai,., AkEXAMPLE Suppose that we wish to post a list of customer names from the CUSTOMERS table but not include their identification numbers, cities, and discounts. This can be accomplished in relational algebra by writing CN := CUSTOMERS cname

16、or CN := cname (CUSTOMERS) The resulting table CN shown below is a “vertical section of the table CUSTOMERS consisting of the column cname.other books usecidcnamecitydiscntC001TiptopDuluth10.00C002BasicsDallas12.00C003AlliedDallas8.00C004ACMEDuluth8.00C006ACMEKyoto0.00cnameTiptopBasicsAlliedCNCN:= c

17、name (CUSTOMERS)CN := CUSTOMERS cname orACMElThe Selection OperationlThe next operation defined is selection, which creates a new table by selecting from a given table only those rows that satisfy a specified criterion. The general form of the condition that specifies this criterion is the subject o

18、f the following definition.l选择运算选择运算lDEFINITION 5 selection. lGiven a table S with Head(S) = A1. An, the selection operation creates a new table, denoted by S where C or c (S) with the same set of attributes, and consisting of those tuples of S that obey the selection condition.other books uselEXAMP

19、LE In order to find all customers based in kyoto, we need to apply the following selection: CUSTOMERS where city = kyoto or city=kyoto (CUSTOMERS) The result of this query is the tablecidcnamecitydiscntc006ACMEKyoto0.00cidcnamecitydiscntc001TiptopDuluth10.00c002BasicsDallas12.00c003AlliedDallas8.00c

20、004ACMEDuluth8.00c006ACMEKyoto0.00Review：set-theoretic operations relational algebranative relational operations.UnionIntersectionDifferenceProductProjectionSelectionJoindivisionlThe Join OperationlThe purpose of the join operation is to create a table T that relates the rows of two given tables (R

21、and S) that have equal values in identically named columns. denoted byl R join ( ) S 连接运算lEXAMPLElConsider the following table R and S:AB1B2a1b1b1a1b2b1a2b1b2B1 B2 Cb1b1c1b1b1c2b1b2c3b2b2c4AB1B2Ca1b1b1c1a1b1b1c2a2b1b2c3RSjoinT relates the rows of two given tables (R and S) that have equal values in

22、identically named columns.RSTT =lEXAMPLE 2.7.8lNow we wish to pose a query to get names of customers who order at least one product costing $0.50. 用学过的关系代数运算完成上述查询。到哪里查询？涉及到几张表？cidcnamecitydiscntC001TiptopDuluth10.00C002BasicsDallas12.00pidpnamecityquantitypriceP01CombDallas1114000.50P02BrushNewark2

23、030000.50P03RazorDuluth1506001.00ordnomonthcidaidpidQtydollars1011JanC001a01P011000450.001012JanC001a01P011000450.001019FebC001a02P02400180.01017FebC001a06P03600540.0customers和products之间有无联系？靠什么联系？请写出关系代数式。Now we wish to pose a query to get names of customers who order at least one product costing $

24、0.50. lNow we wish to pose a query to get names of customers who order at least one product costing $0.50. 在customers表里在products表里在orders表里 cname( pid ( price = 0. 50 (PRODUCTS ) ORDERS CUSTOMERS) 找cid找cname(ORDERS ( PRODUCTS where price = 0. 50 ) pid CUSTOMERS) cnameto extract the product numbers o

25、f products that cost 50 cents. CHEAPS := (PRODUCTS where price = 0. 50) pid orThis can be accomplished by first writingCHEAPS := pid ( price = 0. 50(PRODUCTS ) )pidpnamecityquantitypriceP01CombDallas1114000.50P02BrushNewark2030000.50P03RazorDuluth1506001.00P04PenDuluth1253001.00P05PencilDallas221400

26、1.00P06FolderDallas1231002.00P07CaseNewark1005001.00 price = 0. 50(PRODUCTS ) pidpnamecityquantitypriceP01CombDallas1114000.50P02BrushNewark203000 0.50pidP01P02CHEAPSCHEAPS:= pid ( price = 0. 50 (PR0DUCTS ) )PRODUCTS where price = 0. 50CHEAPS := (PRODUCTS where price = 0. 50) pidget names of custome

27、rs who order at least one product costing $0.50lThen, by computing ORDERS CHEAPS we retrieve those ORDERS involving 50-cent products in ORDERS CHEAPS. get names of customers who order at least one product costing $0.50ordnomonthcidaidpidqtydollars1011JanC001a01P011000450.001012JanC001a01P011000450.0

28、01019FebC001a02P02400180.01017FebC001a06P03600540.01018FebC001a03P04600180.01023MarC001a04P05500450.01022MarC001a05P06400720.01205AprC001a05P07800720.01013JanC002a03P031000880.01021FebC004a06P011000460.001016JanC006a01P011000500.001020FebC006a03P07600600.001024MarC006a06P01800400.00pidP01P02CHEAPSor

29、dno monthcidaidpidqtydollars1011JanC001 a01 P011000 450.001012JanC001 a01 P011000 450.001019FebC001 a02 P02400180.0ORDERS CHEAPS1021FebC004 a06 P011000 460.001016JanC006 a01 P011000 500.001024MarC006 a06 P01800400.00cidC001C004C006(ORDERS CHEAPS) cidget names of customers who order at least one prod

30、uct costing $0.50lFinally we find the names of the customers who placed these ORDERS by joining CUSTOMERS. (ORDERS CHEAPS CUSTOMERS) cnameOR ( (ORDERS CHEAPS) cid CUSTOMERS) cname cname( cid(ORDERS CHEAPS) CUSTOMERS) cidcnamecitydiscntC001TiptopDuluth10.00C002BasicsDallas12.00C003AlliedDallas8.00C00

31、4ACMEDuluth8.00C006ACMEKyoto0.00cidC001C004C006cidcnameC001TiptopC004ACMEC006ACME (ORDERS CHEAPS CUSTOMERS) cname(ORDERS CHEAPS) CUSTOMERS)cnameTiptopACME (ORDERS CHEAPS CUSTOMERS) cnamelWe combine the two steps above cname(ORDERS pid ( price = 0. 50 PRODUCTS ) CUSTOMERS) (ORDERS ( PRODUCTS where pr

32、ice = 0. 50 ) pid CUSTOMERS) cnameReview：set-theoretic operations relational algebranative relational operations.UnionIntersectionDifferenceProductProjectionSelectionJoindivisionlThe Division Operation To introduce division, the last of the native relational operations, consider two tables Rand S, w

33、here the heading of S is a subset of the heading of R. Specifically assume thatHead(R) = A1. An B1. Bm, and Head(S) = B1. Bm.除运算lDEFINITION 5 division. lThe table T is the result of the division R S (which is read as R DIVIDE BY S) if Head(T) = A1. An and T contains exactly those rows t such that fo

34、r every row s in S, the row resulting from concatenating t and s can be found in table R. (See Definition 3 for what it means to concatenate t and s).lEXAMPLE T=R S ?ABCa1b1c1a2b1c1a1b2c1a1b2c2a2b1c2a1b2c3a1b2c4a1b1c5Cc1 S Ra1b1a2b1a1b2lEXAMPLE T=RS R SABCa1b1c1a2b1c1a1b2c1a1b2c2a2b1c2a1b2c3a1b2c4a1

35、b1c5Cc1ABa1b1a2b1a1b2R中元组在AB上的值象集S在C上的投影c1a1b1c1,c5 a2b1c1,c2 a1b2c1,c2,c3,c4T此方法书上没有lEXAMPLE T=R S ?ABCa1b1c1a2b1c1a1b2c1a1b2c2a2b1c2a1b2c3a1b2c4a1b1c5Cc1c2SRlEXAMPLE T=RS R S ABCa1b1c1a2b1c1a1b2c1a1b2c2a2b1c2a1b2c3a1b2c4a1b1c5Cc1c2ABa1b2a2b1la1b1c1,c5la2b1c1,c2la1b2c1,c2,c3,c4Tl R S BCb1c1ABCa1b1c

36、1a2b1c1a1b2c1a1b2c2a2b1c2a1b2c3a1b2c4a1b1c5T=R S ?lT=R S RBCb1c1Aa1a2la1(b1,c1),(b2,c1),(b2,c2) (b2,c3),(b2,c4),(b1,c5)la2(b1,c1),(b1,c2) ABCa1b1c1a2b1c1a1b2c1a1b2c2a2b1c2a1b2c3a1b2c4a1b1c5ST小结： 关系数据结构 二维表 选择（select） 投影（Project） 连接（Join） 除（Divide） 并（Union） 交（Intersection） 关系操作 差（Difference）笛卡尔积 （pro

37、duct） 关系模型关系模型关系代数 （在后面的章节介绍）Relational OperationsRelational algebraRelational Model实体完整性参照完整性用户完性关系完整性约束 增加（Insert）删除（Delete）修改（Update）Rule 4: Entity Integrity Rule. lHighest PROJECT R/ SELECT R where c/ PRODUCT TIMES x JOIN , DIVIDEBY INTERSECTION l Lowest UNION , DIFFERENCE Precedence of Relation

38、al Operations对表进行纵向操作对表进行横向操作两张表必须有相同列两张表必须兼容对单表进行操作两张表有相同列，结果保留了被除表独有的列。lEXAMPLE 2.7.10lExtract the list of product numbers for products ordered by customer c006.?Extract the list of product numbers for products ordered by customer c006.ordnomonthcidaidpidQtydollars1011JanC001a01P011000450.001012Ja

39、nC001a01P011000450.001019FebC001a02P02400180.01017FebC001a06P03600540.01018FebC001a03P04600180.01023MarC001a04P05500450.01022MarC001a05P06400720.01205AprC001a05P07800720.01013JanC002a03P031000880.01026MayC002a05P03800704.01014JanC003a03P0512001104.01021FebC004a06P011000460.001016JanC006a01P011000500

40、.001020FebC006a03P07600600.001024MarC006a06P01800400.00pc6:= pid ( cid=c006 (orders )pidp01p07pc6:= ( (orders where cid=c006 ) pid) orlThen find the customers who have placed orders for all these products (pc6). ?Extract the list of product numbers for products ordered by customer c006.pidp01p07pc6l

41、We can extract from orders the customer number, together with the products they order, by writing cp:= (ORDERS ) cid, pid cp:= cid, pid (ORDERS )lRetrieve the customers who have placed orders for all parts in pc6. ？所有的customer和他们订的products “Retrieve the customers who have placed orders for all parts

42、 in pc6 “can be solved by applying division. The resulting table lcppc6所有的customer和他们订的productsthe list of product numbers for products ordered by customer c006.？ordnomonthcidaidpidqtydollars1011JanC001a01P011000450.001012JanC001a01P011000450.001019FebC001a02P02400180.01017FebC001a06P03600540.01018F

43、ebC001a03P04600180.01023MarC001a04P05500450.01022MarC001a05P06400720.01205AprC001a05P07800720.01013JanC002a03P031000880.01026MayC002a05P03800704.01015JanC003a03P0512001104.01014JanC003a03P0512001104.01021FebC004a06P011000460.001016JanC006a01P011000500.001020FebC006a03P07600600.001024MarC006a06P01800

44、400.00cp:= cid, pid (ORDERS )cidpidC001P01C001P01C001P02C001P03C001P04C001P05C001P06C001P07C002P03C002P03C003P05C003P05C004P01C006P01C006P07C006P01cp:= (ORDERS ) cid, pid pidp01p07cppc6= ?pc6cidpidC001P01C001P01C001P02C001P03C001P04C001P05C001P06C001P07C002P03C002P03C003P05C003P05C004P01C006P01C006P

45、07C006P01cp:= (ORDERS ) cid, pid Retrieve the customers who have placed orders for all parts in pc6 pidp01p07cppc6cidC001C006pc6cp:= (ORDERS ) cid, pid cidpidC001P01C001P01C001P02C001P03C001P04C001P05C001P06C001P07C002P03C002P03C003P05C003P05C004P01C006P01C006P07C006P01C001 P01, P02, P03, P04, P05,

46、P06, P07C002 P03C003 P05C004 P01C006 P01, P07为什么要用除法？客户订的产品The resulting table : cp pc6(ORDERS ) cid, pid (ORDERS where cid=c006) pid cid, pid (ORDERS ) pid ( cid=c006 (orders )You should draw the lesson from this example that whenever the word “all” is used in a retrievalrequest, the query expressi

47、on to use may very well include the division operation.lThen find the customers who have placed orders for all products ordered by customer c006.(ORDERS ) cid, pid (ORDERS where cid=c006)pidl2.5 The interdependence of operationslSeveral of the relational operators defined in Section 2.2 are provided

48、 simply for added convenience, in the sense that the full power of relational algebra could be achieved with a smaller subset of the operations. We claim that a minimal set of basic operations consists of union, difference, product, selection, and projection.The remaining operators intersection, joi

49、n, and division can be expressed using the operations mentioned above.lTHEOREM 2.1 lLet A and B be two compatible tables, where Head(A) = Head(B) = A1. An. The intersection operation can be defined in terms of subtraction alone:AB = A -(A - B)ABA-BA-(A-B)ABlTHEOREM 2.2 The join of two tables R and S

50、, (where Head(R) = A1. An. B1. Bk and Head(S) = B1. Bk C1. Cm and n, k, 0,) can be expressed using product, selection, and projection, together with the assignment operator.ABCa1b1c1a1b2c2a2b2c1ADEa1b2c2a1b3c2a2b2c1RSThe join of two tables R and S, (where Head(R) = A1. An. B1. Bk and Head(S) = B1. B

51、k C1. Cm and n, k, 0,) can be expressed using product, selection, and projection, together with the assignment operator. RSR.A BCa1b1c1a1b1c1a1b1c1a1b2c2S.ADEa1b2c2a1b3c2a2b2c1a1b2c2a1b2c2a1b2c2a2b2c1a2b2c1a2b2c1a1b3c2a2b2c1a1b2c2a1b3c2a2b2c1ABCa1b1c1a1b2c2a2b2c1ADEa1b2c2a1b3c2a2b2c1RST = R SABCa1b1

52、c1a1b1c1a1b2c2DEb2c2b3c2b2c2a1b2c2a2b2c1b3c2b2c1ABCa1 b1c1a1 b2c2a2 b2c1ADEa1 b2c2a1 b3c2a2 b2c1RST =The join of two tables R and S, (where Head(R) = A1. An. B1. Bk and Head(S) = B1. Bk C1. Cm and n, k, 0,) can be expressed using product, selection, and projection, together with the assignment opera

53、tor.lTHEOREM 2.8.3. Division can be expressed using projection, product, and difference. Consider two tables R and S, where Head(R) = A1. An B1. Bm and Head(S)= B1. Bm . We can prove that R S = R A1,., An - (R A1,., An x S) - R) A1,., An .Review：set-theoretic operations Relational algebranative rela

54、tional operations.UnionIntersectionDifferenceProductProjectionSelectionJoindivision2.5 The interdependence of operationsTHEOREM 2.1 The intersection operation can be defined in terms of subtraction aloneTHEOREM 2.2 The join of two tables R and S,can be expressed using product, selection, and projection, together with the assignment operator. Find the customers who have placed orders for all products ordered by customer c002. Find