CS计算机代考程序代写 Functional Dependencies database flex algorithm 1/54

1/54

Week 5 Workshop

Alice: Your model reduces the most interesting information
to something flat and boring.

Vittorio: You’re right, and this causes a lot of problems.

Sergio: Designing the schema for a complex application is
tough, and it is easy to make mistakes when updat-
ing a database.

Riccardo: Also, the system knows so little about the data that it
is hard to obtain good performance.

Alice: Are you telling me that the model is bad?

Vittorio: No, wait, we are going to fix it!

(Foundations of Databases, S. Abiteboul, R. Hull, V. Vianu, Addison-Wesley, 1995)

2/54

Housekeeping

1 Assignment 1 (SQL) (due 11:59pm, 3 Sep 2021)

Which directors have collaborated with at least two different writers?
(Clarification: two different writers, not including director themselves)
Among those directors who have never won any director award, who
directed the largest number of movies? (Clarification: Among . . . )
Pay attention to which attributes you need to list, whether you need to
order the tuples, syntax issues,etc. (Partial marks may be awarded)
Do not wait until the last minute to check/submit your solution.
(Refer to the instructions in the assignment specification.)

2 More consultation hours in Week 6

Aug 30 (Mon) 2-3 pm
Aug 31 (Tue) 2-3 pm
Sep 1 (Wed) 8-9 pm

2/54

Housekeeping

1 Assignment 1 (SQL) (due 11:59pm, 3 Sep 2021)

Which directors have collaborated with at least two different writers?
(Clarification: two different writers, not including director themselves)

Among those directors who have never won any director award, who
directed the largest number of movies? (Clarification: Among . . . )
Pay attention to which attributes you need to list, whether you need to
order the tuples, syntax issues,etc. (Partial marks may be awarded)
Do not wait until the last minute to check/submit your solution.
(Refer to the instructions in the assignment specification.)

2 More consultation hours in Week 6

Aug 30 (Mon) 2-3 pm
Aug 31 (Tue) 2-3 pm
Sep 1 (Wed) 8-9 pm

2/54

Housekeeping

1 Assignment 1 (SQL) (due 11:59pm, 3 Sep 2021)

Pay attention to which attributes you need to list, whether you need to
order the tuples, syntax issues,etc. (Partial marks may be awarded)
Do not wait until the last minute to check/submit your solution.
(Refer to the instructions in the assignment specification.)

2 More consultation hours in Week 6

Aug 30 (Mon) 2-3 pm
Aug 31 (Tue) 2-3 pm
Sep 1 (Wed) 8-9 pm

2/54

Housekeeping

1 Assignment 1 (SQL) (due 11:59pm, 3 Sep 2021)

2 More consultation hours in Week 6

Aug 30 (Mon) 2-3 pm
Aug 31 (Tue) 2-3 pm
Sep 1 (Wed) 8-9 pm

2/54

Housekeeping

1 Assignment 1 (SQL) (due 11:59pm, 3 Sep 2021)

2 More consultation hours in Week 6

Aug 30 (Mon) 2-3 pm
Aug 31 (Tue) 2-3 pm
Sep 1 (Wed) 8-9 pm

2/54

Housekeeping

1 Assignment 1 (SQL) (due 11:59pm, 3 Sep 2021)

2 More consultation hours in Week 6

Aug 30 (Mon) 2-3 pm
Aug 31 (Tue) 2-3 pm
Sep 1 (Wed) 8-9 pm

3/54

Update Anomalies

What could happen to insert, delete and update operations?

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1989 COMP2400 2010 S2 6
Tom 123456 25/01/1989 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

Insertion anomalies: If inserting a new course COMP3000, then …
(i.e., cannot insert NULL values into Course because of the entity
integrity constraint).
Deletion anomalies: If deleting the enrolled course COMP2400 of
Fran, then … the personal information of Fran, such as DoB, will be
lost as well.
Modification anomalies: If changing the DoB of Michael, then …
update every tuple that records the DoB of this student.

3/54

Update Anomalies

What could happen to insert, delete and update operations?

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1989 COMP2400 2010 S2 6
Tom 123456 25/01/1989 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

Insertion anomalies: If inserting a new course COMP3000, then …

(i.e., cannot insert NULL values into Course because of the entity
integrity constraint).
Deletion anomalies: If deleting the enrolled course COMP2400 of
Fran, then … the personal information of Fran, such as DoB, will be
lost as well.
Modification anomalies: If changing the DoB of Michael, then …
update every tuple that records the DoB of this student.

3/54

Update Anomalies

What could happen to insert, delete and update operations?

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1989 COMP2400 2010 S2 6
Tom 123456 25/01/1989 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

Insertion anomalies: If inserting a new course COMP3000, then …
(i.e., cannot insert NULL values into Course because of the entity
integrity constraint).

Deletion anomalies: If deleting the enrolled course COMP2400 of
Fran, then … the personal information of Fran, such as DoB, will be
lost as well.
Modification anomalies: If changing the DoB of Michael, then …
update every tuple that records the DoB of this student.

3/54

Update Anomalies

What could happen to insert, delete and update operations?

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1989 COMP2400 2010 S2 6
Tom 123456 25/01/1989 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

the personal information of Fran, such as DoB, will be
lost as well.
Modification anomalies: If changing the DoB of Michael, then …
update every tuple that records the DoB of this student.

3/54

Update Anomalies

What could happen to insert, delete and update operations?

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1989 COMP2400 2010 S2 6
Tom 123456 25/01/1989 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

Modification anomalies: If changing the DoB of Michael, then …
update every tuple that records the DoB of this student.

3/54

Update Anomalies

What could happen to insert, delete and update operations?

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1989 COMP2400 2010 S2 6
Tom 123456 25/01/1989 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

update every tuple that records the DoB of this student.

3/54

Update Anomalies

What could happen to insert, delete and update operations?

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1989 COMP2400 2010 S2 6
Tom 123456 25/01/1989 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

4/54

Update Anomalies?
ENROLMENT

Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1988 COMP2400 2010 S2 6
Tom 123456 25/01/1988 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

⇓
STUDENT

Name StudentID DoB
Tom 123456 25/01/1988

Michael 123458 21/04/1985
Fran 123457 11/09/1987

COURSE
CourseNo Unit

COMP2400 6
COMP8740 12

ENROL
StudentID CourseNo Semester
123456 COMP2400 2010 S2
123456 COMP8740 2011 S2
123458 COMP2400 2009 S2
123458 COMP8740 2011 S2
123457 COMP2400 2009 S2

5/54

Why Functional Dependencies?

FDs tell us “relationship between and among attributes”!

FDs are developed to define the goodness and badness of (relational)
database design in a formal way.

Top down: start with a relation schema and FDs, and produce smaller
relation schemas in certain normal form (called normalisation).

Bottom up: start with attributes and FDs, and produce relation
schemas (not popular in practice).

6/54

What is “Functional” about Functional Dependencies?

The notion of functional dependency is very close to the notion of function.

A (total) function f : X → Y describes a relationship between two sets X
and Y such that each element of X is mapped to a unique element of Y .

X Y

Determinant Dependant

Functional
dependency

Function

Domain Codomain

7/54

What is “Functional” about Functional Dependencies?

A (total) function f : X → Y describes a relationship between two sets X
and Y such that each element of X is mapped to a unique element of Y .

Exercise: which of them represent a function?

Add another slide (Optional): Before slide 14, we might say that the concept of functional
dependencies stems from the uniqueness property of the definition of function

Recall that a relation f:X -> Y is a function if any two values at the first position of the tuples of
the relation f are different. In other words if x1=x2 then f(x1) = f(x2)

Exercise: Which of the following diagrams satisfy the uniqueness property?

Which one of them satisfy uniqueness property?

Slide 14: Consider adding in the second dot point: In other words if t1[X] = t2[X] then we must
have t1[Y] = t2[Y]. The following is also equivalent to the following:

Add another slide

X is said to be the determinant and Y as the dependent of the functional dependent.

I think you can add the following diagrammatical examples:

Again consider

Here

Answer: The ones at the bottom.

7/54

What is “Functional” about Functional Dependencies?

A (total) function f : X → Y describes a relationship between two sets X
and Y such that each element of X is mapped to a unique element of Y .

Exercise: which of them represent a function?

Add another slide (Optional): Before slide 14, we might say that the concept of functional
dependencies stems from the uniqueness property of the definition of function

Recall that a relation f:X -> Y is a function if any two values at the first position of the tuples of
the relation f are different. In other words if x1=x2 then f(x1) = f(x2)

Exercise: Which of the following diagrams satisfy the uniqueness property?

Which one of them satisfy uniqueness property?

Slide 14: Consider adding in the second dot point: In other words if t1[X] = t2[X] then we must
have t1[Y] = t2[Y]. The following is also equivalent to the following:

Add another slide

X is said to be the determinant and Y as the dependent of the functional dependent.

I think you can add the following diagrammatical examples:

Again consider

Here

Answer: The ones at the bottom.

8/54

Functions vs Functional Dependencies

X Y

Determinant Dependant

Functional
dependency

Function

Domain Codomain

9/54

Functions vs Functional Dependencies

f (x) = x2

x f (x)
1 1
2 4
3 9
4 16
5 25
6 36
. . . . . .

X → f (x)

9/54

Functions vs Functional Dependencies

f (x) = x2

x f (x)
1 1
2 4
3 9
4 16
5 25
6 36
. . . . . .

X → f (x)

9/54

Functions vs Functional Dependencies

f (x) = x2

x f (x)
1 1
2 4
3 9
4 16
5 25
6 36
. . . . . .

X → f (x)

10/54

Formal Definition
Let R be a relation schema.

A FD on R is an expression X → Y with attribute sets X ,Y ⊆ R.
A relation r(R) satisfies X → Y on R if, for any two tuples
t1, t2 ∈ r(R), whenever the tuples t1 and t2 coincide on values of X ,
they also coincide on values of Y .

t1[X ] = t2[X ]
⇓

t1[Y ] = t2[Y ]

A FD is trivial if it can always be satisfied, e.g.,

{A,B} → {A}

{A,B,C} → {A,B,C}

Syntactical convention: (1) Instead of {A,B,C}, we may use ABC. (2)
A,B, . . . for individual attributes and X ,Y , . . . for sets of attributes.

11/54

Exercise – Functional Dependencies

A functional dependency specifies a constraint on the relation schema that
must hold at all times.

