Scribd
Upload
176 views

Lending-Schema (Branch-Name, Branch-City, Assets, Customer-Name, Loan-Number, Amount)

This document discusses relational database design and decomposition. It introduces some key concepts: 1. Functional dependencies allow expression of constraints between attributes and help determine if a relation is in "good" form. 2. A decomposition of a relation R into relations R1 and R2 is lossless if either R1 intersect R2 determines R1 or R2. This ensures all information from R is retained. 3. The closure of a set of functional dependencies F, written F+, includes all dependencies logically implied by F using Armstrong's axioms. F+ is used to check if a decomposition satisfies dependencies.

Uploaded by

nisha tiwari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
176 views

Lending-Schema (Branch-Name, Branch-City, Assets, Customer-Name, Loan-Number, Amount)

This document discusses relational database design and decomposition. It introduces some key concepts: 1. Functional dependencies allow expression of constraints between attributes and help determine if a relation is in "good" form. 2. A decomposition of a relation R into relations R1 and R2 is lossless if either R1 intersect R2 determines R1 or R2. This ensures all information from R is retained. 3. The closure of a set of functional dependencies F, written F+, includes all dependencies logically implied by F using Armstrong's axioms. F+ is used to check if a decomposition satisfies dependencies.

Uploaded by

nisha tiwari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

Chapter 7: Relational Database Design. Part 1.

1. Pitfalls in Relational Database Design


. Relational database design requires that we find a “good” collection of
relation schemas. A bad design may lead to
. Repetition of Information.
. Inability to represent certain information.
. Design Goals:
. Avoid redundant data
. Ensure that relationships among attributes are represented
. Facilitate the checking of updates for violation of database
integrity constraints.
.
Example
. Consider the relation schema:
Lending-schema = (branch-name, branch-city, assets, customer-name,
loan-number, amount)

branch-name branch-city assets customer-name loan- amount


number
Downtown Brooklyn 9000000 Jones L-17 1000
Redwood Palo Alto 2100000 Smith L-23 2000
Perryridge Horseneck 1700000 Hayes L-15 1500
Downtown Brooklyn 9000000 Jackson L-14 1500

Problems:
. Redundancy:
. Data for branch-name, branch-city, assets are repeated for each
loan that a branch makes
. Wastes space
. Complicates updating, introducing possibility of inconsistency of
assets value
. Null values
. Cannot store information about a branch if no loans exist
. Can use null values, but they are difficult to handle.

2. Decomposition
. Decompose the relation schema Lending-schema into:
Branch-schema = (branch-name, branch-city,assets)
Loan-info-schema = (customer-name, loan-number,branch-name, amount)
. All attributes of an original schema (R) must appear in the
decomposition (R1, R2):
R = R1 ∪ R2
. Lossless-join decomposition.
For all possible relations r on schema R
r = ∏R1 (r) |x| ∏R2 (r)

3. A Lossy Decomposition. Example.

Problem: How to distinguish?


4. 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 a
set of relations {R1, R2, ..., Rn} such that
. each relation is in good form
. the decomposition is a lossless-join decomposition

5. Review: domain.
Domain is atomic if its elements are considered to be indivisible units
. Examples of non-atomic domains: set of names, composite
attributes
. In relational schema all domains are usually assumed to be atomic
6. First Normal Form
. A relational schema R is in first normal form if the domains of all
attributes of R are atomic
We assume all relations are in first normal form
If a relational schema is in first normal form, can we say that it is a “good”
scheme. No. Let’s go on.

7. Functional Dependencies
. We’ll build our theory on functional dependencies.
. Functional Dependency is a constraint that requires that the value for a
certain set of attributes determines uniquely the value for another set of
attributes.
A functional dependency is a generalization of the notion of a key.

8. Review: keys.
. K is a superkey for relation schema R if and only if K → R
. K is a candidate key for R if and only if
. K → R, and
. for no α ⊂ K, α → R
. Functional dependencies allow us to express constraints that cannot be
expressed using superkeys. Consider the schema:
Loan-info-schema = (customer-name, loan-number, branch-name, amount).
We expect this set of functional dependencies to hold (be satisfied):
loan-number → amount
loan-number → branch-name
but would not expect the following to hold:
loan-number → customer-name
9. Use of Functional Dependencies
. We use functional dependencies to:
. test relations to see if they are legal under a given set of functional
dependencies.
 If a relation r is legal under a set F of functional
dependencies, we say that r satisfies F.
. specify constraints on the set of legal relations
 We say that F holds on R if all legal relations on R satisfy the
set of functional dependencies F.

Note: A specific instance of a relation schema may satisfy a functional


dependency even if the functional dependency does not hold on all legal
instances. For example, a specific instance of Loan-schema may, by chance,
satisfy
loan-number → customer-name

10. Functional Dependencies (Cont.)


. A functional dependency is trivial if it is satisfied by all instances of a
relation
. E.g.
 customer-name, loan-number → customer-name
 customer-name → customer-name
In general, α → β is trivial if β ⊆ α

11. Closure of a Set of Functional Dependencies


. Given a set F of functional dependencies, there are certain other
functional dependencies that are logically implied by F.
. E.g. 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
closure of F.
. We denote the closure of F by F+.
. We can find all of F+ by applying Armstrong’s Axioms:
. if β ⊆ α, then α → β (reflexivity)
. if α → β, then γ α → γ β (augmentation)
. if α → β, and β → γ, then α → γ (transitivity)
. These rules are
. sound (generate only functional dependencies that actually hold)
and
complete (generate all functional dependencies that hold).
. Example
. R = (A, B, C, G, H, I)
F={ A→B
A→C
CG → H
CG → I
B → H}
. some members of F+
. A→H
 by transitivity from A → B and B → H
. AG → I
 by augmenting A → C with G, to get AG → CG
and then transitivity with CG → I
. CG → HI
 from CG → H and CG → I : “union rule” can be inferred
from definition of functional dependencies, or:
(1) augmentation of CG → I to infer CG → CGI,
(2) augmentation of CG → H to infer CGI → HI, and then
(3) transitivity.

12. Closure of Functional Dependencies (Cont.)


. We can further simplify manual computation of F+ by using the
following additional rules.
. If α → β holds and α → γ holds, then α → β γ holds (union)
. If α → β γ holds, then α → β holds and α → γ holds
(decomposition)
. If α → β holds and γ β → δ holds, then α γ → δ holds
(pseudotransitivity)
The above rules can be inferred from Armstrong’s axioms.

13. Look back at our goal: lossless-join decomposition (#4 and #2).
. All attributes of an original schema (R) must appear in the
decomposition (R1, R2):
R = R1 ∪ R2
. Lossless-join decomposition.
For all possible relations r on schema R
r = ∏R1 (r) |x| ∏R2 (r)
14. How do we know that decomposition is a lossless join?
. A decomposition of R into R1 and R2 is lossless join if and only if
. at least one of the following dependencies is in F+:
. R1 ∩ R2 → R1
R1 ∩ R2 → R2
Example: Lossless join.
Decompose the relation schema Lending-schema into:
Branch-schema = (branch-name, branch-city,assets)
Loan-info-schema = (customer-name, loan-number, branch-name, amount)

Example: A Lossy Decomposition (Kim example)


Decompose the relation schema Employee-schema=(employee_id,
employee_name, telephone_number, start_date) into:
Employee-id-schema = (employee_id, employee_name)
Employee-info-schema = (employee_name, telephone_number, start_date)

You might also like