Designing a Database Week 10: Database Schema …

1 1 Database Design 1 CSC343 introduction to DatabasesWeek 10: DatabaseDesignDatabase DesignDatabase DesignFrom an ER Schema to a RelationalFrom an ER Schema to a RelationalOneOneRestructuring an ER schemaRestructuring an ER schemaPerformance AnalysisPerformance AnalysisAnalysis of Redundancies, RemovingAnalysis of Redundancies, RemovingGeneralizationsGeneralizationsTr anslation into a Relational SchemaTranslation into a Relational SchemaDatabase Design 2 CSC343 introduction to DatabasesSupplierPartsuppliesCustomerord ers(1,N)(1,N)PartnameSupplierPartCustome rPart(Name,Description,Part#)Supplier(Na me, Addr)Customer(Name, Addr)Supplies(Name,Part#, Date)Orders(Name,Part#)HierarchicalNetwo rkRelationalSupplierCustomerDate(1,N)(1, 1)

2 Designing a DatabaseDesigning a DatabaseSchemaSchemaDatabase Design 3 CSC343 introduction to Databases(Relational) Database Design Given a conceptual Schema (ER, but could also bea UML), generate a logical (relational) Schema . This is not just a simple translation from onemodel to another for two main reasons:onot all the constructs of the Entity-Relationshipmodel can be translated naturally into therelational model;othe Schema must be restructured in such a wayas to make the execution of the projectedoperations as efficient as possible. The topic is covered in Section of the Design 4 CSC343 introduction to DatabasesDatabaseDesignProcess2 Database Design 5 CSC343 introduction to DatabasesLogical Design StepsoIt is helpful to divide the design intotwo steps:oRestructuring of the Entity-Relationship Schema , based oncriteria for the optimization of theschema and the simplification of thefollowing step;oTranslation into the logicalmodel, based on the features of thelogical model (in our case, therelational model).

3 Database Design 6 CSC343 introduction to DatabasesPerformance Analysis An ER Schema is restructured to optimize: Cost of an operation (evaluated in terms of thenumber of occurrences of entities and relationshipsthat are visited during the execution of anoperation); Storage requirements (evaluated in terms ofnumber of bytes necessary to store the datadescribed by the Schema ). In order to study these parameters, we need to know: Projected volume of data; Projected operation Design 7 CSC343 introduction to DatabasesCost Model The cost of an operation is measured in terms ofthe number of disk accesses required. A diskaccess is, generally, orders of magnitude moreexpensive than in-memory accesses, or CPUoperations. For a coarse estimate of cost, we assume that a Read operation (for one entity orrelationship) requires 1 disk access; A Write operation (for one entity orrelationship) requires 2 disk accesses (readfrom disk, change, write back to disk).

4 There are many other cost models depending onuse and type of DB Warehouse (OLAP - On-Line AnalysisProcessing) Operational DB (OLTP - On-Line TransactionProcessing) Database Design 8 CSC343 introduction to DatabasesEmployee-Department Example3 Database Design 9 CSC343 introduction to DatabasesTypical Operations Operation 1: Assign an employee to a project. Operation 2: Find an employee record, including herdepartment, and the projects she works for. Operation 3: Find records of employees for adepartment. Operation 4: For each branch, retrieve itsdepartments, and for each department, retrieve thelast names of their managers, and the list of theiremployees. Need operations and their volume/frequencyDatabase Design 10 CSC343 introduction to DatabasesWorkload Design During initial design and requirementsanalysis Estimate operations and frequency Gross estimates at best After Database is operational Tools record actual workloadcharacteristicsDatabase Design 11 CSC343 introduction to DatabasesAnalysisStepsDatabase Design 12 CSC343 introduction to DatabasesAnalysis of Redundancies A redundancy in a conceptualschema corresponds to a piece ofinformation that can be derived(that is, obtained through a seriesof retrieval operations) from otherdata in the Database .

5 An Entity-Relationship schemamay contain various forms Design 13 CSC343 introduction to DatabasesExamples of RedundanciesDatabase Design 14 CSC343 introduction to DatabasesDeciding About Redundancies The presence of a redundancy in a databasemay be an advantage: a reduction in the number ofaccesses necessary to obtain the derivedinformation; a disadvantage: because of larger storagerequirements, (but, usually at negligible cost) andthe necessity to carry out additional operationsin order to keep the derived data consistent. The decision to maintain or eliminate aredundancy is made by comparing the cost ofoperations that involve the redundantinformation and the storage needed, in thecase of presence or absence of Design 15 CSC343 introduction to DatabasesCost Comparison: An ExampleIn this Schema the attributeNumberOfInhabitants Design 16 CSC343 introduction to DatabasesRemoving Generalizations The relational model does not allow directrepresentation of generalizations that maybe present in an E-R diagram.

6 For example, here is an ER Schema withgeneralizations:5 Database Design 17 CSC343 introduction to DatabasesOption 1 Option 2 PossibleRestructuringsNote! Database Design 18 CSC343 introduction to 4 (combination)Option 3 Database Design 19 CSC343 introduction to DatabasesGeneral Rules For RemovingGeneralization Option 1 is convenient when the operations involvethe occurrences and the attributes of E0, E1 and E2more or less in the same way. Option 2 is possible only if the generalizationsatisfies the coverage constraint ( , everyinstance of E0 is either an instance of E1 or E2) andis useful when there are operations that apply onlyto occurrences of E1 or E2. Option 3 is useful when the generalization is notcoverage-compliant and the operations refer toeither occurrences and attributes of E1 (E2) or ofE0, and therefore make distinctions between childand parent entities.

7 Available options can be combined (see option 4) Database Design 20 CSC343 introduction to DatabasesPartitioning and Merging ofEntities and Relationships Entities and relationships of an E-R Schema can bepartitioned or merged to improve the efficiency ofoperations, using the following principle: The same criteria with those discussed forredundancies are valid in making a decision aboutthis type of are reduced by separatingattributes of the same concept that areaccessed by different operations andby merging attributes of differentconcepts that are accessed by thesame Design 21 CSC343 introduction to DatabasesExample of PartitioningRecall this is a weak entityDatabase Design 22 CSC343 introduction to DatabasesDeletion of Multi-Valued AttributeDatabase Design 23 CSC343 introduction to DatabasesMerging EntitiesTwo candidate keysDatabase Design 24 CSC343 introduction to DatabasesPartitioning of a RelationshipSuppose thatcompositionrepresentscurrent

8 Andpastcompositionsof a teamAre these equivalent?7 Database Design 25 CSC343 introduction to DatabasesSelecting a Primary Key Every relation must have a unique primarykey. The criteria for this decision are as follows: Attributes with null values cannot form primarykeys; One/few attributes is preferable to manyattributes; Internal key preferable to external ones (weakentity); A key that is used by many operations toaccess the instances of an entity is preferableto others. At this stage, if none of the candidate keyssatisfies the above requirements, it may bebest to introduce a new attribute ( , socialinsurance #, student #,..) Database Design 26 CSC343 introduction to DatabasesTranslation into a Logical Schema The second step of logical design consists of atranslation between different data models.

9 Starting from an E-R Schema , an equivalentrelational Schema is constructed. By equivalent , we mean a Schema capable ofrepresenting the same information. We will deal with the translation problemsystematically, beginning with thefundamental case, that of entities linked bymany-to-many Design 27 CSC343 introduction to DatabasesMany-to-Many RelationshipsEmployee(Number, Surname, Salary)Project(Code, Name, Budget)Participation(Number, Code, StartDate) Database Design 28 CSC343 introduction to DatabasesMany-to-Many RecursiveRelationshipsProduct(Code, Name, Cost)Composition(Part, SubPart, Quantity)8 Database Design 29 CSC343 introduction to DatabasesTernary RelationshipsSupplier(SupplierID, SupplierName)Product(Code, Type)Department(Name, Telephone)Supply(Supplier, Product, Department, Quantity)

10 Database Design 30 CSC343 introduction to DatabasesOne-to-Many RelationshipsPlayer(Surname, DateOfBirth, Position)Team(Name, Town, TeamColours)Contract(PlayerSurname, PlayerDateOfBirth,Team, Salary)ORPlayer(Surname, DateOfBirth, Position,TeamName, Salary)Team(Name, Town, TeamColours) Database Design 31 CSC343 introduction to DatabasesWeak EntitiesStudent(RegistrationNumber, University,Surname, EnrolmentYear)University(Name, Town, Address) Database Design 32 CSC343 introduction to DatabasesOne-to-One RelationshipsHead(Number, Name, Salary, Department,StartDate)Department(Name, Telephone, Branch)ORHead(Number, Name, Salary, StartDate)Department(Name, Telephone,HeadNumber, Branch)9 Database Design 33 CSC343 introduction to DatabasesOptional One-to-OneRelationshipsEmployee(Number, Name, Salary)Department(Name, Telephone, Branch, Head,StartDate)Or, if both entities are optionalEmployee(Number, Name, Salary)Department(Name, Telephone, Branch)Management(Head, Department, StartDate) Database Design 34 CSC343 introduction to DatabasesA Sample ER SchemaDatabase Design 35 CSC343 introduction to DatabasesEntities with Internal IdentifiersE3(A31, A32)E4(A41, A42)E5(A51, A52)E6(A61, A62, A63)E3E4E5E6 Database Design 36 CSC343 introduction to Databases1-1 and Optional 1-1 RelationshipsE5E6E3E4R3R4R5E5(A51, A52, A61R3, A62R3, AR3, A61R4,A62R4, A61R5, A62R5, AR5)