Consider the following relation with attributes {A,B,C,D,E}. Do they satisfy
the given FDs?

r(R)
A B C D E
1 2 3 4 5
1 2 2 2 2
1 2 3 2 3
2 2 2 4 4

1 ABC → AB Yes.
2 ABC → D No.
3 E → ABCD Yes.

11/54

Exercise – Functional Dependencies

A functional dependency specifies a constraint on the relation schema that
must hold at all times.

Consider the following relation with attributes {A,B,C,D,E}. Do they satisfy
the given FDs?

r(R)
A B C D E
1 2 3 4 5
1 2 2 2 2
1 2 3 2 3
2 2 2 4 4

1 ABC → AB

Yes.
2 ABC → D No.
3 E → ABCD Yes.

11/54

Exercise – Functional Dependencies

A functional dependency specifies a constraint on the relation schema that
must hold at all times.

Consider the following relation with attributes {A,B,C,D,E}. Do they satisfy
the given FDs?

r(R)
A B C D E
1 2 3 4 5
1 2 2 2 2
1 2 3 2 3
2 2 2 4 4

1 ABC → AB Yes.

2 ABC → D No.
3 E → ABCD Yes.

11/54

Exercise – Functional Dependencies

A functional dependency specifies a constraint on the relation schema that
must hold at all times.

Consider the following relation with attributes {A,B,C,D,E}. Do they satisfy
the given FDs?

r(R)
A B C D E
1 2 3 4 5
1 2 2 2 2
1 2 3 2 3
2 2 2 4 4

1 ABC → AB Yes.
2 ABC → D

No.
3 E → ABCD Yes.

11/54

Exercise – Functional Dependencies

A functional dependency specifies a constraint on the relation schema that
must hold at all times.

Consider the following relation with attributes {A,B,C,D,E}. Do they satisfy
the given FDs?

r(R)
A B C D E
1 2 3 4 5
1 2 2 2 2
1 2 3 2 3
2 2 2 4 4

1 ABC → AB Yes.
2 ABC → D No.

3 E → ABCD Yes.

11/54

Exercise – Functional Dependencies

A functional dependency specifies a constraint on the relation schema that
must hold at all times.

Consider the following relation with attributes {A,B,C,D,E}. Do they satisfy
the given FDs?

r(R)
A B C D E
1 2 3 4 5
1 2 2 2 2
1 2 3 2 3
2 2 2 4 4

1 ABC → AB Yes.
2 ABC → D No.
3 E → ABCD

Yes.

11/54

Exercise – Functional Dependencies

A functional dependency specifies a constraint on the relation schema that
must hold at all times.

Consider the following relation with attributes {A,B,C,D,E}. Do they satisfy
the given FDs?

r(R)
A B C D E
1 2 3 4 5
1 2 2 2 2
1 2 3 2 3
2 2 2 4 4

1 ABC → AB Yes.
2 ABC → D No.
3 E → ABCD Yes.

11/54

Exercise – Functional Dependencies

A functional dependency specifies a constraint on the relation schema that
must hold at all times.

Consider the following relation with attributes {A,B,C,D,E}. Do they satisfy
the given FDs?

r(R)
A B C D E
1 2 3 4 5
1 2 2 2 2
1 2 3 2 3
2 2 2 4 4

1 ABC → AB Yes.
2 ABC → D No.
3 E → ABCD Yes.

12/54

How to Identify FDs in General?

A functional dependency specifies a constraint on the relation schema that
must hold at all times.

In real-life applications, we often use the following approaches:

(1) Analyse data requirements
Can be provided in the form of discussion with application users
and/or data requirement specifications.

(2) Analyse sample data
Useful when application users are unavailable for consultation and/or
the document is incomplete.

12/54

How to Identify FDs in General?

A functional dependency specifies a constraint on the relation schema that
must hold at all times.

In real-life applications, we often use the following approaches:

(1) Analyse data requirements
Can be provided in the form of discussion with application users
and/or data requirement specifications.

(2) Analyse sample data
Useful when application users are unavailable for consultation and/or
the document is incomplete.

12/54

How to Identify FDs in General?

A functional dependency specifies a constraint on the relation schema that
must hold at all times.

In real-life applications, we often use the following approaches:

(1) Analyse data requirements
Can be provided in the form of discussion with application users
and/or data requirement specifications.

(2) Analyse sample data
Useful when application users are unavailable for consultation and/or
the document is incomplete.

12/54

How to Identify FDs in General?

A functional dependency specifies a constraint on the relation schema that
must hold at all times.

In real-life applications, we often use the following approaches:

(1) Analyse data requirements
Can be provided in the form of discussion with application users
and/or data requirement specifications.

(2) Analyse sample data
Useful when application users are unavailable for consultation and/or
the document is incomplete.

13/54

(1) Analyse Data Requirements and FD Diagram

Some of the (minimal?) dependencies in the above relational schema are shown in the following
Dependency Diagram:

Customer_No Property_No CName RentStart Owner_No OName

Remark: For the ease of reference, we usually label the dependencies as fd1, fd2, fd3 …

Slide 16?

Dependency diagram for the ENROLMENT Relation

Name StudentID DoB CourseNo Semester Unit

StudentID Name DoB;
CourseNo Unit;
StudentID CourseNo Semester Name DoB Unit

StudentID→ Name, DoB;

CourseNo→ Unit;

StudentID, CourseNo, Semester→ Name, DoB, Unit.

14/54

(2) Analyse Sample Data
Can you find some FDs on ENROLMENT based on the sample data?

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1988 COMP2400 2010 S2 6
Tom 123456 25/01/1988 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

We may have:
{StudentID} → {Name, DoB};
{StudentID, Name} → {DoB};
{Name} → {StudentID} ×;
…… Limitations:

(1) Sample data needs to be a true representa-
tion of all possible values in the database.
(2) Do we need all FDs?

14/54

(2) Analyse Sample Data
Can you find some FDs on ENROLMENT based on the sample data?

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1988 COMP2400 2010 S2 6
Tom 123456 25/01/1988 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

We may have:
{StudentID} → {Name, DoB};
{StudentID, Name} → {DoB};
{Name} → {StudentID} ×;
…… Limitations:

(1) Sample data needs to be a true representa-
tion of all possible values in the database.
(2) Do we need all FDs?

14/54

(2) Analyse Sample Data
Can you find some FDs on ENROLMENT based on the sample data?

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1988 COMP2400 2010 S2 6
Tom 123456 25/01/1988 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

We may have:

{StudentID} → {Name, DoB};
{StudentID, Name} → {DoB};
{Name} → {StudentID} ×;
…… Limitations:

(1) Sample data needs to be a true representa-
tion of all possible values in the database.
(2) Do we need all FDs?

14/54

(2) Analyse Sample Data
Can you find some FDs on ENROLMENT based on the sample data?

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1988 COMP2400 2010 S2 6
Tom 123456 25/01/1988 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

We may have:
{StudentID} → {Name, DoB};

{StudentID, Name} → {DoB};
{Name} → {StudentID} ×;
…… Limitations:

(1) Sample data needs to be a true representa-
tion of all possible values in the database.
(2) Do we need all FDs?

14/54

(2) Analyse Sample Data
Can you find some FDs on ENROLMENT based on the sample data?

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1988 COMP2400 2010 S2 6
Tom 123456 25/01/1988 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

We may have:
{StudentID} → {Name, DoB};
{StudentID, Name} → {DoB};

{Name} → {StudentID} ×;
…… Limitations:

(1) Sample data needs to be a true representa-
tion of all possible values in the database.
(2) Do we need all FDs?

14/54

(2) Analyse Sample Data
Can you find some FDs on ENROLMENT based on the sample data?

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1988 COMP2400 2010 S2 6
Tom 123456 25/01/1988 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

We may have:
{StudentID} → {Name, DoB};
{StudentID, Name} → {DoB};
{Name} → {StudentID} ×;
……

Limitations:
(1) Sample data needs to be a true representa-
tion of all possible values in the database.
(2) Do we need all FDs?

14/54

(2) Analyse Sample Data
Can you find some FDs on ENROLMENT based on the sample data?

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1988 COMP2400 2010 S2 6
Tom 123456 25/01/1988 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

We may have:
{StudentID} → {Name, DoB};
{StudentID, Name} → {DoB};
{Name} → {StudentID} ×;
…… Limitations:

(1) Sample data needs to be a true representa-
tion of all possible values in the database.
(2) Do we need all FDs?

15/54

Inference?

To design a good database, we need to consider all possible FDs.

Example:

If {StudentID} → {ProjectNo} and {ProjectNo} → {Supervisor} , we

can infer {StudentID} → {Supervisor} .

If each student works on one project and each project has one supervisor,
then each student must have one project supervisor.

Can we systematically infer all possible FDs?

15/54

Inference?

To design a good database, we need to consider all possible FDs.

Example:

If {StudentID} → {ProjectNo} and {ProjectNo} → {Supervisor} , we

can infer {StudentID} → {Supervisor} .

If each student works on one project and each project has one supervisor,
then each student must have one project supervisor.

Can we systematically infer all possible FDs?

15/54

Inference?

To design a good database, we need to consider all possible FDs.

Example:

If {StudentID} → {ProjectNo} and {ProjectNo} → {Supervisor} , we

can infer {StudentID} → {Supervisor} .

If each student works on one project and each project has one supervisor,
then each student must have one project supervisor.

Can we systematically infer all possible FDs?

16/54

Armstrong’s Inference Rules
(Slides 16-25 will not to be assessed)

The Armstrong’s inference rules consist of the following three rules:

Reflexive rule: XY → Y

Augmentation rule: {X → Y} |= XZ → YZ

Transitive rule: {X → Y ,Y → Z} |= X → Z

We use the notation Σ |= X → Y to denote that X → Y is inferred from
the set Σ of functional dependencies.

17/54

Rule 1 – Reflexive Rule

XY → Y .

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1988 COMP2400 2010 S2 6
Tom 123456 25/01/1988 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

Example:
{StudentID, CourseNo, Semester} → {CourseNo, Semester},
where

X={StudentID};
Y={CourseNo, Semester}.

18/54

Rule 2 – Augmentation Rule

{X → Y} |= XZ → YZ .

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1988 COMP2400 2010 S2 6
Tom 123456 25/01/1988 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

Example:
{{CourseNo} → {Unit}} |={CourseNo, Semester} → {Unit, Semester},

where

X={CourseNo};
Y={Unit};
Z={Semester}.

