Chapter 7: Relational Database Design

2y ago
125 Views
2 Downloads
473.36 KB
85 Pages
Last View : 16d ago
Last Download : 2m ago
Upload by : Luis Wallis
Transcription

Chapter 7: Relational Database DesignDatabase System Concepts, 5th Ed. Silberschatz, Korth and SudarshanSee www.db-book.com for conditions on re-use

Chapter 7: Relational Database Design Features of Good Relational Design Atomic Domains and First Normal Form Decomposition Using Functional Dependencies Functional Dependency Theory Algorithms for Functional Dependencies Decomposition Using Multivalued Dependencies More Normal Form Database-Design Process Modeling Temporal DataDatabase System Concepts - 5th Edition, July 28, 2005.7.2 Silberschatz, Korth and Sudarshan

The Banking Schema branch (branch name, branch city, assets) customer (customer id, customer name, customer street, customer city) loan (loan number, amount) account (account number, balance) employee (employee id. employee name, telephone number, start date) dependent name (employee id, dname) account branch (account number, branch name) loan branch (loan number, branch name) borrower (customer id, loan number) depositor (customer id, account number) cust banker (customer id, employee id, type) works for (worker employee id, manager employee id) payment (loan number, payment number, payment date, payment amount) savings account (account number, interest rate) checking account (account number, overdraft amount)Database System Concepts - 5th Edition, July 28, 2005.7.3 Silberschatz, Korth and Sudarshan

Combine Schemas? Suppose we combine borrow and loan to getbor loan (customer id, loan number, amount ) Result is possible repetition of information (L-100 in example below)Database System Concepts - 5th Edition, July 28, 2005.7.4 Silberschatz, Korth and Sudarshan

A Combined Schema Without Repetition Consider combining loan branch and loanloan amt br (loan number, amount, branch name) No repetition (as suggested by example below)Database System Concepts - 5th Edition, July 28, 2005.7.5 Silberschatz, Korth and Sudarshan

What About Smaller Schemas? Suppose we had started with bor loan. How would we know to split up(decompose) it into borrower and loan? Write a rule “if there were a schema (loan number, amount), thenloan number would be a candidate key” Denote as a functional dependency:loan number amount In bor loan, because loan number is not a candidate key, the amount of a loanmay have to be repeated. This indicates the need to decompose bor loan. Not all decompositions are good. Suppose we decompose employee intoemployee1 (employee id, employee name)employee2 (employee name, telephone number, start date) The next slide shows how we lose information -- we cannot reconstruct theoriginal employee relation -- and so, this is a lossy decomposition.Database System Concepts - 5th Edition, July 28, 2005.7.6 Silberschatz, Korth and Sudarshan

A Lossy DecompositionDatabase System Concepts - 5th Edition, July 28, 2005.7.7 Silberschatz, Korth and Sudarshan

First Normal Form Domain is atomic if its elements are considered to be indivisible unitszExamples of non-atomic domains: Setof names, composite attributes Identificationnumbers like CS101 that can be broken up intoparts A relational schema R is in first normal form if the domains of allattributes of R are atomic Non-atomic values complicate storage and encourage redundant(repeated) storage of datazExample: Set of accounts stored with each customer, and set ofowners stored with each accountzWe assume all relations are in first normal form (and revisit this inChapter 9)Database System Concepts - 5th Edition, July 28, 2005.7.8 Silberschatz, Korth and Sudarshan

First Normal Form (Cont’d) Atomicity is actually a property of how the elements of the domain areused.zExample: Strings would normally be considered indivisiblezSuppose that students are given roll numbers which are strings ofthe form CS0012 or EE1127zIf the first two characters are extracted to find the department, thedomain of roll numbers is not atomic.zDoing so is a bad idea: leads to encoding of information inapplication program rather than in the database.Database System Concepts - 5th Edition, July 28, 2005.7.9 Silberschatz, Korth and Sudarshan

