Multivalued dependencies and 4NF CTX --------------------------------------------- | COURSE | TEACHER | TEXT | --------------------------------------------- NF2 relation Physics {Prof. Green {Basic Mechanics Prof. Brown} Prin. of Optics} Math {Prof. Green} {Basic Mechanics Vector Analysis} CS {Prof. Brown} {Discrete Math} Normalization 1NF --------------------------------------------- CTX | COURSE | TEACHER | TEXT | --------------------------------------------- Physics Prof. Green Basic Mechanics Physics Prof. Green Prin. of Optics Physics Prof. Brown Basic Mechanics Physics Prof. Brown Prin. of Optics Math Prof. Green Basic Mechanics Math Prof. Green Vector Analysis CS Prof. Brown Discrete Math Properties 1. each course has several teachers COURSE ->> TEACHER 2. each course has several texts COURSE ->> TEXT CTX is in BCNF and 3NF Problem redundancy in the relation results in insertion, update and deletion anormalies Solution decompose the relation into two BCNF relations with only one multivalued dependency ---------------------------- --------------------------- CT | COURSE | TEACHER | CX | COURSE | TEXT | ---------------------------- --------------------------- Physics Prof. Green Physics Basic Mechanics Physics Prof. Brown Physics Prin. of Optics Math Prof. Green Math Basic Mechanics Math Vector Analysis Multivalued dependency: X ->> Y Informally: for each X there is a fixed set of Y values associated with it at any time Formally: Let R be a relation and X and Y be attributes or attribute compositions of R. Let A be the set of all attributes of R Then we say that Y is multivalued dependent on X, X ->> Y iff two tuples t1 and t2 exist in r such that t1.X = t2.X then two tuples t3 and t4 should also exist in R such that t1.X = t2.X = t3.X = t4.X t1.Y = t3.Y and t2.Y = t4.Y t2.(A-XY) = t3.(A-XY) and t1.(A-XY) = t4(A-XY) X Y A-XY --------------------------------------------- CTX | COURSE | TEACHER | TEXT | --------------------------------------------- Physics Prof. Green Basic Mechanics t1 Physics Prof. Green Prin. of Optics t3 Physics Prof. Brown Basic Mechanics t4 Physics Prof. Brown Prin. of Optics t2 Math Prof. Green Basic Mechanics t1 t4 Math Prof. Green Vector Analysis t2 t3 CS Prof. Brown Discrete Math t1 t2 t3 t4 Inference Rules R4: Complementation rule for MVDs {X ->> Y} |= X ->> R - (X union Y) COURSE ->> TEACHER |= COURSE ->> TEXT R5: Augmentation rule for MVDs If X ->> Y and W superset Z then WX ->> YZ special case If X ->> Y, then ZX ->> YZ -------------------------- | COURSE | TEACHER | LOC | -------------------------- Physics Green ME123 Physics Brown ME123 Math Green ME456 COURSE ->> TEACHER |= COURSE,LOC ->> TEACHER,LOC R6: Transitive rule for MVDs X ->> Y, Y ->> Z |= X ->> Z - Y ------------------------- | DEPT | FACULTY | KID | ------------------------- CS John Bob CS John Tom CS John Ann CS Tony Sam ------------------------- DEPT ->> FACULTY FACULTY ->> KID R7: Replication rule for FD and MVD X -> Y |= X ->> Y --------------------- | S# | SNAME | --------------------- S# -> SNAME |= S# ->> SNAME R8: Coalenscence rule for FDs and MVDs If X ->> Y and exists W such that 1) W intersect Y = empty 2) W -> Z 3) Y superset Z, then X -> Z -------------------------- | COURSE | TEACHER | LOC | -------------------------- Physics Green ME123 Physics Brown ME123 Math Green ME456 COURSE ->> TEACHER,LOC, TEACHER,LOC superset LOC | COURSE -> LOC X Y Y Z X Z Disprove a MVD |= Y ->> Z ------------------- | X Y Z | ------------------- | x1 y1 z1 | y1 ->> z1, z2 | x1 y1 z2 | | x2 y1 z3 | y1 ->> z3 ------------------- 4NF: A relation R is in 4NF if for every MVD X ->> Y then all attributes of R other than Y are also functionally dependent on X i.e., only one MVD in the relation CTX and EMP are not in 4NF. CT, CX are EAD, EP are Can we further decompose 4NF relations? Can we decompose relations endlessly? Join Dependencies and 5NF We can decompose a relation into two nonlossly (We can join them back to the original relation) there are relations that cannot be nonloss-decomposed into two but can be decomposed into three or more A relation is n-decomposable if it can be nonloss-decomposed into n relations (projections) but not into m < n relations ----------------------- SPJ | S# | P# | J# | ----------------------- S1 P1 J1 S1 P1 J2 S1 P2 J1 S2 P1 J1 ---------------- --------------- SP | S# | P# | PJ | P# | J# | ---------------- --------------- S1 P1 P1 J1 S1 P2 P1 J2 S2 P1 P2 J1 ----------------------- SP njoin PJ | S# | P# | J# | <> SPJ ----------------------- S1 P1 J1 S1 P1 J2 S1 P2 J1 S2 P1 J1 S2 P1 J2 spurious ---------------- --------------- ------------- SP | S# | P# | PJ | P# | J# | JS | J# | S# | ---------------- --------------- ------------- S1 P1 P1 J1 J1 S1 S1 P2 P1 J2 J2 S1 S2 P1 P2 J1 J1 S2 SP njoin PJ njoin JS = SPJ SPJ is 3-decomposable SPJ = SP njoin PJ njoin JS Join Dependency (JD) Let X, ..., Z be arbitrary subset of attributes of R. Then the relation R satisfies JD, denoted by JD (X, ..., Z) iff it is equal to the join of its projections on X, ..., Z. SPJ satisfies the JD (SP,PJ,JS) 5NF A relation is in 5NF, iff there is no JDs. SPJ is not in 5NF SP, PJ, JS are in 5NF Overview of Normalization theory 1) Relations domain, attributes, primary key, foreign key, integrities, index ... 2) Normalization NF2, 1NF, 2NF, 3NF, BCNF, 4NF, 5NF Functional Dependency (FD) Multivalued Dependency (MVD) Join Dependency (JD) 3) DB Design (done by DBA) ------------- ( real world ) ( application ) ------------- Use E/R model | semantics DBMS v modeling independent ------------- ( Relations ) ------------- Normalization | data DBMS NF2, 1NF, 2NF,3NF, BCNF, 4NF v modeling dependent ------------- Use Relational ( Schema ) model ( in DBMS ) ------------- Object-Relational Databases Other names Nested Relational Model Complex Object Model Object-Relational Model Extend the relational model by providing a richer type (domain) system that supports set and tuple constructors Definition domain a set of values (atomic or non-atomic) relation based on D1 x ... x Dn attribute columns tuple rows attribute value element of the corresponding domain atomic or non-atomic Example kind domain(type) values ------------------------------------------------------ atomic int 123 set {int} {123,234,237} tuple (Street int, Sname char(10)) (12, 'King St') set of tuple {(Street int, Sname char(10))} {(12, 'King St')} A relation (which is also a complex object) ---------------------------------------------------------- Name BDate Children Phones ---------------------------------------------------------- Employee --------------- ----------- | Name Age | --------- Tom |1960 1 10| | ----------- | | 1234 | ----------- | Bob 8 | | 2341 | | Ann 5 | --------- --------------- ---------------------------------------------------------- --------------- ----------- | Name Age | | ----- | Pam |1960 2 25| | ----------- | | 1234 | ----------- | Bob 8 | | 2341 | | Ann 5 | --------- | Sam 7 | --------------- ---------------------------------------------------------- Name -> BDate Name ->> Children Name ->> Phones 4NF -------------- -------------------- ----------- Name CName Age Name Year Month Day Name Phones -------------- -------------------- ----------- Tom Bob 8 Tom 1960 1 10 Tom 1234 Tom Ann 5 Pam 1960 2 25 Tom 2341 Pam Bob 8 ------------------- Pam 1234 Pam Ann 5 Pam 2341 Pam Sam 7 ----------- ------------- Object-relational Model 1. Schema Employee {[Name varchar10, BDate [Year int, Month int, Day int], Children {[Name string,Age int]}, phone {int}]} Composition Hierarchy Employee / / \ \ Name BDate Children Phone / / | \ / \ \ varchar Year Month Day Name Age int / | \ / \ int int int varchar int 2. DDL a) create type create table DDL Examples create type Date_T as object (Year integer, Month integer, Day integer); / create type Child_T as object (Name varchar(10), Age integer); / create type Children_T as table of Child_T; / create type Phones_T as varray(4) of integer; / create table Employee (Name Varchar(10), BDate Date_T, Children Children_T, Phones Phones_T) nested table Children store as Children_tab;