Multivalued dependency

1. Multivalued DependencyMultivalued Dependency
Tamer AbuelataTamer Abuelata

2. IntroductionIntroduction
Goal in Databases:Goal in Databases:
BCNF (Boyce Codd Normal Form)BCNF (Boyce Codd Normal Form)
LosslessnessLosslessness
Dependency preservationDependency preservation

3. Remember…Remember…
Boyce Codd Normal Form (BCNF) eliminates Boyce Codd Normal Form (BCNF) eliminates
all redundancy that can be discovered based on all redundancy that can be discovered based on
functional dependencies.functional dependencies.

4. IssueIssue
Some relation schemas, even though they are in Some relation schemas, even though they are in
BCNF, do not seem to be BCNF, do not seem to be sufficiently sufficiently
normalized.normalized.
They still contain They still contain repetitionsrepetitions

5. Case studyCase study
Consider the bank database schema:Consider the bank database schema:
cust_loan = (cust_loan = (loan_number, cust_idloan_number, cust_id, cust_name, cust_street, cust_city), cust_name, cust_street, cust_city)
This is BCNF because of the functional dependency:This is BCNF because of the functional dependency:
cust_id -> cust_name, cust_street cust_citycust_id -> cust_name, cust_street cust_city
And because cust_id is not a key for cust_loanAnd because cust_id is not a key for cust_loan

6. Case StudyCase Study
But what if some customers have several But what if some customers have several
addresses?addresses?
We no longer wish to enforce the func. We no longer wish to enforce the func.
dependency: dependency: cust_id ->cust_street cust_citycust_id ->cust_street cust_city
But we still want to enforceBut we still want to enforce
cust_id -> cust_namecust_id -> cust_name

7. Case StudyCase Study
Following BCNF decomposition algorithmFollowing BCNF decomposition algorithm
we get:we get:
R1 = (R1 = (cust_idcust_id, cust_name), cust_name)
R2 = (R2 = (loan_number, cust_idloan_number, cust_id, cust_street, cust_city), cust_street, cust_city)
(both in BCNF)(both in BCNF)

8. Case StudyCase Study
The issueThe issue
Despite R2 in BCNF, there is redundancy. We Despite R2 in BCNF, there is redundancy. We
repeat the address of each residence for each repeat the address of each residence for each
loan that the customer has.loan that the customer has.

9. Case StudyCase Study
We can therefore We can therefore decompose furtherdecompose further into: into:
loan_cust_id = (loan_number, cust_id)loan_cust_id = (loan_number, cust_id)
cust_residence = (cust_id, cust_street, cust_city)cust_residence = (cust_id, cust_street, cust_city)
But there is no constraint that lead us to do that.But there is no constraint that lead us to do that.
To deal with this, we need a few form of To deal with this, we need a few form of
constraint: 4NF.constraint: 4NF.

10. 4NF4NF
We can use multivalued dependencies to define We can use multivalued dependencies to define
the the fourth normal formfourth normal form

11. 4NF4NF
A relation schema R is in fourth normal form A relation schema R is in fourth normal form
with respect to a set D of functional and with respect to a set D of functional and
multivalued dependencies if, for all multivlued multivalued dependencies if, for all multivlued
dependencies in D+ of the form A -->-> B at dependencies in D+ of the form A -->-> B at
least one of the following holds:least one of the following holds:
A -->-> B is a trivial multivalued dependencyA -->-> B is a trivial multivalued dependency
A is a superkey for schema RA is a superkey for schema R

12. Multivalued DependencyMultivalued Dependency
Requires that other tuples of a certain form be Requires that other tuples of a certain form be
present in the relation.present in the relation.
Multivalued DependenciesMultivalued Dependencies
The The multivalued dependencymultivalued dependency relates to this  relates to this
problem when more than one multivalued problem when more than one multivalued
attributes exist.attributes exist.
Also referred to as:Also referred to as:
tuple-generating dependencytuple-generating dependency