Goal — Devise a Theory for the Following Decide whether a particular relation R is in “good” form. In the case that a relation R is not in “good” form, decompose it into aset of relations {R1, R2, ., Rn} such thatzeach relation is in good formzthe decomposition is a lossless-join decomposition Our theory is based on:zfunctional dependencieszmultivalued dependenciesDatabase System Concepts - 5th Edition, July 28, 2005.7.10 Silberschatz, Korth and Sudarshan

Functional Dependencies Constraints on the set of legal relations. Require that the value for a certain set of attributes determinesuniquely the value for another set of attributes. A functional dependency is a generalization of the notion of a key.Database System Concepts - 5th Edition, July 28, 2005.7.11 Silberschatz, Korth and Sudarshan

Functional Dependencies (Cont.) Let R be a relation schemaα R and β R The functional dependencyα βholds on R if and only if for any legal relations r(R), whenever anytwo tuples t1 and t2 of r agree on the attributes α, they also agreeon the attributes β. That is,t1[α] t2 [α] t1[β ] t2 [β ] Example: Consider r(A,B ) with the following instance of r.1 41 53 7 On this instance, A B does NOT hold, but B A does hold.Database System Concepts - 5th Edition, July 28, 2005.7.12 Silberschatz, Korth and Sudarshan

Functional Dependencies (Cont.) K is a superkey for relation schema R if and only if K R K is a candidate key for R if and only ifzK R, andzfor no α K, α R Functional dependencies allow us to express constraints that cannotbe expressed using superkeys. Consider the schema:bor loan (customer id, loan number, amount ).We expect this functional dependency to hold:loan number amountbut would not expect the following to hold:amount customer nameDatabase System Concepts - 5th Edition, July 28, 2005.7.13 Silberschatz, Korth and Sudarshan

Use of Functional Dependencies We use functional dependencies to:ztest relations to see if they are legal under a given set of functionaldependencies. zIf a relation r is legal under a set F of functional dependencies, wesay that r satisfies F.specify constraints on the set of legal relations Wesay that F holds on R if all legal relations on R satisfy the set offunctional dependencies F. Note: A specific instance of a relation schema may satisfy a functionaldependency even if the functional dependency does not hold on all legalinstances.zFor example, a specific instance of loan may, by chance, satisfyamount customer name.Database System Concepts - 5th Edition, July 28, 2005.7.14 Silberschatz, Korth and Sudarshan

Functional Dependencies (Cont.) A functional dependency is trivial if it is satisfied by all instances of arelationzzExample: customer name, loan number customer name customer name customer nameIn general, α β is trivial if β αDatabase System Concepts - 5th Edition, July 28, 2005.7.15 Silberschatz, Korth and Sudarshan

Closure of a Set of FunctionalDependencies Given a set F set of functional dependencies, there are certain otherfunctional dependencies that are logically implied by F.zFor example: If A B and B C, then we can infer that A C The set of all functional dependencies logically implied by F is the closureof F. We denote the closure of F by F . F is a superset of F.Database System Concepts - 5th Edition, July 28, 2005.7.16 Silberschatz, Korth and Sudarshan

Boyce-Codd Normal FormA relation schema R is in BCNF with respect to a set F offunctional dependencies if for all functional dependencies in F ofthe formα βwhere α R and β R, at least one of the following holds: α β is trivial (i.e., β α) α is a superkey for RExample schema not in BCNF:bor loan ( customer id, loan number, amount )because loan number amount holds on bor loan but loan number isnot a superkeyDatabase System Concepts - 5th Edition, July 28, 2005.7.17 Silberschatz, Korth and Sudarshan

Decomposing a Schema into BCNF Suppose we have a schema R and a non-trivial dependency α βcauses a violation of BCNF.We decompose R into: (α U β ) (R-(β-α)) In our example,zα loan numberzβ amountand bor loan is replaced byzz(α U β ) ( loan number, amount )( R - ( β - α ) ) ( customer id, loan number )Database System Concepts - 5th Edition, July 28, 2005.7.18 Silberschatz, Korth and Sudarshan