19/54

Rule 3 – Transitive Rule

{X → Y ,Y → Z} |= X → Z .

ENROLMENT
Name StudentID DoB CourseNo Semester Unit
Tom 123456 25/01/1988 COMP2400 2010 S2 6
Tom 123456 25/01/1988 COMP8740 2011 S2 12

Michael 123458 21/04/1985 COMP2400 2009 S2 6
Michael 123458 21/04/1985 COMP8740 2011 S2 12

Fran 123457 11/09/1987 COMP2400 2009 S2 6

Example: {StudentID, CourseNo} → {CourseNo}, {CourseNo} →
{Unit} |= {StudentID, CourseNo} → {Unit}, where

X={StudentID, CourseNo};

Y={CourseNo};

Z={Unit}.

20/54

Other Derived Rules

From Armstrong’s axioms (i.e., reflexive, augmentation, transitive rules), we
can derive the following rules:

Union rule: If X → Y and X → Z , then X → YZ
Example: If StudentID→ Name and StudentID→ DoB hold, then we
have StudentID→ Name, DoB, where

X=StudentID;
Y=Name;
Z=DoB.

Decomposition rule: If X → YZ , then X → Y and X → Z
Example: If StudentID→ Name, DoB holds, then we have StudentID
→ Name and StudentID→ DoB, where

X=StudentID;
Y=Name;
Z=DoB.

20/54

Other Derived Rules

From Armstrong’s axioms (i.e., reflexive, augmentation, transitive rules), we
can derive the following rules:

Union rule: If X → Y and X → Z , then X → YZ
Example: If StudentID→ Name and StudentID→ DoB hold, then we
have StudentID→ Name, DoB, where

X=StudentID;
Y=Name;
Z=DoB.

Decomposition rule: If X → YZ , then X → Y and X → Z
Example: If StudentID→ Name, DoB holds, then we have StudentID
→ Name and StudentID→ DoB, where

X=StudentID;
Y=Name;
Z=DoB.

20/54

Other Derived Rules

From Armstrong’s axioms (i.e., reflexive, augmentation, transitive rules), we
can derive the following rules:

Union rule: If X → Y and X → Z , then X → YZ
Example: If StudentID→ Name and StudentID→ DoB hold, then we
have StudentID→ Name, DoB, where

X=StudentID;
Y=Name;
Z=DoB.

Decomposition rule: If X → YZ , then X → Y and X → Z
Example: If StudentID→ Name, DoB holds, then we have StudentID
→ Name and StudentID→ DoB, where

X=StudentID;
Y=Name;
Z=DoB.

21/54

Example on Armstrong’s Inference Rules

If each student works on one project and each project has one supervisor,
does each student have one project supervisor?

{{StudentID}→{ProjectNo},
{ProjectNo}→{Supervisor}} |= {StudentID}→{Supervisor}

This can be proven by using the Transitive rule:

{X → Y ,Y → Z} |= X → Z

21/54

Example on Armstrong’s Inference Rules

If each student works on one project and each project has one supervisor,
does each student have one project supervisor?

{{StudentID}→{ProjectNo},
{ProjectNo}→{Supervisor}} |= {StudentID}→{Supervisor}

This can be proven by using the Transitive rule:

{X → Y ,Y → Z} |= X → Z

22/54

Example on Armstrong’s Inference Rules

Can we use the following rules to infer FDs, i.e., are they correct?

(1) {X → Y} |= XZ → YZ

Yes, using the Augmentation rule.

(2) {XZ → YZ} |= X → Y
No. See the counter-example below:

X Y Z
a b c
a c d

(3) {X → Y} |= Y → X
No. See the counter-example below:

X Y
0 2
1 2

22/54

Example on Armstrong’s Inference Rules

Can we use the following rules to infer FDs, i.e., are they correct?

(1) {X → Y} |= XZ → YZ

Yes, using the Augmentation rule.

(2) {XZ → YZ} |= X → Y
No. See the counter-example below:

X Y Z
a b c
a c d

(3) {X → Y} |= Y → X
No. See the counter-example below:

X Y
0 2
1 2

22/54

Example on Armstrong’s Inference Rules

Can we use the following rules to infer FDs, i.e., are they correct?

(1) {X → Y} |= XZ → YZ

Yes, using the Augmentation rule.

(2) {XZ → YZ} |= X → Y

No. See the counter-example below:

X Y Z
a b c
a c d

(3) {X → Y} |= Y → X
No. See the counter-example below:

X Y
0 2
1 2

22/54

Example on Armstrong’s Inference Rules

Can we use the following rules to infer FDs, i.e., are they correct?

(1) {X → Y} |= XZ → YZ

Yes, using the Augmentation rule.

(2) {XZ → YZ} |= X → Y
No. See the counter-example below:

X Y Z
a b c
a c d

(3) {X → Y} |= Y → X
No. See the counter-example below:

X Y
0 2
1 2

22/54

Example on Armstrong’s Inference Rules

Can we use the following rules to infer FDs, i.e., are they correct?

(1) {X → Y} |= XZ → YZ

Yes, using the Augmentation rule.

(2) {XZ → YZ} |= X → Y
No. See the counter-example below:

X Y Z
a b c
a c d

(3) {X → Y} |= Y → X

No. See the counter-example below:

X Y
0 2
1 2

22/54

Example on Armstrong’s Inference Rules

Can we use the following rules to infer FDs, i.e., are they correct?

(1) {X → Y} |= XZ → YZ

Yes, using the Augmentation rule.

(2) {XZ → YZ} |= X → Y
No. See the counter-example below:

X Y Z
a b c
a c d

(3) {X → Y} |= Y → X
No. See the counter-example below:

X Y
0 2
1 2

23/54

Armstrong’s Inference Rules

Two questions:

Are all the FDs inferred using the Armstrong’s inference rules correct?
soundness (you cannot prove anything that is wrong)

Can we use the Armstrong’s inference rules to infer all possible FDs?
completeness (you can prove anything that is right)

Theorem (W. W. Armstrong, 19741)

The Armstrong’s inference rules are both sound and complete.

1
William Ward Armstrong: Dependency Structures of Data Base Relationships, page 580-583. IFIP Congress, 1974.

23/54

Armstrong’s Inference Rules

Two questions:

Are all the FDs inferred using the Armstrong’s inference rules correct?
soundness (you cannot prove anything that is wrong)

Can we use the Armstrong’s inference rules to infer all possible FDs?
completeness (you can prove anything that is right)

Theorem (W. W. Armstrong, 19741)

The Armstrong’s inference rules are both sound and complete.

1
William Ward Armstrong: Dependency Structures of Data Base Relationships, page 580-583. IFIP Congress, 1974.

23/54

Armstrong’s Inference Rules

Two questions:

Are all the FDs inferred using the Armstrong’s inference rules correct?
soundness (you cannot prove anything that is wrong)

Can we use the Armstrong’s inference rules to infer all possible FDs?
completeness (you can prove anything that is right)

Theorem (W. W. Armstrong, 19741)

The Armstrong’s inference rules are both sound and complete.

1
William Ward Armstrong: Dependency Structures of Data Base Relationships, page 580-583. IFIP Congress, 1974.

23/54

Armstrong’s Inference Rules

Two questions:

Are all the FDs inferred using the Armstrong’s inference rules correct?
soundness (you cannot prove anything that is wrong)

Can we use the Armstrong’s inference rules to infer all possible FDs?
completeness (you can prove anything that is right)

Theorem (W. W. Armstrong, 19741)

The Armstrong’s inference rules are both sound and complete.

1
William Ward Armstrong: Dependency Structures of Data Base Relationships, page 580-583. IFIP Congress, 1974.

24/54

Implied Functional Dependencies
We write Σ∗ for all possible FDs implied by Σ.

Σ∗ can be computed using the Armstrong’s inference rules.

Why can we compute Σ∗ using the Armstrong’s inference rules?

Because the Armstrong’s inference rules are both sound and complete.

Nonetheless, computing Σ∗ using the Armstrong’s inference rules is not
efficient.

24/54

Implied Functional Dependencies
We write Σ∗ for all possible FDs implied by Σ.

Σ∗ can be computed using the Armstrong’s inference rules.

Why can we compute Σ∗ using the Armstrong’s inference rules?

Because the Armstrong’s inference rules are both sound and complete.

Nonetheless, computing Σ∗ using the Armstrong’s inference rules is not
efficient.

24/54

Implied Functional Dependencies
We write Σ∗ for all possible FDs implied by Σ.

Σ∗ can be computed using the Armstrong’s inference rules.

Why can we compute Σ∗ using the Armstrong’s inference rules?

Because the Armstrong’s inference rules are both sound and complete.

Nonetheless, computing Σ∗ using the Armstrong’s inference rules is not
efficient.

24/54

Implied Functional Dependencies
We write Σ∗ for all possible FDs implied by Σ.

Σ∗ can be computed using the Armstrong’s inference rules.

Why can we compute Σ∗ using the Armstrong’s inference rules?

Because the Armstrong’s inference rules are both sound and complete.

Nonetheless, computing Σ∗ using the Armstrong’s inference rules is not
efficient.

24/54

Implied Functional Dependencies
We write Σ∗ for all possible FDs implied by Σ.

Σ∗ can be computed using the Armstrong’s inference rules.

Why can we compute Σ∗ using the Armstrong’s inference rules?

Because the Armstrong’s inference rules are both sound and complete.

Nonetheless, computing Σ∗ using the Armstrong’s inference rules is not
efficient.

25/54

Implied Functional Dependencies

Computing Σ∗ using the Armstrong’s inference rules is not efficient.

Example: Consider a relation schema R = {A,B,C,D,E} and a set of FDs
Σ = {AB → CD,B → E ,DE → A}. How can we use the Armstrong rules to
show that DB → A ∈ Σ∗?

How can we derive the proof more efficiently?

25/54

Implied Functional Dependencies

Computing Σ∗ using the Armstrong’s inference rules is not efficient.

Example: Consider a relation schema R = {A,B,C,D,E} and a set of FDs
Σ = {AB → CD,B → E ,DE → A}. How can we use the Armstrong rules to
show that DB → A ∈ Σ∗?

How can we derive the proof more efficiently?

25/54

Implied Functional Dependencies

Computing Σ∗ using the Armstrong’s inference rules is not efficient.

Example: Consider a relation schema R = {A,B,C,D,E} and a set of FDs
Σ = {AB → CD,B → E ,DE → A}. How can we use the Armstrong rules to
show that DB → A ∈ Σ∗?