13. ExampleExample
R relation schema, A and B follow the R relation schema, A and B follow the
multivaluedmultivalued dependencydependency::
A A -->->-->-> B B
The relationship between A and B is independent The relationship between A and B is independent
of the relation between A and R – Bof the relation between A and R – B
If If A A -->-> -->-> B B is satisfied by all relations on R thenis satisfied by all relations on R then
A A -->-> -->-> B B is a trivial multivalued dependencyis a trivial multivalued dependency

14. ExampleExample
Let’s reconsiderLet’s reconsider
R2 = (R2 = (loan_number, cust_idloan_number, cust_id, cust_street, cust_city), cust_street, cust_city)
loan_numberloan_number cust_idcust_id cust_streetcust_streetcust_citycust_city
L-23L-23 99-12399-123 NorthNorth RyeRye
L-23L-23 99-12399-123 MainMain ManchesterManchester
L-93L-93 15-10615-106 LakeLake HorseneckHorseneck

15. ExampleExample
loan_numberloan_number cust_idcust_id cust_streetcust_streetcust_citycust_city
L-23L-23 99-12399-123 NorthNorth RyeRye
L-23L-23 99-12399-123 MainMain ManchesterManchester
L-93L-93 15-10615-106 LakeLake HorseneckHorseneck
We must We must repeat the loan numberrepeat the loan number once for once for each each
addressaddress a customer has and we must a customer has and we must repeat the repeat the
addressaddress for for each loaneach loan a customer has. a customer has.

16. ExampleExample
loan_numberloan_number cust_idcust_id cust_streetcust_streetcust_citycust_city
L-23L-23 99-12399-123 NorthNorth RyeRye
L-23L-23 99-12399-123 MainMain ManchesterManchester
L-93L-93 15-10615-106 LakeLake HorseneckHorseneck
We must We must repeat the loan numberrepeat the loan number once for once for each each
addressaddress a customer has and we must a customer has and we must repeat the repeat the
addressaddress for for each loaneach loan a customer has. a customer has.
This repetition is unnecessary since the relationship between This repetition is unnecessary since the relationship between
a customer and his address is independent of the relationship a customer and his address is independent of the relationship
between that customer and a loan.between that customer and a loan.

17. ExampleExample
Therefore this relation is Therefore this relation is illegalillegal
loan_numberloan_number cust_idcust_id cust_streetcust_street cust_citycust_city
L-23L-23 99-12399-123 NorthNorth RyeRye
L-27L-27 99-12399-123 MainMain ManchesterManchester

18. ExampleExample
Therefore this relation is Therefore this relation is illegalillegal
loan_numberloan_number cust_idcust_id cust_streetcust_street cust_citycust_city
L-23L-23 99-12399-123 NorthNorth RyeRye
L-27L-27 99-12399-123 MainMain ManchesterManchester
To make it legal we should add tuplesTo make it legal we should add tuples
(L23, 99-123, Main, Manchester) and(L23, 99-123, Main, Manchester) and
(L27, 99-123, North, Rye)(L27, 99-123, North, Rye)

19. ExampleExample
loan_numberloan_number cust_idcust_id cust_streetcust_street cust_citycust_city
L-23L-23 99-12399-123 NorthNorth RyeRye
L-27L-27 99-12399-123 MainMain ManchesterManchester
L-23L-23 99-12399-123 MainMain ManchesterManchester
L-27L-27 99-12399-123 NorthNorth RyeRye
Updated table (legal)Updated table (legal)

20. ExampleExample
loan_numberloan_number cust_idcust_id cust_streetcust_street cust_citycust_city
L-23L-23 99-12399-123 NorthNorth RyeRye
L-27L-27 99-12399-123 MainMain ManchesterManchester
L-23L-23 99-12399-123 MainMain ManchesterManchester
L-27L-27 99-12399-123 NorthNorth RyeRye
Updated table (legal)Updated table (legal)
We wantWe want Cust_id Cust_id -->->-->-> cust_street cust_city cust_street cust_city
to holdto hold

21. ConclusionConclusion
We can use multivalued dependenciesWe can use multivalued dependencies
To test relations to determine whether they are To test relations to determine whether they are
legal under a given set of functional and legal under a given set of functional and
multivalued dependenciesmultivalued dependencies
To specify constraints on the set of legal To specify constraints on the set of legal
relationsrelations