BCNF and Dependency Preservation Constraints, including functional dependencies, are costly to check inpractice unless they pertain to only one relation If it is sufficient to test only those dependencies on each individualrelation of a decomposition in order to ensure that all functionaldependencies hold, then that decomposition is dependencypreserving. Because it is not always possible to achieve both BCNF anddependency preservation, we consider a weaker normal form, knownas third normal form.Database System Concepts - 5th Edition, July 28, 2005.7.19 Silberschatz, Korth and Sudarshan

Third Normal Form A relation schema R is in third normal form (3NF) if for all:α β in F at least one of the following holds:zα β is trivial (i.e., β α)zα is a superkey for RzEach attribute A in β – α is contained in a candidate key for R.(NOTE: each attribute may be in a different candidate key) If a relation is in BCNF it is in 3NF (since in BCNF one of the first twoconditions above must hold). Third condition is a minimal relaxation of BCNF to ensure dependencypreservation (will see why later).Database System Concepts - 5th Edition, July 28, 2005.7.20 Silberschatz, Korth and Sudarshan

Goals of Normalization Let R be a relation scheme with a set F of functionaldependencies. Decide whether a relation scheme R is in “good” form. In the case that a relation scheme R is not in “good” form,decompose it into a set of relation scheme {R1, R2, ., Rn} suchthatzeach relation scheme is in good formzthe decomposition is a lossless-join decompositionzPreferably, the decomposition should be dependencypreserving.Database System Concepts - 5th Edition, July 28, 2005.7.21 Silberschatz, Korth and Sudarshan

How good is BCNF? There are database schemas in BCNF that do not seem to besufficiently normalized Consider a databaseclasses (course, teacher, book )such that (c, t, b) classes means that t is qualified to teach c, and bis a required textbook for c The database is supposed to list for each course the set of teachersany one of which can be the course’s instructor, and the set of books,all of which are required for the course (no matter who teaches it).Database System Concepts - 5th Edition, July 28, 2005.7.22 Silberschatz, Korth and Sudarshan

How good is BCNF? sedatabasedatabaseoperating systemsoperating systemsoperating systemsoperating etebookDB ConceptsUllmanDB ConceptsUllmanDB ConceptsUllmanOS ConceptsStallingsOS ConceptsStallingsclasses There are no non-trivial functional dependencies and therefore therelation is in BCNF Insertion anomalies – i.e., if Marilyn is a new teacher that can teachdatabase, two tuples need to be inserted(database, Marilyn, DB Concepts)(database, Marilyn, Ullman)Database System Concepts - 5th Edition, July 28, 2005.7.23 Silberschatz, Korth and Sudarshan

How good is BCNF? (Cont.) Therefore, it is better to decompose classes g systemsoperating basedatabaseoperating systemsoperating systemsDB ConceptsUllmanOS ConceptsShawtextThis suggests the need for higher normal forms, such as FourthNormal Form (4NF), which we shall see later.Database System Concepts - 5th Edition, July 28, 2005.7.24 Silberschatz, Korth and Sudarshan

Functional-Dependency Theory We now consider the formal theory that tells us which functionaldependencies are implied logically by a given set of functionaldependencies. We then develop algorithms to generate lossless decompositions intoBCNF and 3NF We then develop algorithms to test if a decomposition is dependency-preservingDatabase System Concepts - 5th Edition, July 28, 2005.7.25 Silberschatz, Korth and Sudarshan

Closure of a Set of FunctionalDependencies Given a set F set of functional dependencies, there are certain otherfunctional dependencies that are logically implied by F.zFor example: If A B and B C, then we can infer that A C The set of all functional dependencies logically implied by F is the closureof F. We denote the closure of F by F . We can find all of F by applying Armstrong’s Axioms:zif β α, then α β(reflexivity)zif α β, then γ α γ β(augmentation)zif α β, and β γ, then α γ (transitivity) These rules arezsound (generate only functional dependencies that actually hold) andzcomplete (generate all functional dependencies that hold).Database System Concepts - 5th Edition, July 28, 2005.7.26 Silberschatz, Korth and Sudarshan

Example R (A, B, C, G, H, I)F { A BA CCG HCG IB H} some members of F zA H byzAG I byztransitivity from A B and B Haugmenting A C with G, to get AG CGand then transitivity with CG ICG HI byaugmenting CG I to infer CG CGI,and augmenting of CG H to infer CGI HI,and then transitivityDatabase System Concepts - 5th Edition, July 28, 2005.7.27 Silberschatz, Korth and Sudarshan