How can we derive the proof more efficiently?

26/54

Implied Functional Dependencies

Let Σ be a set of FDs. Check whether or not Σ |= X → W holds?

We need to
1 Compute the set of all attributes that are dependent on X , which is

called the closure of X under Σ and is denoted by X+.
2 Σ |= X → W holds iff W ⊆ X+.

Algorithm2

X+ := X ;

repeat until no more change on X+

for each Y → Z ∈ Σ with Y ⊆ X+,
add all the attributes in Z to X+, i.e.,
replace X+ by X+ ∪ Z .

Pushing
out

X
+

2
See Algorithm 15.1 on Page 538 in [Elmasri & Navathe, 7th edition] or Algorithm 1 on Page 555 in [Elmasri &

Navathe, 6th edition]

26/54

Implied Functional Dependencies

Let Σ be a set of FDs. Check whether or not Σ |= X → W holds?
We need to

1 Compute the set of all attributes that are dependent on X , which is
called the closure of X under Σ and is denoted by X+.

2 Σ |= X → W holds iff W ⊆ X+.
Algorithm2

X+ := X ;

repeat until no more change on X+

for each Y → Z ∈ Σ with Y ⊆ X+,
add all the attributes in Z to X+, i.e.,
replace X+ by X+ ∪ Z .

Pushing
out

X
+

2
See Algorithm 15.1 on Page 538 in [Elmasri & Navathe, 7th edition] or Algorithm 1 on Page 555 in [Elmasri &

Navathe, 6th edition]

26/54

Implied Functional Dependencies

Let Σ be a set of FDs. Check whether or not Σ |= X → W holds?
We need to

1 Compute the set of all attributes that are dependent on X , which is
called the closure of X under Σ and is denoted by X+.

2 Σ |= X → W holds iff W ⊆ X+.
Algorithm2

X+ := X ;

repeat until no more change on X+

for each Y → Z ∈ Σ with Y ⊆ X+,
add all the attributes in Z to X+, i.e.,
replace X+ by X+ ∪ Z .

Pushing
out

X
+

2
See Algorithm 15.1 on Page 538 in [Elmasri & Navathe, 7th edition] or Algorithm 1 on Page 555 in [Elmasri &

Navathe, 6th edition]

26/54

Implied Functional Dependencies

Let Σ be a set of FDs. Check whether or not Σ |= X → W holds?
We need to

1 Compute the set of all attributes that are dependent on X , which is
called the closure of X under Σ and is denoted by X+.

2 Σ |= X → W holds iff W ⊆ X+.

Algorithm2

X+ := X ;

repeat until no more change on X+

for each Y → Z ∈ Σ with Y ⊆ X+,
add all the attributes in Z to X+, i.e.,
replace X+ by X+ ∪ Z .

Pushing
out

X
+

2
See Algorithm 15.1 on Page 538 in [Elmasri & Navathe, 7th edition] or Algorithm 1 on Page 555 in [Elmasri &

Navathe, 6th edition]

26/54

Implied Functional Dependencies

Let Σ be a set of FDs. Check whether or not Σ |= X → W holds?
We need to

1 Compute the set of all attributes that are dependent on X , which is
called the closure of X under Σ and is denoted by X+.

2 Σ |= X → W holds iff W ⊆ X+.
Algorithm2

X+ := X ;

repeat until no more change on X+

for each Y → Z ∈ Σ with Y ⊆ X+,
add all the attributes in Z to X+, i.e.,
replace X+ by X+ ∪ Z .

Pushing
out

X
+

2
See Algorithm 15.1 on Page 538 in [Elmasri & Navathe, 7th edition] or Algorithm 1 on Page 555 in [Elmasri &

Navathe, 6th edition]

27/54

Implied Functional Dependencies – Example

Consider a relation schema R = {A,B,C,D,E ,F}, a set of FDs
Σ = {AC → B,B → CD,C → E ,AF → B} on R.

Decide whether or not Σ |= AC → DE holds .

1 We first build the closure of AC:

(AC)+ ⊇ AC initialisation
⊇ ACB using AC → B
⊇ ACBD using B → CD
⊇ ACBDE using C → E
= ACBDE

2 Then we check that DE ⊆ (AC)+. Hence Σ |= AC → DE .
Can you quickly tell whether or not Σ |= AC → EF holds?
Σ |= AC → EF does not hold because EF * (AC)+

27/54

Implied Functional Dependencies – Example

Consider a relation schema R = {A,B,C,D,E ,F}, a set of FDs
Σ = {AC → B,B → CD,C → E ,AF → B} on R.

Decide whether or not Σ |= AC → DE holds .

1 We first build the closure of AC:

(AC)+ ⊇ AC initialisation

⊇ ACB using AC → B
⊇ ACBD using B → CD
⊇ ACBDE using C → E
= ACBDE

2 Then we check that DE ⊆ (AC)+. Hence Σ |= AC → DE .
Can you quickly tell whether or not Σ |= AC → EF holds?
Σ |= AC → EF does not hold because EF * (AC)+

27/54

Implied Functional Dependencies – Example

Consider a relation schema R = {A,B,C,D,E ,F}, a set of FDs
Σ = {AC → B,B → CD,C → E ,AF → B} on R.

Decide whether or not Σ |= AC → DE holds .

1 We first build the closure of AC:

(AC)+ ⊇ AC initialisation
⊇ ACB using AC → B

⊇ ACBD using B → CD
⊇ ACBDE using C → E
= ACBDE

2 Then we check that DE ⊆ (AC)+. Hence Σ |= AC → DE .
Can you quickly tell whether or not Σ |= AC → EF holds?
Σ |= AC → EF does not hold because EF * (AC)+

27/54

Implied Functional Dependencies – Example

Consider a relation schema R = {A,B,C,D,E ,F}, a set of FDs
Σ = {AC → B,B → CD,C → E ,AF → B} on R.

Decide whether or not Σ |= AC → DE holds .

1 We first build the closure of AC:

(AC)+ ⊇ AC initialisation
⊇ ACB using AC → B
⊇ ACBD using B → CD

⊇ ACBDE using C → E
= ACBDE

2 Then we check that DE ⊆ (AC)+. Hence Σ |= AC → DE .
Can you quickly tell whether or not Σ |= AC → EF holds?
Σ |= AC → EF does not hold because EF * (AC)+

27/54

Implied Functional Dependencies – Example

Consider a relation schema R = {A,B,C,D,E ,F}, a set of FDs
Σ = {AC → B,B → CD,C → E ,AF → B} on R.

Decide whether or not Σ |= AC → DE holds .

1 We first build the closure of AC:

(AC)+ ⊇ AC initialisation
⊇ ACB using AC → B
⊇ ACBD using B → CD
⊇ ACBDE using C → E

= ACBDE

2 Then we check that DE ⊆ (AC)+. Hence Σ |= AC → DE .
Can you quickly tell whether or not Σ |= AC → EF holds?
Σ |= AC → EF does not hold because EF * (AC)+

27/54

Implied Functional Dependencies – Example

Consider a relation schema R = {A,B,C,D,E ,F}, a set of FDs
Σ = {AC → B,B → CD,C → E ,AF → B} on R.

Decide whether or not Σ |= AC → DE holds .

1 We first build the closure of AC:

(AC)+ ⊇ AC initialisation
⊇ ACB using AC → B
⊇ ACBD using B → CD
⊇ ACBDE using C → E
= ACBDE

2 Then we check that DE ⊆ (AC)+. Hence Σ |= AC → DE .
Can you quickly tell whether or not Σ |= AC → EF holds?
Σ |= AC → EF does not hold because EF * (AC)+

27/54

Implied Functional Dependencies – Example

Consider a relation schema R = {A,B,C,D,E ,F}, a set of FDs
Σ = {AC → B,B → CD,C → E ,AF → B} on R.

Decide whether or not Σ |= AC → DE holds .

1 We first build the closure of AC:

(AC)+ ⊇ AC initialisation
⊇ ACB using AC → B
⊇ ACBD using B → CD
⊇ ACBDE using C → E
= ACBDE

2 Then we check that DE ⊆ (AC)+. Hence Σ |= AC → DE .

Can you quickly tell whether or not Σ |= AC → EF holds?
Σ |= AC → EF does not hold because EF * (AC)+

27/54

Implied Functional Dependencies – Example

Consider a relation schema R = {A,B,C,D,E ,F}, a set of FDs
Σ = {AC → B,B → CD,C → E ,AF → B} on R.

Decide whether or not Σ |= AC → DE holds .

1 We first build the closure of AC:

(AC)+ ⊇ AC initialisation
⊇ ACB using AC → B
⊇ ACBD using B → CD
⊇ ACBDE using C → E
= ACBDE

2 Then we check that DE ⊆ (AC)+. Hence Σ |= AC → DE .
Can you quickly tell whether or not Σ |= AC → EF holds?

Σ |= AC → EF does not hold because EF * (AC)+

27/54

Implied Functional Dependencies – Example

Consider a relation schema R = {A,B,C,D,E ,F}, a set of FDs
Σ = {AC → B,B → CD,C → E ,AF → B} on R.

Decide whether or not Σ |= AC → DE holds .

1 We first build the closure of AC:

(AC)+ ⊇ AC initialisation
⊇ ACB using AC → B
⊇ ACBD using B → CD
⊇ ACBDE using C → E
= ACBDE

2 Then we check that DE ⊆ (AC)+. Hence Σ |= AC → DE .
Can you quickly tell whether or not Σ |= AC → EF holds?
Σ |= AC → EF does not hold because EF * (AC)+

28/54

Exercise – Implied Functional Dependencies

Consider a relation schema R = {A,B,C,D,E} and a set of functional
dependencies Σ = {A→ C,B → C,CD → E} on R.

Decide whether or not

1 Σ |= AD → CE holds

2 Σ |= BD → AC holds

We build the closure for the set of attributes and check:

1 (AD)+ = (ACD)+ = (ACDE)+ = ACDE and CE ⊆ (AD)+, hence
Σ |= AD → CE .

2 (BD)+ = (BCD)+ = (BCDE)+ = BCDE and AC 6⊆ (BD)+, hence
Σ 6|= BD → AC.

28/54

Exercise – Implied Functional Dependencies

Consider a relation schema R = {A,B,C,D,E} and a set of functional
dependencies Σ = {A→ C,B → C,CD → E} on R.

