Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Database Systems > L5/6: Database Design Theory > Flashcards

L5/6: Database Design Theory Flashcards

1
Q

What is

Design Theory

about?

A

How to represent your data

in such a way that you

avoid Anomalies

caused by data redundancy, null values, etc

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are

Armstrongs 4 Rules

used for?

A

Discovering Functional Dependencies

from Functional Dependencies that are already known

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Armstrong’s Rules

(names only)

A
  • Reduction (trivial)
  • Transitivity
  • Augmentation
  • Split/Combine
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Armstrong’s Rules:

Reduction

A

Given a set of attributes: X, Y, Z

If Y is a subset of X (Y is in X),

Then X is Functionally Dependent on Y

X → Y

This is kind of trivial.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Armstrong’s Rules:

Transitivity

A

Given a set of attributes: X, Y, Z

If X is functionally dependent on Y (X → Y),

and Y is functionally dependent on Z ( Y → Z),

then X is functionally dependent on Z:

X → Y → Z, therefore X → Z

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Armstrong’s Rules:

Augmentation

A

Given a set of attributes: X, Y, Z

If X is functionally dependent on Y (X → Y),

then XZ is functionally dependent on YZ ( XZ → YZ):

X → Y, therefore XZ → YZ for any Z

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Armstrong’s Rules:

Split/Combine

A

Given a set of attributes: X, Y, Z

Combine:

If X is functionally dependent on Y (X → Y),

and X is functionally dependent on Z ( X → Z),

then X is functionally dependent on YZ:

X → Y , and X→Z, therefore X → YZ

Split:

If X is functionally dependent on YZ,(X → YZ),

then X is functionally dependent on Y ( X → Y)

and X is functionally dependent on Z ( X → Z),

X → YZ therefore: X→Y and X → Z

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Good Functional Depenedencies

vs

Bad Functional Depenedencies

A

Good Functional Depenedency:

  • Minimal Redundancy
  • Less possibility of anomalies
  • Example: EmployeeID → Name, Phone

Bad Functional Depenedency:

  • A lot of redundancy
  • May tie unrelated things together, allowing data anomalies
  • Example: Position → PhoneNumber
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Functional Dependencies

as Constraints

A
  • A Functional Dependency will hold on some instances, and will not hold on others
  • If designed as part of the schema, a FD can help define a valid instance
  • Can check if a FD is violated by checking a single instance
  • But cannot prove that a FD exists by checking a single instance
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Using Functional Dependencies

for Database Schema Design:

General Steps

A
  1. Start with some Relational Schema
  2. Determine it’s Functional Dependencies (FDs)
  3. Use the FDs to design a better schema
    • ​​One which minimizes the possibility of anomalies
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Definition:

Closure of a

Set of Attributes

A

Given a set of attributes: {A1, …, An }

and a set of FDs, F

The Closure: {A1, …, An }+

is the set of attributes B such that

{A1, …, An } → B

So, the closure is the set of attributes dependent on attributes of A

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Algorithm for

Computing Attribute Closure

A

closure = x;

repeat until there is no change:

if there is an FD: U → V in F

such that U is a subset of the Closure,

then set closure = closure UNION V

Translation:

If an FD implies another attribute that is not in the closure, add it to the closure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Types of Anomalies

A
  • Update Anomaly
  • Deletion Anomaly
  • Insertion Anomaly
  • Redundancy
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Anomaly Types:

Update Anomaly

A

Updating one tuple causes inconsistent data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Anomaly Types:

Deletion Anomaly

A

Deleting one kind of information makes you lose another

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Anomaly Types:

Insertion Anomaly

A

Storing one kind of info depends on storing another

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Anomaly Types:

Redundancy

A

Storage of multiple instances

of redundant information

18
Q

What is a

Functional Dependency (FD) ?

A
  • An Integrity Constraint
    • not explicity expressed in the E/R diagram
  • Occurs when one attribute in a relation uniquely determines another attribute
    • Two attributes always occur in the same pair
    • Example: classroom and course
  • A → B
    • If A, then B
19
Q

Superkeys

and

Keys

A

Superkey

a set of attributes {A1, …, An} such that

for any other attribute B in a relation R,

{A1, …, An } → B

  • All attributes are functionally dependent by a superkey
  • A Key is a minimal superkey,
    • no subset of the key is a superkey
20
Q

Steps for finding

Keys and Superkeys

A

For each set of attributes X:

  1. Compute X+ (The Closure)
  2. If X+ = the set of all attributes, then X is a Superkey
  3. If X is minimal, then X is a Key
21
Q

Functional Dependency:

Formal Definition

A

Let A, B be sets of attributes

We write A → B, or say “A functionally determines B”

If, for any tuples t1 and t2 :

t1[A] = t2[A] implies t1[B] = t2[B]

We call A → B a Functional Dependency

22
Q

First Normal Form

(1NF)

A

A Relation is in First Normal Form (1NF) if:

Every field contains only Atomic Values

(No lists or sets)

This is an implicit requirement in the Relational Model.

Pretty simple: One column, one value

23
Q

Second Normal Form (2NF)

A

A Relation R is in Second Normal Form (2NF) if:

Every non-key attribute in R is has Full Funtional Dependency on the Candidate Key of R

A non-2NF schema can be decomposed to 2NF

24
Q

Full Functional Dependency