Procedure for Computing F To compute the closure of a set of functional dependencies F:F Frepeatfor each functional dependency f in F apply reflexivity and augmentation rules on fadd the resulting functional dependencies to F for each pair of functional dependencies f1and f2 in F if f1 and f2 can be combined using transitivitythen add the resulting functional dependency to F until F does not change any furtherNOTE: We shall see an alternative procedure for this task laterDatabase System Concepts - 5th Edition, July 28, 2005.7.28 Silberschatz, Korth and Sudarshan

Closure of Functional Dependencies(Cont.) We can further simplify manual computation of F by using thefollowing additional rules.zIf α β holds and α γ holds, then α β γ holds (union)zIf α β γ holds, then α β holds and α γ holds(decomposition)zIf α β holds and γ β δ holds, then α γ δ holds(pseudotransitivity)The above rules can be inferred from Armstrong’s axioms.Database System Concepts - 5th Edition, July 28, 2005.7.29 Silberschatz, Korth and Sudarshan

Closure of Attribute Sets Given a set of attributes α, define the closure of α under F (denoted byα ) as the set of attributes that are functionally determined by α underF Algorithm to compute α , the closure of α under Fresult : α;while (changes to result) dofor each β γ in F dobeginif β result then result : result γendDatabase System Concepts - 5th Edition, July 28, 2005.7.30 Silberschatz, Korth and Sudarshan

Example of Attribute Set Closure R (A, B, C, G, H, I) F {A BA CCG HCG IB H} (AG) 1. result AG2. result ABCG(A C and A B)3. result ABCGH(CG H and CG AGBC)4. result ABCGHI (CG I and CG AGBCH) Is AG a candidate key?1.Is AG a super key?2.Does AG R? Is (AG) RIs any subset of AG a superkey?1.1.Does A R? Is (A) R2.Does G R? Is (G) RDatabase System Concepts - 5th Edition, July 28, 2005.7.31 Silberschatz, Korth and Sudarshan

Uses of Attribute ClosureThere are several uses of the attribute closure algorithm: Testing for superkey:zTo test if α is a superkey, we compute α , and check if α containsall attributes of R. Testing functional dependencieszTo check if a functional dependency α β holds (or, in otherwords, is in F ), just check if β α .zThat is, we compute α by using attribute closure, and then checkif it contains β.zIs a simple and cheap test, and very useful Computing closure of FzFor each γ R, we find the closure γ , and for each S γ , weoutput a functional dependency γ S.Database System Concepts - 5th Edition, July 28, 2005.7.32 Silberschatz, Korth and Sudarshan

Canonical Cover Sets of functional dependencies may have redundant dependenciesthat can be inferred from the otherszFor example: A C is redundant in: {A B, B C}zParts of a functional dependency may be redundant E.g.:on RHS: {A B, B C, A CD} can be simplifiedto{A B, B C, A D} E.g.:on LHS:{A B, B C, AC D} can be simplifiedto{A B, B C, A D} Intuitively, a canonical cover of F is a “minimal” set of functionaldependencies equivalent to F, having no redundant dependencies orredundant parts of dependenciesDatabase System Concepts - 5th Edition, July 28, 2005.7.33 Silberschatz, Korth and Sudarshan

Extraneous Attributes Consider a set F of functional dependencies and the functionaldependency α β in F.zAttribute A is extraneous in α if A αand F logically implies (F – {α β}) {(α – A) β}.zAttribute A is extraneous in β if A βand the set of functional dependencies(F – {α β}) {α (β – A)} logically implies F. Note: implication in the opposite direction is trivial in each of thecases above, since a “stronger” functional dependency alwaysimplies a weaker one Example: Given F {A C, AB C }zB is extraneous in AB C because {A C, AB C} logicallyimplies A C (I.e. the result of dropping B from AB C). Example: Given F {A C, AB CD}zC is extraneous in AB CD since AB C can be inferred evenafter deleting CDatabase System Concepts - 5th Edition, July 28, 2005.7.34 Silberschatz, Korth and Sudarshan