Decide whether or not

1 Σ |= AD → CE holds

2 Σ |= BD → AC holds

We build the closure for the set of attributes and check:

1 (AD)+ = (ACD)+ = (ACDE)+ = ACDE and CE ⊆ (AD)+, hence
Σ |= AD → CE .

2 (BD)+ = (BCD)+ = (BCDE)+ = BCDE and AC 6⊆ (BD)+, hence
Σ 6|= BD → AC.

29/54

Equivalence of Functional Dependencies

Σ1 and Σ2 are equivalent if Σ∗1= Σ
∗
2 .

Let Σ1 = {X → Y ,Y → Z} and Σ2 = {X → Y ,Y → Z ,X → Z}. Note
Σ1 6= Σ2 but Σ∗1= Σ

∗
2 = {X → Y ,Y → Z ,X → Z} (Σ1 and Σ2 are equivalent)

If Σ1 |= Σ2 and Σ2 |= Σ1, are Σ1 and Σ2 equivalent? Yes.

Questions: Can we find the minimal one among equivalent sets of FDs?

29/54

Equivalence of Functional Dependencies

Σ1 and Σ2 are equivalent if Σ∗1= Σ
∗
2 .

Let Σ1 = {X → Y ,Y → Z} and Σ2 = {X → Y ,Y → Z ,X → Z}. Note
Σ1 6= Σ2 but Σ∗1= Σ

∗
2 = {X → Y ,Y → Z ,X → Z} (Σ1 and Σ2 are equivalent)

If Σ1 |= Σ2 and Σ2 |= Σ1, are Σ1 and Σ2 equivalent? Yes.

Questions: Can we find the minimal one among equivalent sets of FDs?

29/54

Equivalence of Functional Dependencies

Σ1 and Σ2 are equivalent if Σ∗1= Σ
∗
2 .

Let Σ1 = {X → Y ,Y → Z} and Σ2 = {X → Y ,Y → Z ,X → Z}. Note
Σ1 6= Σ2 but Σ∗1= Σ

∗
2 = {X → Y ,Y → Z ,X → Z} (Σ1 and Σ2 are equivalent)

If Σ1 |= Σ2 and Σ2 |= Σ1, are Σ1 and Σ2 equivalent?

Yes.

Questions: Can we find the minimal one among equivalent sets of FDs?

29/54

Equivalence of Functional Dependencies

Σ1 and Σ2 are equivalent if Σ∗1= Σ
∗
2 .

Let Σ1 = {X → Y ,Y → Z} and Σ2 = {X → Y ,Y → Z ,X → Z}. Note
Σ1 6= Σ2 but Σ∗1= Σ

∗
2 = {X → Y ,Y → Z ,X → Z} (Σ1 and Σ2 are equivalent)

If Σ1 |= Σ2 and Σ2 |= Σ1, are Σ1 and Σ2 equivalent? Yes.

Questions: Can we find the minimal one among equivalent sets of FDs?

29/54

Equivalence of Functional Dependencies

Σ1 and Σ2 are equivalent if Σ∗1= Σ
∗
2 .

Let Σ1 = {X → Y ,Y → Z} and Σ2 = {X → Y ,Y → Z ,X → Z}. Note
Σ1 6= Σ2 but Σ∗1= Σ

∗
2 = {X → Y ,Y → Z ,X → Z} (Σ1 and Σ2 are equivalent)

If Σ1 |= Σ2 and Σ2 |= Σ1, are Σ1 and Σ2 equivalent? Yes.

Questions: Can we find the minimal one among equivalent sets of FDs?

30/54

Minimal Cover – The Hard Part!

Let Σ be a set of FDs. A minimal cover Σm of Σ is a set of FDs such that

1 Σm is equivalent to Σ, i.e., start with Σm = Σ;

2 Dependent: each FD in Σm has only a single attribute on its right
hand side, i.e., replace each FD X → {A1, . . . ,Ak} in Σm with
X → A1, . . . ,X → Ak ;

3 Determinant: each FD has as few attributes on the left hand side as
possible, i.e., for each FD X → A in Σm, check each attribute B of X to
see if we can replace X → A with (X − B)→ A in Σm;

4 Remove a FD from Σm if it is redundant.

30/54

Minimal Cover – The Hard Part!

Let Σ be a set of FDs. A minimal cover Σm of Σ is a set of FDs such that

1 Σm is equivalent to Σ, i.e., start with Σm = Σ;

2 Dependent: each FD in Σm has only a single attribute on its right
hand side, i.e., replace each FD X → {A1, . . . ,Ak} in Σm with
X → A1, . . . ,X → Ak ;

4 Remove a FD from Σm if it is redundant.

30/54

Minimal Cover – The Hard Part!

Let Σ be a set of FDs. A minimal cover Σm of Σ is a set of FDs such that

1 Σm is equivalent to Σ, i.e., start with Σm = Σ;

2 Dependent: each FD in Σm has only a single attribute on its right
hand side, i.e., replace each FD X → {A1, . . . ,Ak} in Σm with
X → A1, . . . ,X → Ak ;

4 Remove a FD from Σm if it is redundant.

30/54

Minimal Cover – The Hard Part!

Let Σ be a set of FDs. A minimal cover Σm of Σ is a set of FDs such that

1 Σm is equivalent to Σ, i.e., start with Σm = Σ;

2 Dependent: each FD in Σm has only a single attribute on its right
hand side, i.e., replace each FD X → {A1, . . . ,Ak} in Σm with
X → A1, . . . ,X → Ak ;

4 Remove a FD from Σm if it is redundant.

30/54

Minimal Cover – The Hard Part!

Let Σ be a set of FDs. A minimal cover Σm of Σ is a set of FDs such that

1 Σm is equivalent to Σ, i.e., start with Σm = Σ;

2 Dependent: each FD in Σm has only a single attribute on its right
hand side, i.e., replace each FD X → {A1, . . . ,Ak} in Σm with
X → A1, . . . ,X → Ak ;

4 Remove a FD from Σm if it is redundant.

31/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by A→ D?
Σ = {B → A,D → A,AB→ D}, Σ1 = {B → A,D → A,A→ D}
check whether Σ∗ = Σ∗1? (we have Σ1 |= Σ, but Σ |= Σ1?)
check Σ |= A→ D?

If Σ |= A→ D, then Σ |= Σ1 and Σ1 |= Σ, indicating Σ∗ = Σ∗1 .
If Σ 2 A→ D, then Σ∗ 6= Σ∗1 .

Σ 2 A→ D because D 6⊆ (A)+.
No. AB → D cannot be replaced by A→ D.

31/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by A→ D?
Σ = {B → A,D → A,AB→ D}, Σ1 = {B → A,D → A,A→ D}
check whether Σ∗ = Σ∗1? (we have Σ1 |= Σ, but Σ |= Σ1?)
check Σ |= A→ D?

If Σ |= A→ D, then Σ |= Σ1 and Σ1 |= Σ, indicating Σ∗ = Σ∗1 .
If Σ 2 A→ D, then Σ∗ 6= Σ∗1 .

Σ 2 A→ D because D 6⊆ (A)+.
No. AB → D cannot be replaced by A→ D.

31/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by A→ D?
Σ = {B → A,D → A,AB→ D}, Σ1 = {B → A,D → A,A→ D}
check whether Σ∗ = Σ∗1? (we have Σ1 |= Σ, but Σ |= Σ1?)
check Σ |= A→ D?

If Σ |= A→ D, then Σ |= Σ1 and Σ1 |= Σ, indicating Σ∗ = Σ∗1 .
If Σ 2 A→ D, then Σ∗ 6= Σ∗1 .

Σ 2 A→ D because D 6⊆ (A)+.
No. AB → D cannot be replaced by A→ D.

31/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by A→ D?

Σ = {B → A,D → A,AB→ D}, Σ1 = {B → A,D → A,A→ D}
check whether Σ∗ = Σ∗1? (we have Σ1 |= Σ, but Σ |= Σ1?)
check Σ |= A→ D?

If Σ |= A→ D, then Σ |= Σ1 and Σ1 |= Σ, indicating Σ∗ = Σ∗1 .
If Σ 2 A→ D, then Σ∗ 6= Σ∗1 .

Σ 2 A→ D because D 6⊆ (A)+.
No. AB → D cannot be replaced by A→ D.

31/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by A→ D?
Σ = {B → A,D → A,AB→ D}, Σ1 = {B → A,D → A,A→ D}

check whether Σ∗ = Σ∗1? (we have Σ1 |= Σ, but Σ |= Σ1?)
check Σ |= A→ D?

If Σ |= A→ D, then Σ |= Σ1 and Σ1 |= Σ, indicating Σ∗ = Σ∗1 .
If Σ 2 A→ D, then Σ∗ 6= Σ∗1 .

Σ 2 A→ D because D 6⊆ (A)+.
No. AB → D cannot be replaced by A→ D.

31/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by A→ D?
Σ = {B → A,D → A,AB→ D}, Σ1 = {B → A,D → A,A→ D}
check whether Σ∗ = Σ∗1?

(we have Σ1 |= Σ, but Σ |= Σ1?)
check Σ |= A→ D?

If Σ |= A→ D, then Σ |= Σ1 and Σ1 |= Σ, indicating Σ∗ = Σ∗1 .
If Σ 2 A→ D, then Σ∗ 6= Σ∗1 .

Σ 2 A→ D because D 6⊆ (A)+.
No. AB → D cannot be replaced by A→ D.

31/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by A→ D?
Σ = {B → A,D → A,AB→ D}, Σ1 = {B → A,D → A,A→ D}
check whether Σ∗ = Σ∗1? (we have Σ1 |= Σ, but Σ |= Σ1?)

check Σ |= A→ D?
If Σ |= A→ D, then Σ |= Σ1 and Σ1 |= Σ, indicating Σ∗ = Σ∗1 .
If Σ 2 A→ D, then Σ∗ 6= Σ∗1 .

Σ 2 A→ D because D 6⊆ (A)+.
No. AB → D cannot be replaced by A→ D.

31/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by A→ D?
Σ = {B → A,D → A,AB→ D}, Σ1 = {B → A,D → A,A→ D}
check whether Σ∗ = Σ∗1? (we have Σ1 |= Σ, but Σ |= Σ1?)
check Σ |= A→ D?

If Σ |= A→ D, then Σ |= Σ1 and Σ1 |= Σ, indicating Σ∗ = Σ∗1 .
If Σ 2 A→ D, then Σ∗ 6= Σ∗1 .