vs

Partial Functional Dependency

A

X → Y is a:

Full Functional Dependency

if removing attribute A from X makes X → Y not hold

Partial Functional Dependency

if after removing attribute A from X,

X → Y still holds

25
Q

Decomposing a

Non-2NF Schema

to 2NF

A

To be in Second Normal Form, all attributes must be Fully Dependent on the Candidate Key

Steps:

  1. Identify which attributes are not Fully Dependent on a key
  2. Seperate into tables that are Fully Dependent
26
Q

Decompose the following non-2NF schema:

Employee(ssn, pno, hours, ename, plocation)

into 2NF

A
  1. Identify candidate key: (ssn, pno)
  2. Identify Full Dependencies:
  • (ssn, pno) → (hours, ename, plocation)
  • ssn → ename
  • pno → plocation
  1. Split into other tables;
  • T1(ssn, pno, hours)
  • T2(ssn, ename)
  • T3(pno, plocation)
27
Q

Third Normal Form

(3NF)

A

A Relation R, with Functional Dependencies F,

is in 3NF if:

For all Dependencies X→A in the Closure F+ :

  1. A is a part of X (trivial FD)
  2. X contains a key for R (X is a superkey) or
  3. A is part of some key for R

R should not have a non-key attribute that is functionally determined by another non-key attribute

28
Q

Normal Forms:

1NF, 2NF, 3NF Summaries

A
  • 1NF
    • Remove non-atomic values
  • 2NF
    • Remove partial dependencies
  • 3NF
    • Remove transitive dependencies
29
Q

First Normal Form (1NF):

  • Test
  • Remedy
A

Test

Should NOT have non-atomic values

Remedy

Create relations for each non-atomic attribute

30
Q

Second Normal Form( 2NF):

  • Test
  • Remedy
A

Test

No non-key attributes are functional dependencies on just a part of primary key

Remedy

Decompose and create a new relation for each partial dependency

31
Q

Third Normal Form (3NF):

  • Test
  • Remedy
A

Test

Should NOT have non-key attribute FD by another non-key attribute

Remedy

Decompose, create relation including non-key attributes that are functionally dependent on other non-keys

32
Q

Boyce-Codd Normal Form (BCNF)

A

A Relation R is in BCNF if:

For all Functional Dependencies(X→A) in the Closure(F+):

  • A is part of X (trivial FD)
  • X contains a key for R, X is a superkey

Intuitively:

The only non-trivial dependencies are those in which a key determines some attributes.

Each tuple can be seen as an entity or relationship, identified by a key and described by attributes.

33
Q

BCNF:

Relation Diagram

A

*Need an image

Each attribute is exclusively functionally dependent on the key

34
Q

Motivation for

decomposing data into BCNF

A
  • Redundancies in data can lead to data anomalies
    • Bad functional dependencies can be a factor
  • We want to detect and remove redundancies
  • Sometimes, decomposition can lead to subtle and unwanted effects
35
Q

Decomposition:

Two Types

A
  • Lossless/Lossless-Join
  • Dependency Preserving
36
Q

Decomposition:

Checks

A

It is important to check that a decomposition doesn’t introduce new problems

Checks:

Good decomposition should allow us to:

  • Recover the original relation
  • Check integrity constraints efficiently
37
Q

Decompositions:

  • Basic Structure
  • Projections
A

For an original relation:

R( [key attributes] , [Attr. Set A] , [Attr. Set B] )

R can be decomposed into two new relations, each using the Key of R as their own Keys:

R1( [key attributes], [Attr. Set A] )

R2( [key attributes], [Attr. Set B] )

These are called the Projections of R

38
Q

Dependency Preservation

during Decomposition

A

A Functional Dependency(FD) X→Y in a relation R,

is Preserved in a projection Rn if:

Rn contains all of the attributes of X and Y

A FD can therefore be checked by accessing only R

39
Q

True or False:

BNCF Decomposition is

always lossless

A

TRUE!

All Functional Dependencies in a BNCF table are already dependent on the superkey

This means that all tables would have the same key:

R = R1 Join R2 Join … Join Rn

40
Q

Dependency Checking

after

Decomposition

A

A decomposition is Dependency Preserving if:

the set of new Functional Dependencies, F++

is the same as the set F+ from the original table

F++ = F+

41
Q

BCNF

Normalization

Algorithm

A

Starting with a relation R, not in BCNF:

Let X in R,A be a single attribute in R,

and X → A be an FD that causes a violation of BCNF

Decompose into R-A and XA

If either R-A or XA is not in BCNF, decompose those Relations

42
Q

Functional Dependencies:

Useful Rules derived from

Armstrong’s Axioms

A
  • Decomposition
    • If (A1, …, An) -> (B1, …, Bm) then
      • (A1, …, An) -> B1 , (A1, …, An)
      • (A1, …, An) -> B2 , (A1, …, An)
      • etc
  • Union
    • If (A1, …, An) -> B1, …, (A1, …, An)-> Bm
    • then (A1, …, An) -> (B1, …, Bm)
  • Pseudotransitivity
    • If (A1, …, An) -> (B1, …, Bm)
    • and (B1, …, Bm), (C1, …, Ck) -> (D1, …, Dp)
    • then
    • (A1, …, An)(C1, …, Ck) -> (D1, …, Dp)

Database Systems (18 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions