數(shù)據(jù)庫第二章5節(jié)

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.并運(yùn)算差運(yùn)算交運(yùn)算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投影運(yùn)算投影運(yùn)算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選擇運(yùn)算選擇運(yùn)算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 連接運(yùn)算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. 用學(xué)過的關(guān)系代數(shù)運(yùn)算完成上述查詢。到哪里查詢？涉及到幾張表？cidcnamecitydiscntC001TiptopDuluth10.00C002BasicsDallas12.00pidpnamecityquantitypriceP01CombDallas1114000.50P02BrushNewark2

23、030000.50P03RazorDuluth1506001.00ordnomonthcidaidpidQtydollars1011JanC001a01P011000450.001012JanC001a01P011000450.001019FebC001a02P02400180.01017FebC001a06P03600540.0customers和products之間有無聯(lián)系？靠什么聯(lián)系？請寫出關(guān)系代數(shù)式。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.除運(yùn)算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此方法書上沒有l(wèi)EXAMPLE 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小結(jié)： 關(guān)系數(shù)據(jù)結(jié)構(gòu) 二維表 選擇（select） 投影（Project） 連接（Join） 除（Divide） 并（Union） 交（Intersection） 關(guān)系操作 差（Difference）笛卡爾積 （pro

37、duct） 關(guān)系模型關(guān)系模型關(guān)系代數(shù) （在后面的章節(jié)介紹）Relational OperationsRelational algebraRelational Model實(shí)體完整性參照完整性用戶完性關(guān)系完整性約束 增加（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對表進(jìn)行縱向操作對表進(jìn)行橫向操作兩張表必須有相同列兩張表必須兼容對單表進(jìn)行操作兩張表有相同列，結(jié)果保留了被除表獨(dú)有的列。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為什么要用除法？客戶訂的產(chǎn)品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