Σ 2 A→ D because D 6⊆ (A)+.
No. AB → D cannot be replaced by A→ D.

31/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by A→ D?
Σ = {B → A,D → A,AB→ D}, Σ1 = {B → A,D → A,A→ D}
check whether Σ∗ = Σ∗1? (we have Σ1 |= Σ, but Σ |= Σ1?)
check Σ |= A→ D?

If Σ |= A→ D, then Σ |= Σ1 and Σ1 |= Σ, indicating Σ∗ = Σ∗1 .

If Σ 2 A→ D, then Σ∗ 6= Σ∗1 .
Σ 2 A→ D because D 6⊆ (A)+.

No. AB → D cannot be replaced by A→ D.

31/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by A→ D?
Σ = {B → A,D → A,AB→ D}, Σ1 = {B → A,D → A,A→ D}
check whether Σ∗ = Σ∗1? (we have Σ1 |= Σ, but Σ |= Σ1?)
check Σ |= A→ D?

If Σ |= A→ D, then Σ |= Σ1 and Σ1 |= Σ, indicating Σ∗ = Σ∗1 .
If Σ 2 A→ D, then Σ∗ 6= Σ∗1 .

Σ 2 A→ D because D 6⊆ (A)+.
No. AB → D cannot be replaced by A→ D.

31/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by A→ D?
Σ = {B → A,D → A,AB→ D}, Σ1 = {B → A,D → A,A→ D}
check whether Σ∗ = Σ∗1? (we have Σ1 |= Σ, but Σ |= Σ1?)
check Σ |= A→ D?

If Σ |= A→ D, then Σ |= Σ1 and Σ1 |= Σ, indicating Σ∗ = Σ∗1 .
If Σ 2 A→ D, then Σ∗ 6= Σ∗1 .

Σ 2 A→ D because D 6⊆ (A)+.
No. AB → D cannot be replaced by A→ D.

32/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by B → D?

Σ = {B → A,D → A,AB→ D}, Σ2 = {B → A,D → A,B→ D}
check whether Σ∗ = Σ∗2? (we have Σ2 |= Σ, but Σ |= Σ2?)
check Σ |= B→ D?

If Σ |= B→ D, then Σ |= Σ2 and Σ2 |= Σ, indicating Σ∗ = Σ∗2 .
If Σ 2 B→ D, then Σ∗ 6= Σ∗2

Σ |= B→ D because D ⊆ (B)+.
Yes. AB → D can be replaced by B → D.

32/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by B → D?
Σ = {B → A,D → A,AB→ D}, Σ2 = {B → A,D → A,B→ D}

check whether Σ∗ = Σ∗2? (we have Σ2 |= Σ, but Σ |= Σ2?)
check Σ |= B→ D?

If Σ |= B→ D, then Σ |= Σ2 and Σ2 |= Σ, indicating Σ∗ = Σ∗2 .
If Σ 2 B→ D, then Σ∗ 6= Σ∗2

Σ |= B→ D because D ⊆ (B)+.
Yes. AB → D can be replaced by B → D.

32/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by B → D?
Σ = {B → A,D → A,AB→ D}, Σ2 = {B → A,D → A,B→ D}
check whether Σ∗ = Σ∗2?

(we have Σ2 |= Σ, but Σ |= Σ2?)
check Σ |= B→ D?

If Σ |= B→ D, then Σ |= Σ2 and Σ2 |= Σ, indicating Σ∗ = Σ∗2 .
If Σ 2 B→ D, then Σ∗ 6= Σ∗2

Σ |= B→ D because D ⊆ (B)+.
Yes. AB → D can be replaced by B → D.

32/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by B → D?
Σ = {B → A,D → A,AB→ D}, Σ2 = {B → A,D → A,B→ D}
check whether Σ∗ = Σ∗2?

(we have Σ2 |= Σ, but Σ |= Σ2?)
check Σ |= B→ D?

If Σ |= B→ D, then Σ |= Σ2 and Σ2 |= Σ, indicating Σ∗ = Σ∗2 .
If Σ 2 B→ D, then Σ∗ 6= Σ∗2

Σ |= B→ D because D ⊆ (B)+.
Yes. AB → D can be replaced by B → D.

32/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by B → D?
Σ = {B → A,D → A,AB→ D}, Σ2 = {B → A,D → A,B→ D}
check whether Σ∗ = Σ∗2? (we have Σ2 |= Σ, but Σ |= Σ2?)

check Σ |= B→ D?
If Σ |= B→ D, then Σ |= Σ2 and Σ2 |= Σ, indicating Σ∗ = Σ∗2 .
If Σ 2 B→ D, then Σ∗ 6= Σ∗2

Σ |= B→ D because D ⊆ (B)+.
Yes. AB → D can be replaced by B → D.

32/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by B → D?
Σ = {B → A,D → A,AB→ D}, Σ2 = {B → A,D → A,B→ D}
check whether Σ∗ = Σ∗2? (we have Σ2 |= Σ, but Σ |= Σ2?)
check Σ |= B→ D?

If Σ |= B→ D, then Σ |= Σ2 and Σ2 |= Σ, indicating Σ∗ = Σ∗2 .
If Σ 2 B→ D, then Σ∗ 6= Σ∗2

Σ |= B→ D because D ⊆ (B)+.
Yes. AB → D can be replaced by B → D.

32/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by B → D?
Σ = {B → A,D → A,AB→ D}, Σ2 = {B → A,D → A,B→ D}
check whether Σ∗ = Σ∗2? (we have Σ2 |= Σ, but Σ |= Σ2?)
check Σ |= B→ D?

If Σ |= B→ D, then Σ |= Σ2 and Σ2 |= Σ, indicating Σ∗ = Σ∗2 .

If Σ 2 B→ D, then Σ∗ 6= Σ∗2
Σ |= B→ D because D ⊆ (B)+.

Yes. AB → D can be replaced by B → D.

32/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by B → D?
Σ = {B → A,D → A,AB→ D}, Σ2 = {B → A,D → A,B→ D}
check whether Σ∗ = Σ∗2? (we have Σ2 |= Σ, but Σ |= Σ2?)
check Σ |= B→ D?

If Σ |= B→ D, then Σ |= Σ2 and Σ2 |= Σ, indicating Σ∗ = Σ∗2 .
If Σ 2 B→ D, then Σ∗ 6= Σ∗2

Σ |= B→ D because D ⊆ (B)+.
Yes. AB → D can be replaced by B → D.

32/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 check if AB → D can be replaced by B → D?
Σ = {B → A,D → A,AB→ D}, Σ2 = {B → A,D → A,B→ D}
check whether Σ∗ = Σ∗2? (we have Σ2 |= Σ, but Σ |= Σ2?)
check Σ |= B→ D?

If Σ |= B→ D, then Σ |= Σ2 and Σ2 |= Σ, indicating Σ∗ = Σ∗2 .
If Σ 2 B→ D, then Σ∗ 6= Σ∗2

Σ |= B→ D because D ⊆ (B)+.
Yes. AB → D can be replaced by B → D.

33/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 AB → D can be replaced by B → D;

4 look for a redundant FD in {B → A,D → A,B → D}
check whether B → A is redundant?
B → A is redundant because {D → A,B → D} |= B → A;

Therefore, the minimal cover of Σ is {D → A,B → D}.

33/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 AB → D can be replaced by B → D;

4 look for a redundant FD in {B → A,D → A,B → D}

check whether B → A is redundant?
B → A is redundant because {D → A,B → D} |= B → A;

Therefore, the minimal cover of Σ is {D → A,B → D}.

33/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 AB → D can be replaced by B → D;

4 look for a redundant FD in {B → A,D → A,B → D}
check whether B → A is redundant?

B → A is redundant because {D → A,B → D} |= B → A;

Therefore, the minimal cover of Σ is {D → A,B → D}.

33/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 AB → D can be replaced by B → D;

4 look for a redundant FD in {B → A,D → A,B → D}
check whether B → A is redundant?
B → A is redundant because {D → A,B → D} |= B → A;

Therefore, the minimal cover of Σ is {D → A,B → D}.

33/54

Minimal Cover – Examples

Given the set of FDs Σ = {B → A,D → A,AB → D}, we can compute the
minimal cover of Σ as follows:

1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 AB → D can be replaced by B → D;

4 look for a redundant FD in {B → A,D → A,B → D}
check whether B → A is redundant?
B → A is redundant because {D → A,B → D} |= B → A;

Therefore, the minimal cover of Σ is {D → A,B → D}.

34/54

Minimal Cover
Theorem:

The minimal cover of a set of functional dependencies Σ always
exists but is not necessarily unique.

Examples: Consider the following set of functional dependencies:

Σ = {A→ BC,B → C,B → A,C → AB}

Σ has two different minimal covers:

Σ1 = {A→ B,B → C,C → A}
Σ2 = {A→ C,C → B,B → A}

The algorithm in the previous slide can find one, but not all minimal covers
of a set of functional dependencies Σ.

34/54

Minimal Cover
Theorem:

The minimal cover of a set of functional dependencies Σ always
exists but is not necessarily unique.

Examples: Consider the following set of functional dependencies:

Σ = {A→ BC,B → C,B → A,C → AB}

Σ has two different minimal covers:

Σ1 = {A→ B,B → C,C → A}
Σ2 = {A→ C,C → B,B → A}

The algorithm in the previous slide can find one, but not all minimal covers
of a set of functional dependencies Σ.

34/54

Minimal Cover
Theorem:

The minimal cover of a set of functional dependencies Σ always
exists but is not necessarily unique.

Examples: Consider the following set of functional dependencies:

Σ = {A→ BC,B → C,B → A,C → AB}

Σ has two different minimal covers:

Σ1 = {A→ B,B → C,C → A}
Σ2 = {A→ C,C → B,B → A}

The algorithm in the previous slide can find one, but not all minimal covers
of a set of functional dependencies Σ.

34/54

Minimal Cover
Theorem:

The minimal cover of a set of functional dependencies Σ always
exists but is not necessarily unique.

Examples: Consider the following set of functional dependencies:

Σ = {A→ BC,B → C,B → A,C → AB}

Σ has two different minimal covers:

Σ1 = {A→ B,B → C,C → A}
Σ2 = {A→ C,C → B,B → A}

The algorithm in the previous slide can find one, but not all minimal covers
of a set of functional dependencies Σ.

