DOC PREVIEW
UW-Milwaukee COMPSCI 557 - Decompositions

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

AnnouncementsFrom last timeDecompositionsExample DecompositionDesirable Properties of DecompositionsExample 1 of Lossy DecompositionExample 2 of Lossy DecompositionA test for lossless decompositionNormalization by Decomposition into BCNFSlide 10What about normalizing to 3NFSummary of Database Design TheoryAnnouncements•Program 3 due Friday•Homework 2 out today, due Mon•Read: Chapter 3From last time•Yes! Any relational schema with two attributes is in BCNF.•The “area” attribute does indeed refer to the size of a lot (eg, in acres)Is lots1A in 3NF? BCNF?Decompositions•Given a relation schema R that is not in 3NF (or perhaps BCNF) decomposition can be used to help fix this problem•Decomposition replaces R with R1,...,RN where –1) attributes of Ri are a subset of the attributes of R–2) each attribute of R is in at least one Ri•Binary decomposition: R  R1,R2•Example Decomposition•Hourly_Emps relation with attributes–(Ssn, name, rating, hourly wage, hours worked)•FD: rating  hourly wage•Hourly_Emps is not in 3NF (why?)•Decompose Hourly_Emps into –R1: (ssn, name, rating)–R2: (rating, hourly wage)•Key question: can we recover any legal row in Hourly_Emps from rows in R1 and R2?Projections of Hourly_EmpsDesirable Properties of Decompositions•Lossless-Join–A decomposition R  R1,R2 has the lossless join property if R can be exactly reconstructed from NATURAL_JOIN(R1,R2)•Dependency Preserving –A decomposition R  R1,R2 is dependency preserving if we can enforce all FDs on R by examining either only R1 or R2 whenever a row is inserted or modified•LJ property is essential, DP is nice•3NF normalization w/ LJ & DP always possible•DP BCNF normalization may not be possibleExample 1 of Lossy DecompositionExample 2 of Lossy Decomposition•Hourly_Emps relation with attributes–(Ssn, name, rating, hourly wage, hours worked)•FD: rating  hourly wage•Decompose Hourly_Emps into –R1: (ssn, rating)–R2: (rating, name, hourly wage)•Why?A test for lossless decomposition•The binary decomposition R with functional dependencies F into R1, R2 is lossless if and only if F contains either:–R1 ∩ R2  R1 or–R1 ∩ R2  R2•That is, attrs common to R1 and R2 must be key of either R1 or R2.•Consequence 1: If FD X  Y holds over R and X ∩ Y is emptythendecomposition of R into (R-Y) and XY is lossless.•Consequence 2: If R  R1, R2 AND R1  R1a, R1b are both lossless then R R1a,R1b,R2 is lossless.Normalization by Decomposition into BCNF•If R is not in BCNF, it is possible to obtain a lossless join decomposition into a collection of BCNF relation schmas•However, there may not by any dependency preserving decompositions into BCNF relationsNormalization by Decomposition into BCNF•Suppose that R is not in BCNF and XA be a FD that violates BCNF1) Decompose R into R-A and XA2) If either R-A or XA is not in BCNF, decompose further by recursive application•In general there may be alternate ways to normalize to BCNF. The theory does not help discriminate among these.What about normalizing to 3NF•An dependency preserving algorithm for normalizing to 3NF exists•Extension of BCNF normalization approach•See section 11.2.3Summary of Database Design Theory•Constructing relation schemas is called DB design•Poor design can lead to insert, update and delete anomalies because of redundancy•Good design reduces redundancy by normalizing all relations to 3NF or BCNF•The theory of functional dependencies plays a major role in DB


View Full Document

UW-Milwaukee COMPSCI 557 - Decompositions

Download Decompositions
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Decompositions and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Decompositions 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?