Bài giảng Database systems - Relational data model (2)

DATABASE SYSTEMS Nguyen Ngoc Thien An RELATIONAL DATA MODEL Spring 2014 Contents 2 Overview of Relational Data Model ER- & EER-to-Relational Mapping Relational Algebra Reading Suggestion: [1] Chapter 9 ER- & EER-to-Relational Mapping 3 ER- & EER-to-Relational Mapping 4 Step 1: Regular Entity Types Step 2: Weak Entity Types Step 3: Binary 1:1 Relationship Types Step 4: Binary 1:N Relationship Types Step 5: Binary M:N Relationship Types Step 6: Multivalued Attributes Step 7: N-ary Relationship Types Step 8: Specialization or Generalization Step 9: Union Types (Categories) 5 ERD of Company Database EMPLOYEE DEPARTMENT PROJECT WORKS_FOR MANAGES CONTROLS WORKS_ON SUPERVISION SSN Bdate Name Address Salary Sex Fname Minit Lname Name Number Locations Number_of_employees Start_date Hours Name Number Location Name Sex Birth_dateRelationship DEPENDENT N 1 1 1 1 N N N N 1 1 N DEPENDENTS_OF 6 Relational Schema of Company Database Fname Minit Lname SSN Bdate Address Sex Salary Super_SSN Dno Dname Dnumber Mgr_SSN Mgr_start_date Dnumber Dlocation PnumberPname Plocation Dnum Essn Pno Hours Essn Dependent_name BdateSex Relationship EMPLOYEE DEPARTMENT DEPT_LOCATIONS PROJECT WORKS_ON DEPENDENT ER- & EER-to-Relational Mapping 7 Step 1: Regular Entity Types Step 2: Weak Entity Types Step 3: Binary 1:1 Relationship Types Step 4: Binary 1:N Relationship Types Step 5: Binary M:N Relationship Types Step 6: Multivalued Attributes Step 7: N-ary Relationship Types Step 8: Specialization or Generalization Step 9: Union Types (Categories) Step 1: Regular Entity 8  Step 1: Mapping of Regular (Strong) Entity Types  Each regular entity type E  Create one new relation S.  Simple attributes of E  Attributes of S.  Composite attributes of E  Include only their simple component attributes in S.  Choose one of the key attributes of E as the primary key for S.  The other key attributes of E??? (Homework!!!)  The new relation is called an entity relation.  Each tuple represents an entity instance.  E.g.:  Regular entity types EMPLOYEE, DEPARTMENT, and PROJECT  relations EMPLOYEE, DEPARTMENT, and PROJECT.  Ssn, Dnumber, and Pnumber are the primary keys for the relations EMPLOYEE, DEPARTMENT, and PROJECT.  Knowledge that Dname of DEPARTMENT and Pname of PROJECT are secondary keys is kept for possible use later in the design. 9 Step 1: Regular Entity EMPLOYEE DEPARTMENT PROJECT WORKS_FOR MANAGES CONTROLS WORKS_ON SUPERVISION SSN Bdate Name Address Salary Sex Fname Minit Lname Name Number Locations Number_of_employees Start_date Hours Name Number Location Name Sex Birth_dateRelationship DEPENDENT N 1 1 1 1 N N N N 1 1 N DEPENDENTS_OF 10 Step 1: Regular Entity Fname Minit Lname SSN Bdate Address Sex Salary Super_SSN Dno Dname Dnumber Mgr_SSN Mgr_start_date Dnumber Dlocation PnumberPname Plocation Dnum Essn Pno Hours Essn Dependent_name BdateSex Relationship EMPLOYEE DEPARTMENT DEPT_LOCATIONS PROJECT WORKS_ON DEPENDENT ER- & EER-to-Relational Mapping 11 Step 1: Regular Entity Types Step 2: Weak Entity Types Step 3: Binary 1:1 Relationship Types Step 4: Binary 1:N Relationship Types Step 5: Binary M:N Relationship Types Step 6: Multivalued Attributes Step 7: N-ary Relationship Types Step 8: Specialization or Generalization Step 9: Union Types (Categories) Step 2: Weak Entity 12  Step 2: Mapping of Weak Entity Types  Each weak entity type W with owner entity type(s) Ei(s)  Create one new relation S.  Simple attributes and simple components of composite attributes of W  Attributes of S.  The primary key attribute(s) of the relation(s) corresponding to Ei(s)  Foreign key attribute(s) of S.  This takes care of mapping the identifying relationship type of W.  The primary key of S is the combination of the primary key(s) of the owner(s) and the partial key of W, if any.  E.g.:  Weak entity type DEPENDENT  Relation DEPENDENT.  The primary key SSN of EMPLOYEE relation  Foreign key attribute of DEPENDENT (renamed to Essn).  The primary key of DEPENDENT is {Essn, Dependent_name}. 13 EMPLOYEE DEPARTMENT PROJECT WORKS_FOR MANAGES CONTROLS WORKS_ON SUPERVISION SSN Bdate Name Address Salary Sex Fname Minit Lname Name Number Locations Number_of_employees Start_date Hours Name Number Location Name Sex Birth_dateRelationship DEPENDENT N 1 1 1 1 N N N N 1 1 N DEPENDENTS_OF Step 2: Weak Entity Primary Key Owner’s PK Partial PK 14 Fname Minit Lname SSN Bdate Address Sex Salary Super_SSN Dno Dname Dnumber Mgr_SSN Mgr_start_date Dnumber Dlocation PnumberPname Plocation Dnum Essn Pno Hours Essn Dependent_name BdateSex Relationship EMPLOYEE DEPARTMENT DEPT_LOCATIONS PROJECT WORKS_ON DEPENDENT Step 2: Weak Entity ER- & EER-to-Relational Mapping 15 Step 1: Regular Entity Types Step 2: Weak Entity Types Step 3: Binary 1:1 Relationship Types Step 4: Binary 1:N Relationship Types Step 5: Binary M:N Relationship Types Step 6: Multivalued Attributes Step 7: N-ary Relationship Types Step 8: Specialization or Generalization Step 9: Union Types (Categories) Step 3: Binary 1:1 Relationship (1) 16  Step 3: Mapping of Binary 1:1 Relationship Types  R is a relationship type with two entity types E1 and E2.  Case 1: At least one entity type has total participation in R.  E1: the entity type participates totally in R.  Include the primary key of the relation corresponding to E2 as a foreign key in the relation representing E1.  Include all the simple attributes and simple components of composite attributes of R in the relation of E1.  E.g.: DEPARTMENT’s participation in the 1:1 relationship type MANAGES is total.  Include the primary key of EMPLOYEE as foreign key in DEPARTMENT and rename it Mgr_ssn.  Include the simple attribute Start_date in the DEPARTMENT and rename it Mgr_start_date. Step 3: Binary 1:1 Relationship (2) 17 E1 E2R 1 1 A E1(PK1,,PK2,A) E2(PK2,) PK1 PK2 E1(PK1,) E2(PK2,,PK1,A) OR E1 E2R 1 1 A E1(PK1,,PK2, A) E2(PK2,) PK1 PK2 Step 3 – Case 1 Step 3: Binary 1:1 Relationship (3) 18  Case 2: Both entity types have optional participation in R.  Option 1: the same way in the case 1.  Option 2:  Create a new relation S representing R.  Include the primary keys of the relations representing E1 and E2 as foreign keys in S.  One of them becomes the primary key of S. The other is a unique key S.  Include all the simple attributes and simple components of composite attributes of R in S.  The new relation is called a relationship relation.  Each tuple in S represents an instance of R. Step 3: Binary 1:1 Relationship (4) 19 E1 E2R 1 1 A E1(PK1,) E2(PK2,) R(PK1,PK2,A) PK1 PK2 OR E1(PK1,) E2(PK2,) R(PK1,PK2,A) Step 3 – Case 2 – Option 2 Step 3: Binary 1:1 Relationship (5) 20  Case 2: Both entity types have optional participation in R.  Usage:  Option 1:  Drawback: May cause excessive NULL values in the foreign key.  Usually used when the relation containing the foreign key has a high percentage of instances participating in R.  Option 2:  Drawback: Having an extra relation, and requiring an extra join operation when combining related tuples from the tables.  Usually used when the relations of E1 and E2 have a low percentage of instances participating in R. 21 Step 3: Binary 1:1 Relationship EMPLOYEE DEPARTMENT PROJECT WORKS_FOR MANAGES CONTROLS WORKS_ON SUPERVISION SSN Bdate Name Address Salary Sex Fname Minit Lname Name Number Locations Number_of_employees Start_date Hours Name Number Location Name Sex Birth_dateRelationship DEPENDENT N 1 1 1 1 N N N N 1 1 N DEPENDENTS_OF 22 Step 3: Binary 1:1 Relationship Fname Minit Lname SSN Bdate Address Sex Salary Super_SSN Dno Dname Dnumber Mgr_SSN Mgr_start_date Dnumber Dlocation PnumberPname Plocation Dnum Essn Pno Hours Essn Dependent_name BdateSex Relationship EMPLOYEE DEPARTMENT DEPT_LOCATIONS PROJECT WORKS_ON DEPENDENT ER- & EER-to-Relational Mapping 23 Step 1: Regular Entity Types Step 2: Weak Entity Types Step 3: Binary 1:1 Relationship Types Step 4: Binary 1:N Relationship Types Step 5: Binary M:N Relationship Types Step 6: Multivalued Attributes Step 7: N-ary Relationship Types Step 8: Specialization or Generalization Step 9: Union Types (Categories) Step 4: Binary 1:N Relationship (1) 24  Step 4: Mapping of Binary 1:N Relationship Types  Case 1: The entity type E1 of N-side has total participation in R.  The same way in the case 1 of the step 3.  Case 2: The entity type E1 of N-side has partial participation in R.  The same way in the case 2 of the step 3.  Usually use the option 1 when E1 has a high percentage of instances participating in R.  Otherwise: use the option 2.  E.g.: 1:N relationship types SUPERVISION, CONTROLS, WORKS_FOR:  WORKS_FOR, CONTROLS: include the primary key Dnumber of DEPARTMENT as foreign key in EMPLOYEE (called Dno) and in PROJECT (called Dnum).  SUPERVISION: include the primary key of EMPLOYEE as foreign key in EMPLOYEE itself (called Super_ssn). Step 4: Binary 1:N Relationship (2) 25 E1 E2R N 1 A E1(PK1,,PK2,A) E2(PK2,) PK1 PK2 Step 4 – Case 1 Step 4: Binary 1:N Relationship (3) 26 OR E1 E2R N 1 APK1 PK2 E1(PK1,,PK2,A) E2(PK2,) E1(PK1,) E2(PK2,) R(PK1,PK2,A) Step 4 – Case 2 27 Step 4: Binary 1:N Relationship EMPLOYEE DEPARTMENT PROJECT WORKS_FOR MANAGES CONTROLS WORKS_ON SUPERVISION SSN Bdate Name Address Salary Sex Fname Minit Lname Name Number Locations Number_of_employees Start_date Hours Name Number Location Name Sex Birth_dateRelationship DEPENDENT N 1 1 1 1 N N N N 1 1 N DEPENDENTS_OF 28 Step 4: Binary 1:N Relationship Fname Minit Lname SSN Bdate Address Sex Salary Super_SSN Dno Dname Dnumber Mgr_SSN Mgr_start_date Dnumber Dlocation PnumberPname Plocation Dnum Essn Pno Hours Essn Dependent_name BdateSex Relationship EMPLOYEE DEPARTMENT DEPT_LOCATIONS PROJECT WORKS_ON DEPENDENT ER- & EER-to-Relational Mapping 29 Step 1: Regular Entity Types Step 2: Weak Entity Types Step 3: Binary 1:1 Relationship Types Step 4: Binary 1:N Relationship Types Step 5: Binary M:N Relationship Types Step 6: Multivalued Attributes Step 7: N-ary Relationship Types Step 8: Specialization or Generalization Step 9: Union Types (Categories) Step 5: Binary M:N Relationship 30  Step 5: Mapping of Binary M:N Relationship Types  For each binary M:N relationship type R  Create a new relation S for R.  Include primary keys of relations corresponding to two participating entity types as foreign key attributes in S.  Include any simple attributes and simple components of composite attributes of R in S.  The combination of the prime attributes forms the primary key of S.  E.g.: The M:N relationship type WORKS_ON:  Create the relation WORKS_ON.  Include the primary keys of PROJECT and EMPLOYEE as foreign keys in WORKS_ON (called Pno and Essn, respectively).  Include an attribute Hours in WORKS_ON.  The primary key of WORKS_ON is {Essn, Pno}. 31 Step 5: Binary M:N Relationship EMPLOYEE DEPARTMENT PROJECT WORKS_FOR MANAGES CONTROLS WORKS_ON SUPERVISION SSN Bdate Name Address Salary Sex Fname Minit Lname Name Number Locations Number_of_employees Start_date Hours Name Number Location Name Sex Birth_dateRelationship DEPENDENT N 1 1 1 1 N N N N 1 1 N DEPENDENTS_OF 32 Step 5: Binary M:N Relationship Fname Minit Lname SSN Bdate Address Sex Salary Super_SSN Dno Dname Dnumber Mgr_SSN Mgr_start_date Dnumber Dlocation PnumberPname Plocation Dnum Essn Pno Hours Essn Dependent_name BdateSex Relationship EMPLOYEE DEPARTMENT DEPT_LOCATIONS PROJECT WORKS_ON DEPENDENT Recursive Relationship (1) 33  Mapping of Recursive / Involuted Relationship Types  Relationship among different instances of the same entity type.  The name(s) of the prime attribute(s) must be changed to reflect the roles which entities play in the relationship.  E.g.: Involuted 1:1 relationship with optional membership. MARRYPERSON 1 1 PERSON (PersonID, Name, Address, ...) MARRY (HusbandID, WifeID, Date_of_marriage) Recursive Relationship (2) 34  E.g.: Involuted 1:N relationship.  With mandatory or almost mandatory membership:  With optional membership: SUPERVISEEMPLOYEE N 1 EMPLOYEE (ID, Ename, ..., SupervisorID) EMPLOYEE (ID, Ename, ...) SUPERVISE (ID, Start_date, ..., SupervisorID) Recursive Relationship (3) 35  E.g.: Involuted M:N relationship. COMPRISEPART M N PART (Pnumber, Description, ...) COMPRISE (MajorPnumber, MinorPnumber, Quantity) ER- & EER-to-Relational Mapping 36 Step 1: Regular Entity Types Step 2: Weak Entity Types Step 3: Binary 1:1 Relationship Types Step 4: Binary 1:N Relationship Types Step 5: Binary M:N Relationship Types Step 6: Multivalued Attributes Step 7: N-ary Relationship Types Step 8: Specialization or Generalization Step 9: Union Types (Categories) Step 6: Multivalued Attributes 37  Step 6: Mapping of Multivalued Attributes  For each multivalued attribute A  K: the primary key of the relation representing the entity type or relationship type that has A as an attribute.  Create a new relation S.  Include an attribute corresponding to A in S. If A is composite, include its simple components.  Include K as a foreign key in S.  The primary key of S is the combination of A and K.  E.g.: The new relation DEPT_LOCATIONS is created.  Dlocation represents the multivalued attribute LOCATIONS of DEPARTMENT.  The primary key Dnumber of DEPARTMENT is included as a foreign key in DEPT_LOCATIONS.  The primary key of DEPT_LOCATIONS: {Dnumber, Dlocation}. 38 Step 6: Multivalued Attributes EMPLOYEE DEPARTMENT PROJECT WORKS_FOR MANAGES CONTROLS WORKS_ON SUPERVISION SSN Bdate Name Address Salary Sex Fname Minit Lname Name Number Locations Number_of_employees Start_date Hours Name Number Location Name Sex Birth_dateRelationship DEPENDENT N 1 1 1 1 N N N N 1 1 N DEPENDENTS_OF 39 Step 6: Multivalued Attributes Fname Minit Lname SSN Bdate Address Sex Salary Super_SSN Dno Dname Dnumber Mgr_SSN Mgr_start_date Dnumber Dlocation PnumberPname Plocation Dnum Essn Pno Hours Essn Dependent_name BdateSex Relationship EMPLOYEE DEPARTMENT DEPT_LOCATIONS PROJECT WORKS_ON DEPENDENT ER- & EER-to-Relational Mapping 40 Step 1: Regular Entity Types Step 2: Weak Entity Types Step 3: Binary 1:1 Relationship Types Step 4: Binary 1:N Relationship Types Step 5: Binary M:N Relationship Types Step 6: Multivalued Attributes Step 7: N-ary Relationship Types Step 8: Specialization or Generalization Step 9: Union Types (Categories) Step 7: N-ary Relationship Types 41  Step 7: Mapping of N-ary Relationship Types  For each n-ary relationship type R, where n>2:  Create a new relation S to represent R.  Include as foreign key attributes in S the primary keys of the relations representing the participating entity types.  Include simple attributes and simple components of composite attributes of R as attributes of S.  E.g.: The relationship type SUPPY can be mapped to the relation SUPPLY, whose primary key is the combination of the three foreign keys {Sname, PartNo, ProjName}.  Note: if the cardinality constraint on any of the entity types E participating in the relationship is 1, the primary key should not include the foreign key attributes that reference the relation E’ corresponding to E. 42 SUPPLYSUPPLIER NN PROJECT PART SName ProjName PartNo Quantity N SUPPLIER (SName,...) PROJECT (ProjName,) PART (PartNo,) SUPPLY (SName, ProjName, PartNo, Quantity) Step 7: N-ary Relationship Exercises 43  Map SUPPLY relationship type into the relational schema. SUPPLYSUPPLIER N1 PROJECT PART SName ProjName PartNo Quantity N SUPPLYSUPPLIER 11 PROJECT PART SName ProjName PartNo Quantity 1 SUPPLYSUPPLIER N1 PROJECT PART SName ProjName PartNo Quantity 1 Mapping for ER Model Constructs 44  In a relational schema, relationship types are not represented explicitly. ER- & EER-to-Relational Mapping 45 Step 1: Regular Entity Types Step 2: Weak Entity Types Step 3: Binary 1:1 Relationship Types Step 4: Binary 1:N Relationship Types Step 5: Binary M:N Relationship Types Step 6: Multivalued Attributes Step 7: N-ary Relationship Types Step 8: Specialization or Generalization Step 9: Union Types (Categories) Step 8: Specialization/Generalization 46  Step 8: Mapping Specialization/Generalization  Conventions  Superclass 𝐶 and its 𝑚 subclasses {𝑆1, 𝑆2, , 𝑆𝑚}.  The attributes of 𝐶 are 𝑘, 𝑎1, 𝑎2, , 𝑎𝑛 .  𝑘 is the primary key of 𝐶.  𝐴𝑡𝑡𝑟𝑠(𝑅): the attributes of relation R.  𝑃𝐾(𝑅): the primary key of R.  Mapping by using one of the four following options:  Option 8A: Multiple Relations - Superclass and Subclasses.  Option 8B: Multiple Relations - Subclass Relations only.  Option 8C: Single Relation with One Type Attribute.  Option 8D: Single Relation with Multiple Type Attributes. Step 8 – Option 8A & 8B 47  Option 8A: Multiple Relations - Superclass & Subclasses  Create a relation 𝐿 for 𝐶:  𝐴𝑡𝑡𝑟𝑠 𝐿 = 𝑘, 𝑎1, 𝑎2, , 𝑎𝑛 𝑃𝐾 𝐿 = 𝑘  Create a relation 𝐿𝑖 for each subclass 𝑆𝑖 (1 ≤ 𝑖 ≤ 𝑚):  𝐴𝑡𝑡𝑟𝑠 𝐿𝑖 = 𝑘 ∪ 𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒𝑠 𝑜𝑓 𝑆𝑖 𝑃𝐾 𝐿𝑖 = 𝑘  For any specialization (total / partial, disjoint / overlapping).  Option 8B: Multiple Relations - Subclass Relations only  Create a relation 𝐿𝑖 for each subclass 𝑆𝑖 1 ≤ 𝑖 ≤ 𝑚 :  𝐴𝑡𝑡𝑟𝑠 𝐿𝑖 = 𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒𝑠 𝑜𝑓 𝑆𝑖 ∪ {𝑘, 𝑎1, 𝑎2, , 𝑎𝑛}  𝑃𝐾 𝐿𝑖 = 𝑘  For total specialization.  Disjointness is recommended (overlapping  duplicated). 48 Example - Option 8A 49 Example - Option 8B Step 8 – Option 8C & 8D 50  Option 8C: Single Relation with One Type Attribute  Create a relation 𝐿:  𝐴𝑡𝑡𝑟𝑠 𝐿 = 𝑘, 𝑎1, 𝑎2, , 𝑎𝑛 ∪ {𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒𝑠 𝑜𝑓 𝑆1} ∪ ⋯ ∪ 𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒𝑠 𝑜𝑓 𝑆𝑚 ∪ {𝑡}  𝑃𝐾(𝐿) = 𝑘  𝑡: a type (or discriminating) attribute indicating the subclass of each tuple.  For disjoint specialization  generate many NULL values if many specific attributes exist in the subclasses.  Option 8D: Single Relation with Multiple Type Attributes  Create a relation 𝐿:  𝐴𝑡𝑡𝑟𝑠 𝐿 = 𝑘, 𝑎1, , 𝑎𝑛 ∪ 𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒𝑠 𝑜𝑓 𝑆1 ∪ ⋯ ∪ 𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒𝑠 𝑜𝑓 𝑆𝑚 ∪ 𝑡1, , 𝑡𝑚  𝑃𝐾(𝐿) = 𝑘  𝑡𝑖(1 ≤ 𝑖 ≤ 𝑚): a Boolean type attribute indicating subclasses 𝑆𝑖(s) of a tuple.  For overlapping specialization (but also for disjoint specialization). 51 Example - Option 8C 52 Example - Option 8D Mapping Shared Subclasses (1) 53  Mapping of Shared Subclasses  A shared subclass is a subclass of several classes indicating multiple inheritance. These classes must all have the same key attribute.  Can apply any of the options discussed in Step 8 to a shared subclass, subject to the restriction discussed in Step 8 of the mapping algorithm. Mapping Shared Subclasses (2) 54 Mapping Shared Subclasses (3) 55 ER- & EER-to-Relational Mapping 56 Step 1: Regular Entity Types Step 2: Weak Entity Types Step 3: Binary 1:1 Relationship Types Step 4: Binary 1:N Relationship Types Step 5: Binary M:N Relationship Types Step 6: Multivalued Attributes Step 7: N-ary Relationship Types Step 8: Specialization or Generalization Step 9: Union Types (Categories) Step 9: Union Types 57  Step 9: Mapping of Union Types (Categories)  Create a new relation S for the category with a primary key.  Include any attributes of the category in S.  If superclasses have different keys:  Include a new key attribute, called surrogate key, as foreign key in each relation of the superclasses.  These foreign keys reference to the primary key of S.  E.g.: OWNER category.  If superclasses have the same key  No need for a surrogate key.  Primary keys of relations corresponding to superclasses reference to the primary key of S.  E.g.: REGISTERED_VEHICLE category. 58 Q & A 59