35/54

Finding Keys

Given a set Σ of FDs on a relation R, the question is:

How can we find all the (candidate) keys of R?

The Primary key

Candidate keys
(keys)

Superkeys

36/54

Finding Keys

Fact: A key K of R always defines a FD K → R.

Algorithm3:

Input: a set Σ of FDs on R.

Output: the set of all keys of R.

for every subset X of the relation R, compute its closure X+

if X+ = R, then X is a superkey.

if no proper subset Y of X with Y+ = R, then X is a key.

A prime attribute is an attribute occurring in a key, and a non-prime
attribute is an attribute that is not a prime attribute.

3
It extends Algorithm 15.2(a) in [Elmasri & Navathe, 7th edition, pp. 542], or Algorithm 2(a) or in Algorithm 2(a) in

[Elmasri & Navathe, 6th edition pp. 558] to finding all keys of R

36/54

Finding Keys

Fact: A key K of R always defines a FD K → R.

Algorithm3:

Input: a set Σ of FDs on R.

Output: the set of all keys of R.

for every subset X of the relation R, compute its closure X+

if X+ = R, then X is a superkey.

if no proper subset Y of X with Y+ = R, then X is a key.

A prime attribute is an attribute occurring in a key, and a non-prime
attribute is an attribute that is not a prime attribute.

3
It extends Algorithm 15.2(a) in [Elmasri & Navathe, 7th edition, pp. 542], or Algorithm 2(a) or in Algorithm 2(a) in

[Elmasri & Navathe, 6th edition pp. 558] to finding all keys of R

36/54

Finding Keys

Fact: A key K of R always defines a FD K → R.

Algorithm3:

Input: a set Σ of FDs on R.

Output: the set of all keys of R.

for every subset X of the relation R, compute its closure X+

if X+ = R, then X is a superkey.

if no proper subset Y of X with Y+ = R, then X is a key.

A prime attribute is an attribute occurring in a key, and a non-prime
attribute is an attribute that is not a prime attribute.

3
It extends Algorithm 15.2(a) in [Elmasri & Navathe, 7th edition, pp. 542], or Algorithm 2(a) or in Algorithm 2(a) in

[Elmasri & Navathe, 6th edition pp. 558] to finding all keys of R

36/54

Finding Keys

Fact: A key K of R always defines a FD K → R.

Algorithm3:

Input: a set Σ of FDs on R.

Output: the set of all keys of R.

for every subset X of the relation R, compute its closure X+

if X+ = R, then X is a superkey.

if no proper subset Y of X with Y+ = R, then X is a key.

A prime attribute is an attribute occurring in a key, and a non-prime
attribute is an attribute that is not a prime attribute.

3
It extends Algorithm 15.2(a) in [Elmasri & Navathe, 7th edition, pp. 542], or Algorithm 2(a) or in Algorithm 2(a) in

[Elmasri & Navathe, 6th edition pp. 558] to finding all keys of R

36/54

Finding Keys

Fact: A key K of R always defines a FD K → R.

Algorithm3:

Input: a set Σ of FDs on R.

Output: the set of all keys of R.

for every subset X of the relation R, compute its closure X+

if X+ = R, then X is a superkey.

if no proper subset Y of X with Y+ = R, then X is a key.

A prime attribute is an attribute occurring in a key, and a non-prime
attribute is an attribute that is not a prime attribute.

3
It extends Algorithm 15.2(a) in [Elmasri & Navathe, 7th edition, pp. 542], or Algorithm 2(a) or in Algorithm 2(a) in

[Elmasri & Navathe, 6th edition pp. 558] to finding all keys of R

36/54

Finding Keys

Fact: A key K of R always defines a FD K → R.

Algorithm3:

Input: a set Σ of FDs on R.

Output: the set of all keys of R.

for every subset X of the relation R, compute its closure X+

if X+ = R, then X is a superkey.

if no proper subset Y of X with Y+ = R, then X is a key.

A prime attribute is an attribute occurring in a key, and a non-prime
attribute is an attribute that is not a prime attribute.

3
It extends Algorithm 15.2(a) in [Elmasri & Navathe, 7th edition, pp. 542], or Algorithm 2(a) or in Algorithm 2(a) in

[Elmasri & Navathe, 6th edition pp. 558] to finding all keys of R

36/54

Finding Keys

Fact: A key K of R always defines a FD K → R.

Algorithm3:

Input: a set Σ of FDs on R.

Output: the set of all keys of R.

for every subset X of the relation R, compute its closure X+

if X+ = R, then X is a superkey.

if no proper subset Y of X with Y+ = R, then X is a key.

A prime attribute is an attribute occurring in a key, and a non-prime
attribute is an attribute that is not a prime attribute.

3
It extends Algorithm 15.2(a) in [Elmasri & Navathe, 7th edition, pp. 542], or Algorithm 2(a) or in Algorithm 2(a) in

[Elmasri & Navathe, 6th edition pp. 558] to finding all keys of R

37/54

Exercises – Keys and Minimal Cover

Consider RENTAL={CustID, CustName, PropertyNo, DateStart, Owner} and the
following set Σ of FDs:

{CustID} → {CustName}

{PropertyNo, StartDate} → {CustID}

{PropertyNo, CustID} → {StartDate}

{CustID, StartDate} → {PropertyNo}

{Owner} → {PropertyNo}

Questions:

1 What are the keys of RENTAL?

2 What is a minimal cover of Σ?

38/54

Exercises – Keys and Minimal Cover

Consider RENTAL={CustID, CustName, PropertyNo, DateStart, Owner} and its
FDs in the abbreviated form as

R={C, N, P, D, O}, and
Σ = {C → N, PD→ C, CP→ D, CD→ P, O→ P}

What are the keys of RENTAL?

Solution: Check (X )+ for every subset of {C, N, P, D, O}.
O never appears in the dependent of any FD, O must be part of each
key.
(O)+ = OP

(CO)+ = CPNDO, (DO)+ = CPNDO . . .

Thus, {CustID, Owner} and {Owner, DateStart} are the keys.

38/54

Exercises – Keys and Minimal Cover

Consider RENTAL={CustID, CustName, PropertyNo, DateStart, Owner} and its
FDs in the abbreviated form as

R={C, N, P, D, O}, and
Σ = {C → N, PD→ C, CP→ D, CD→ P, O→ P}

What are the keys of RENTAL?

Solution: Check (X )+ for every subset of {C, N, P, D, O}.
O never appears in the dependent of any FD, O must be part of each
key.

(O)+ = OP

(CO)+ = CPNDO, (DO)+ = CPNDO . . .

Thus, {CustID, Owner} and {Owner, DateStart} are the keys.

38/54

Exercises – Keys and Minimal Cover

Consider RENTAL={CustID, CustName, PropertyNo, DateStart, Owner} and its
FDs in the abbreviated form as

R={C, N, P, D, O}, and
Σ = {C → N, PD→ C, CP→ D, CD→ P, O→ P}

What are the keys of RENTAL?

Solution: Check (X )+ for every subset of {C, N, P, D, O}.
O never appears in the dependent of any FD, O must be part of each
key.
(O)+ = OP

(CO)+ = CPNDO, (DO)+ = CPNDO . . .

Thus, {CustID, Owner} and {Owner, DateStart} are the keys.

38/54

Exercises – Keys and Minimal Cover

Consider RENTAL={CustID, CustName, PropertyNo, DateStart, Owner} and its
FDs in the abbreviated form as

R={C, N, P, D, O}, and
Σ = {C → N, PD→ C, CP→ D, CD→ P, O→ P}

What are the keys of RENTAL?

Solution: Check (X )+ for every subset of {C, N, P, D, O}.
O never appears in the dependent of any FD, O must be part of each
key.
(O)+ = OP

(CO)+ = CPNDO, (DO)+ = CPNDO . . .

Thus, {CustID, Owner} and {Owner, DateStart} are the keys.

39/54

Exercises – Keys and Minimal Cover

Consider RENTAL={CustID, CustName, PropertyNo, DateStart, Owner} and its
FDs in the abbreviated form as

R={C, N, P, D, O}, and
Σ = {C → N, PD→ C, CP→ D, CD→ P, O→ P}

What is a minimal cover of Σ?

Solution:
1 start from Σ;
2 check whether all the FDs in Σ have only one attribute on the right

hand side (look good);
3 determine if PD→ C, CP→ D and CD→ P have any redundant

attribute on the left hand side (look good);
4 look for a redundant FD in Σ (none of FDs in Σ are redundant);

Therefore, Σ is a minimal cover itself.

39/54

Exercises – Keys and Minimal Cover

Consider RENTAL={CustID, CustName, PropertyNo, DateStart, Owner} and its
FDs in the abbreviated form as

R={C, N, P, D, O}, and
Σ = {C → N, PD→ C, CP→ D, CD→ P, O→ P}

What is a minimal cover of Σ?

Solution:
1 start from Σ;

2 check whether all the FDs in Σ have only one attribute on the right
hand side (look good);

3 determine if PD→ C, CP→ D and CD→ P have any redundant
attribute on the left hand side (look good);

4 look for a redundant FD in Σ (none of FDs in Σ are redundant);

Therefore, Σ is a minimal cover itself.

39/54

Exercises – Keys and Minimal Cover

Consider RENTAL={CustID, CustName, PropertyNo, DateStart, Owner} and its
FDs in the abbreviated form as

R={C, N, P, D, O}, and
Σ = {C → N, PD→ C, CP→ D, CD→ P, O→ P}

What is a minimal cover of Σ?

Solution:
1 start from Σ;
2 check whether all the FDs in Σ have only one attribute on the right

hand side (look good);

3 determine if PD→ C, CP→ D and CD→ P have any redundant
attribute on the left hand side (look good);

4 look for a redundant FD in Σ (none of FDs in Σ are redundant);

Therefore, Σ is a minimal cover itself.

39/54

Exercises – Keys and Minimal Cover

Consider RENTAL={CustID, CustName, PropertyNo, DateStart, Owner} and its
FDs in the abbreviated form as

R={C, N, P, D, O}, and
Σ = {C → N, PD→ C, CP→ D, CD→ P, O→ P}

What is a minimal cover of Σ?

Solution:
1 start from Σ;
2 check whether all the FDs in Σ have only one attribute on the right

hand side (look good);
3 determine if PD→ C, CP→ D and CD→ P have any redundant

attribute on the left hand side (look good);