Testing if an Attribute is Extraneous Consider a set F of functional dependencies and the functionaldependency α β in F. To test if attribute A α is extraneous in α1.2. compute ({α} – A) using the dependencies in Fcheck that ({α} – A) contains A; if it does, A is extraneousTo test if attribute A β is extraneous in β1.2.compute α using only the dependencies inF’ (F – {α β}) {α (β – A)},check that α contains A; if it does, A is extraneousDatabase System Concepts - 5th Edition, July 28, 2005.7.35 Silberschatz, Korth and Sudarshan

Canonical Cover A canonical cover for F is a set of dependencies Fc such thatzF logically implies all dependencies in Fc, andzFc logically implies all dependencies in F, andzNo functional dependency in Fc contains an extraneous attribute, andzEach left side of functional dependency in Fc is unique. To compute a canonical cover for F:repeatUse the union rule to replace any dependencies in Fα1 β1 and α1 β2 with α1 β1 β2Find a functional dependency α β with anextraneous attribute either in α or in βIf an extraneous attribute is found, delete it from α βuntil F does not change Note: Union rule may become applicable after some extraneous attributeshave been deleted, so it has to be re-appliedDatabase System Concepts - 5th Edition, July 28, 2005.7.36 Silberschatz, Korth and Sudarshan

Computing a Canonical Cover R (A, B, C)F {A BCB CA BAB C} Combine A BC and A B into A BCz Set is now {A BC, B C, AB C}A is extraneous in AB CzCheck if the result of deleting A from AB C is implied by the otherdependencies z Yes: in fact, B C is already present!Set is now {A BC, B C}C is extraneous in A BCzCheck if A C is logically implied by A B and the other dependencies Yes: using transitivity on A B and B C.– Can use attribute closure of A in more complex cases The canonical cover is:Database System Concepts - 5th Edition, July 28, 2005.A BB C7.37 Silberschatz, Korth and Sudarshan

Lossless-join Decomposition For the case of R (R1, R2), we require that for all possiblerelations r on schema Rr R1 (r ) R2 (r ) A decomposition of R into R1 and R2 is lossless join if andonly if at least one of the following dependencies is in F :zR1 R 2

Suppose we decompose employee into employee1 (employee_id, employee_name) employee2 (employee_name, telephone_number, start_date) The next slide shows how we lose information -- we cannot reconstruct the original employee re

Related Documents:

Part One: Heir of Ash Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 Chapter 24 Chapter 25 Chapter 26 Chapter 27 Chapter 28 Chapter 29 Chapter 30 .

The Relational Algebra A procedural query language Comprised of relational algebra operations Relational operations: Take one or two relations as input Produce a relation as output Relational operations can be composed together Each operation produces a relation A query is simply a relational algebra expression Six "fundamental" relational operations

TO KILL A MOCKINGBIRD. Contents Dedication Epigraph Part One Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Part Two Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18. Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 Chapter 24 Chapter 25 Chapter 26

relational DBMS (RDBMS) software packages Jukić, Vrbsky, Nestorov – Database Systems Chapter 3 – Slide 2 . Once database requirements are collected and visualized as an ER diagram, the next step in creating a relational database is t\൯ map \ 挀漀渀瘀攀爀琀尩 the ER diagram into a relational schema.\

Keywords: database, query, relational algebra, programming, SQL 1. INTRODUCTION Most commercial database systems are based on the relational data model. Recent editions of database textbooks focus primarily on the relational model. In this dual context, the relational model for data

The Relational Database Model 12 Retrieving Data 15 Advantages of a Relational Database 16 Relational Database Management Systems 18 Beyond the Relational Model 19 What the Future Holds 21 A Final Note 22 Summary 22 Review Questions 24 Chapter

relational database on Amazon EC2 is the ideal scenario for users whose application requires a specific, traditional relational database, or for those users who require a maximum level of control and configurability. Relational Database Management Systems (RDBMS) are some of the most w

DEDICATION PART ONE Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 PART TWO Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 .