# Database Design Techniques

**Database Design Techniques**

Generally we can design the database in two different approaches.

**1. Top-Down Design (Analysis) methodology**

It starts with the major entities of their interest, their attributes and their relationships. And then we add other entities and may split these entities into a number of specialized entities and add the relationships between these entities.

**2. Bottom-Up Design**

It starts with a set of attributes. And group these attributes into entities. Then find out the relationship between these entities. Identify the higher-level entities, generalized these entities and locate relationships at this higher level.

# Definition of the three types of anomalies

**Definition of the three types of anomalies:**

**Insertion anomaly **means that that some data can not be inserted in the database. For example we can not add a new course to the database of example-1,unless we insert a student who has taken that course.

**Update anomaly **means we have data redundancy in the database and to make any modification we have to change all copies of the redundant data or else the database will contain incorrect data. For example in our database we have the Course description "Database Concepts" for IS380 appears in both **St-100-Course-taken **and **St-200-Course-taken **tables. To change its description to "New Database Concepts" we have to change it in all places. Indeed one of the purposes of normalization is to eliminate data redundancy in the database.

**Deletion anomaly means **deleting some data cause other information to be lost. For example if student Russell is deleted from **St-100-Course-taken **table we also lose the information that we had a course call IS417 with description System Analysis.

** **

# Functional Dependency (FD)

**Functional Dependency (FD)**

Functional dependency is a constraint between two sets of attributes from the database. **Definition: **A FD denoted by X→ Y between two sets of attributes X and Y that are subsets of R specifies a constraint on the possible tuples that can form a relation state r of R. The constraint is that, for any two tuples t1 and t2 in r that have t1[X] =t2[X], they must also have t1[Y] =t2[Y]. i. e. the values of the Y component of a tuple in r depends on the values of X component or the X component determines the value of Y component.

**Example- **

**1.** The constraint on R states that there cannot be more than one tuple with a given X value in any relation state r(R) ╡ X→ Y for any subset of attributes Y of R.

**2. **If X→ Y in R doesn’t say whether or not Y→ X in R.

A functional dependency FD: is called trivial if Y is a subset of X.

Definition: A functional dependency, denoted by X→Y, between two sets of attributes X and Y that are subsets of the attributes of relation R, specifies that the values in a tuple corresponding to the attributes in Y are uniquely determined by the values corresponding to the attributes in X.

**For example:** the social security number uniquely determines a name; SSN→ Name

Functional dependencies are determined by the semantics of the relation, in general, they cannot be determined by inspection of an instance of the relation. That is, a functional dependency is a constraint and not a property derived from a relation.

# Use of Functional Dependencies

**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.*

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 *may, by chance, satisfy

*amount *→*customer_name.*

*A *functional dependency is trivial if it is satisfied by all instances of a relation.

**Example :**

*customer_name, loan_number*→

*customer_name*

*customer_name*→

*customer_name*

# Inference rules

**Inference rules**

Armstrong's axioms - sound and complete i.e, enable the computation of any functional dependency. Functional dependencies are:

1. Reflexivity - if the B's are a subset of the A's then A → B

2. Augmentation - If A → B, then A, C → B, C.

3. Transitivity - If A → B and B → C then A → C.

*Additional inference rules*

4. Decomposition - If A → B, C then A → B

5. Union - If A → B and A → C then A → B, C

6. Pseudo transitive - If A → B and C, B → D then C, A → D

# Equivalence of sets of functional dependencies

**Equivalence of sets of functional dependencies**

Two functional dependencies S & T are equivalent iff S→ T and T → S.

The dependency {A_1, ..., A_n} → {B_1, ..., B_m} is trivial if the B's are a subset of the A's is nontrivial if at least one of the B's is not among the A's is completely nontrivial if none of the B's is also one of the A's

# Closure (F+)

All dependencies that include F and that can be inferred from F using the above rules are called closure of F denoted by F+.

Algorithm to compute closure

We have to find out whether F╞ X → Y. This is the case when X → Y Є F+

The better method is to generate X+, closure of X under Fand test F╞ X → Y using the first two axioms augmentation and reflexive rules.

**Algorithm**:

Input: A set of FD ‘s F and a set of attributes X.

Output: The closure X+ of X under the FD’s F+.

X+:=X;

Change=true;

While change do

Begin

Change: = False;

For each FD W → Z in F do

Begin

If W Z then do

Begin

X+: = X+UZ;

Change: =True;

End;

End;

End;