4 look for a redundant FD in Σ (none of FDs in Σ are redundant);

Therefore, Σ is a minimal cover itself.

39/54

Exercises – Keys and Minimal Cover

Consider RENTAL={CustID, CustName, PropertyNo, DateStart, Owner} and its
FDs in the abbreviated form as

R={C, N, P, D, O}, and
Σ = {C → N, PD→ C, CP→ D, CD→ P, O→ P}

What is a minimal cover of Σ?

Solution:
1 start from Σ;
2 check whether all the FDs in Σ have only one attribute on the right

hand side (look good);
3 determine if PD→ C, CP→ D and CD→ P have any redundant

attribute on the left hand side (look good);
4 look for a redundant FD in Σ (none of FDs in Σ are redundant);

Therefore, Σ is a minimal cover itself.

39/54

Exercises – Keys and Minimal Cover

Consider RENTAL={CustID, CustName, PropertyNo, DateStart, Owner} and its
FDs in the abbreviated form as

R={C, N, P, D, O}, and
Σ = {C → N, PD→ C, CP→ D, CD→ P, O→ P}

What is a minimal cover of Σ?

Solution:
1 start from Σ;
2 check whether all the FDs in Σ have only one attribute on the right

hand side (look good);
3 determine if PD→ C, CP→ D and CD→ P have any redundant

attribute on the left hand side (look good);
4 look for a redundant FD in Σ (none of FDs in Σ are redundant);

Therefore, Σ is a minimal cover itself.

40/54

Accommodation Database

Consider the following:

HOTEL(hotelNo, hotelName, city) with PK {hotelNo}
ROOM(roomNo, hotelNo, type, price) with PK {roomNo, hotelNo}
GUEST(guestNo, guestName, guestAddress) with PK {guestNo}
BOOKING(guestNo, hotelNo, date, roomNo) with PK {?}

We have some requirements on BOOKING:

R1 A booking can be made for one day only.
R2 A guest can make several bookings in a hotel for different days.
R3 A guest cannot make two or more bookings in the same hotel for the

same day.
R4 A guest can make two or more bookings in different hotels for the

same day.
R5 A room in any hotel can only be booked by one guest on the same

date, i.e., no double-booking.

40/54

Accommodation Database

Consider the following:

We have some requirements on BOOKING:

R1 A booking can be made for one day only.
R2 A guest can make several bookings in a hotel for different days.
R3 A guest cannot make two or more bookings in the same hotel for the

same day.
R4 A guest can make two or more bookings in different hotels for the

same day.
R5 A room in any hotel can only be booked by one guest on the same

date, i.e., no double-booking.

41/54

How to Identify FDs?

Consider the following:

Which functional dependency does the following requirement imply?

R1 A booking can be made for one day only.

↪→ {guestNo, hotelNo, roomNo} → {date}? No

guestNo hotelNo roomNo Date

001 H1 R101 28/08/2020
001 H1 R101 29/08/2020

41/54

How to Identify FDs?

Consider the following:

Which functional dependency does the following requirement imply?

R1 A booking can be made for one day only.

↪→ {guestNo, hotelNo, roomNo} → {date}?

guestNo hotelNo roomNo Date

001 H1 R101 28/08/2020
001 H1 R101 29/08/2020

41/54

How to Identify FDs?

Consider the following:

Which functional dependency does the following requirement imply?

R1 A booking can be made for one day only.

↪→ {guestNo, hotelNo, roomNo} → {date}? No

guestNo hotelNo roomNo Date

001 H1 R101 28/08/2020
001 H1 R101 29/08/2020

41/54

How to Identify FDs?

Consider the following:

Which functional dependency does the following requirement imply?

R1 A booking can be made for one day only.

↪→ {guestNo, hotelNo, roomNo} → {date}? No

guestNo hotelNo roomNo Date

001 H1 R101 28/08/2020
001 H1 R101 29/08/2020

42/54

How to Identify FDs?

Consider the following:

Which functional dependency does the following requirement imply?

R2 A guest can make several bookings in a hotel for different days.

None

42/54

How to Identify FDs?

Consider the following:

Which functional dependency does the following requirement imply?

R2 A guest can make several bookings in a hotel for different days.

None

43/54

How to Identify FDs?

Consider the following:

Which functional dependency does the following requirement imply?

R3 A guest cannot make two or more bookings in the same hotel for the
same day.

↪→ {guestNo, hotelNo, date} → {roomNo}? Yes

guestNo hotelNo roomNo Date

001 H1 R101 29/08/2020
001 H1 R102 × 29/08/2020

43/54

How to Identify FDs?

Consider the following:

Which functional dependency does the following requirement imply?

R3 A guest cannot make two or more bookings in the same hotel for the
same day.

↪→ {guestNo, hotelNo, date} → {roomNo}?

Yes

guestNo hotelNo roomNo Date

001 H1 R101 29/08/2020
001 H1 R102 × 29/08/2020

43/54

How to Identify FDs?

Consider the following:

Which functional dependency does the following requirement imply?

R3 A guest cannot make two or more bookings in the same hotel for the
same day.

↪→ {guestNo, hotelNo, date} → {roomNo}? Yes

guestNo hotelNo roomNo Date

001 H1 R101 29/08/2020
001 H1 R102 × 29/08/2020

44/54

How to Identify FDs?

Consider the following:

Which functional dependency does the following requirement imply?

R4 A guest can make two or more bookings in different hotels for the
same day.

None

44/54

How to Identify FDs?

Consider the following:

Which functional dependency does the following requirement imply?

R4 A guest can make two or more bookings in different hotels for the
same day.

None

45/54

How to Identify FDs?

Consider the following:

Which functional dependency does the following requirement imply?

R5 A room in any hotel can only be booked by one guest on the same
date, i.e., no double-booking.

↪→ {hotelNo, date, roomNo} → {guestNo}

Yes

guestNo hotelNo roomNo Date

001 H1 R101 29/08/2020
002 × H1 R101 29/08/2020

45/54

How to Identify FDs?

Consider the following:

Which functional dependency does the following requirement imply?

R5 A room in any hotel can only be booked by one guest on the same
date, i.e., no double-booking.

↪→ {hotelNo, date, roomNo} → {guestNo} Yes

guestNo hotelNo roomNo Date

001 H1 R101 29/08/2020
002 × H1 R101 29/08/2020

46/54

How to Find Candidate Keys?

Consider the following:

FDs on BOOKING

{guestNo, hotelNo, date} → {roomNo} by R3
{hotelNo, date, roomNo} → {guestNo} by R5

Candidate keys on BOOKING

{guestNo, hotelNo, date}
{hotelNo, date, roomNo}

46/54

How to Find Candidate Keys?

Consider the following:

FDs on BOOKING

{guestNo, hotelNo, date} → {roomNo} by R3
{hotelNo, date, roomNo} → {guestNo} by R5

Candidate keys on BOOKING

{guestNo, hotelNo, date}
{hotelNo, date, roomNo}

47/54

How to Identify FDs?

Consider BOOKING(guestNo, hotelNo, date, roomNo) and the following
changes:

R1 A booking can be made for one day only.
R2 A guest can make several bookings in a hotel for different days.
R3 A guest cannot make two or more bookings in the same hotel for the

same day.
R4 A guest can make two or more bookings in different hotels for the

same day.
R5 A room in any hotel can only be booked by one guest on the same

date, i.e., no double-booking.
R6 A guest is not allowed to make more than one booking for the same

day even in the different hotels.

48/54

How to Identify FDs?

Consider the following:

Which functional dependency does the following requirement imply?

R6 A guest is not allowed to make more than one booking for the same
day even in the different hotels.

↪→ {guestNo, date} → {hotelNo, roomNo}

48/54

How to Identify FDs?

Consider the following:

Which functional dependency does the following requirement imply?

R6 A guest is not allowed to make more than one booking for the same
day even in the different hotels.

↪→ {guestNo, date} → {hotelNo, roomNo}

49/54

How to Find Candidate Keys?

Consider the following:

FDs on BOOKING

{hotelNo, date, roomNo} → {guestNo} by R5
{guestNo, date} → {hotelNo, roomNo} by R6

Candidate keys on BOOKING

{hotelNo, date, roomNo}
{guestNo, date}

49/54

How to Find Candidate Keys?

Consider the following:

FDs on BOOKING

{hotelNo, date, roomNo} → {guestNo} by R5
{guestNo, date} → {hotelNo, roomNo} by R6

Candidate keys on BOOKING

{hotelNo, date, roomNo}
{guestNo, date}

50/54

(credit cookie) Kurt Gödel and Incompleteness Theorem

Kurt Gödel (1906-1978)

51/54

Armstrong’s Inference Rules

Two questions:

Are all the FDs inferred using the Armstrong’s inference rules correct?
soundness (you cannot prove anything that is wrong)

Can we use the Armstrong’s inference rules to infer all possible FDs?
completeness (you can prove anything that is right)

Theorem (W. W. Armstrong)

The Armstrong’s inference rules are both sound and complete.

52/54

Hilbert’s program (1920s)

Formulation of mathematics: formalize all true mathematical statements
Completeness: all true mathematical statements can be proved
Consistency: no contradiction can be obtained in the formalism
Decidability: decide the truth or falsity of any mathematical statement.

David Hilbert (1862-1943)
We must know. We will know.

52/54

Hilbert’s program (1920s)

David Hilbert (1862-1943)
We must know. We will know.

53/54

Kurt Gödel and Incompleteness Theorem

Kurt Gödel
(1906-1978)

Theorem (Kurt Gödel, 1931)
For any computable axiomatic system that is powerful enough to describe
the arithmetic of the natural numbers, there will always be at least one
true but unprovable statement.

54/54

Kurt Gödel and Gödel Prize

Kurt Gödel
(1906-1978)

John von Neumann
(1903-1957)

Kurt Gödel’s achievement in modern logic is singular and monumental –
indeed it is more than a monument, it is a landmark which will remain visible
far in space and time. — John von Neumann

The Gödel prize became an annual prize for outstanding papers in the area
of theoretical computer science since 1993.

54/54

Kurt Gödel and Gödel Prize

Kurt Gödel
(1906-1978)

John von Neumann
(1903-1957)

Kurt Gödel’s achievement in modern logic is singular and monumental –
indeed it is more than a monument, it is a landmark which will remain visible
far in space and time. — John von Neumann

The Gödel prize became an annual prize for outstanding papers in the area
of theoretical computer science since 1993.

Related Posts