COMP9311
2023T2
Revision
Zhengyi Yang, UNSW
1
Details of Final Exam:
1. Time: 9AM to 12PM, Sydney time. 18th Aug 2023.
2. Exam paper: will be released on our course website just before 9AM 18th Aug
2022.
3. How to submit: via Moodle
◦ Same procedure as what you did for the two assignments.
◦ In case near 12PM and you cannot submit via Moodle, send your solution to
zyang@cse.unsw.edu.au and yiheng.hu@unsw.edu.au with you zID and
name.
◦ You can submit multiple times and we will mark the last one.
◦ We accept any format: directly answer using word or handwriting and
convert to word/pdf. As long as the file is in .doc or .pdf format and clear.
4. Any question during the exam, send email to zyang@cse.unsw.edu.au and
yiheng.hu@unsw.edu.au
2
Final Exam
❖ 3 hrs + 10 mins for uploading (i.e., the exam paper will be released
on the course website about 10 mins before the exam starts)
❖ If you do not feel well on the exam day, please not attend the
exam. By sitting or submitting an exam or assessment on the
scheduled assessment date, you are declaring that you are fit to do
so and cannot later apply for Special Consideration. (I.e., no
sup-exam will be given.)
3
Late Submission
You MUST submit your answers on time
Extra 10 minutes will be given to upload the answers (they are NOT used
to answer questions).
5% late penalty per minute for late submissions.
Submitting wrong files will result in 0 marks.
4
Plagiarism
★ We adopt a zero-tolerance policy for plagiarism.
All submissions are checked for plagiarism. The university regards plagiarism as a
form of academic misconduct and has very strict rules regarding plagiarism.
For UNSW policies, penalties, and information to help avoid plagiarism, please
see: https://student.unsw.edu.au/plagiarism. Not knowing the rules is not
considered a valid excuse.
All assessments must be your own original work. They are NOT group project.
DO NOT: copy from others, copy from the Internet, pay someone to do it.
You are not allowed to use generative AI tools such as ChatGPT.
5
Question Types:
- 6 questions
- Similar to questions in assignments and sample exam
paper
6
Consultation:
We will also run (hybrid) consultation before the final exam:
Week 11
8th Aug, 14-15 PM, Building K17 Room 204
10th Aug, 14-15 PM, Building K17 Room 203
Week 12
14th Aug, 14-15 PM, Building K17 Room 508
15th Aug, 18-19 PM, Building K17 Room 508
16th Aug, 14-15 PM, Building K17 Room 508
17th Aug, 14-15 PM, Building K17 Room 508
7
Overview: Database Design 1
Data models:
◦ ER, Relational Data Model and their mapping
Relational Algebra:
◦ Be able to use relational algebra to answer question.
Database Languages:
◦ SQL (final exam: may need to write some simple SQL)
Relational Database Design:
◦ Functional Dependency
◦ Normal Forms
◦ Design Algorithms for 3NF and BCNF
8
Overview: Database Design 2
Data Storage:
◦ Record Format,
◦ Buffer Management
Query Optimisation:
◦ Index
◦ Query Plan/Join Order Selection
Transaction Management:
◦ Concurrency Control
◦ Recovery
NoSQL：
◦ NoSQL Concept
◦ Different Data Model
◦ Key-Value, Document, Column-family, Graph
9
Data Models
ER, Relational Data Model and their mapping
10
Application E-R Relational DB
Entity-Relationship Model(cont)
1. Entity type: Group of object with the same properties
2. Entity: member of an entity type - analogous to an object.
3. Attribute: a property of object
4. Relationship: among objects
11
Notmations (cont)
The notation used for ERDs is summarised in Elmasre/Navathe Figure
3.15.
12
of a (strong) entity
of a weak entity
Relating to Weak Entities
Relational Data Model
In the relational model, everything is described using relations.
A relation can be thought of as a named table.
Each column of the table corresponds to a named attribute.
The set of allowed values for an attribute is called its domain.
Each row of the table is called a tuple of the relation.
N.B. There is no ordering of column or rows.
13
Keys
Keys are used to identify tuples in a relation.
A superkey is a set of attributes that uniquely determines a tuple.
Note that this is a property of the relation that does not depend on the
current relation instance.
A candidate key is a superkey, none of whose proper subsets is a
superkey.
Keys are determined by the applications.
14
Integrity Constraints
There are several kinds of integrity constraints that are an integral part
of the relational model:
1. Key constraint: candidate key values must be unique for every
relation instance.
2. Entity integrity: an attribute that is part of a primary key cannot be
NULL.
3. Referential integrity: The third kind has to do with “foreign keys”.
15
Foreign Keys
Foreign keys are used to refer to a tuple in another relation.
A set, FK, of attributes from a relation schema R1 may be a foreign key if
◦ the attributes have the same domains as the attributes in the
primary key of another relation schema R2, and
◦ a value of FK in a tuple t1 of R1 either occurs as a value of PK for
some tuple t2 in R2 or is null.
Referential integrity: The value of FK must occur in the other relation or
be entirely NULL.
16
ER to Relational Model Mapping
One technique for database design is to first design a conceptual
schema using a high-level data model, and then map it to a conceptual
schema in the DBMS data model for the chosen DBMS.
Here we looked at a way to do this mapping from the ER to the
relational data model. (see details in the lecture notes of Relational Data
Model).
Composite and multivalued attributes are allowed in ER model, but not
allowed in relational data model.
17
Relational Algebra
Relational Algebra is a procedural data manipulation language (DML).
It specifies operations on relations to define new relations:
Unary Relational Operations: Select, Project
Operations from Set Theory: Union, Intersection, Difference,
Cartesian Product
Binary Relational Operations: Join, Divide.

Relational Algebra: be able to use relational algebra to answer
question.
18
19
OPERATION PURPOSE NOTATION
SELECT Selects all tuples that satisfy the selection condition from a relation R
PROJECT Produces a new relation with only some of the attributes of R and removes duplicate tuples.
THETA-JOIN Produces all combinations of tuples from R and S that satisfy the join condition.
EQUI-JOIN Produces all the combinations of tuples from R and S that satisfy a join condition with only equality comparisons.
NATURAL-JOIN
Same as EQUIJOIN except that the join attributes of S are not
included in the resulting relation; if the join attributes have
the same names, they do not have to be specified at all.
UNION Produces a relation that includes all the tuples in R or S or both R and S; R and S must be union compatible.
INTERAECTION Produces a relation that includes all the tuples in both R and S; R and S must be union compatible.
DIFFERENCE Produces a relation that includes all the tuples in R that are not in S; R and S must be union compatible. R - S
CARTESIAN
PRODUCT
Produces a relation that has the attributes of R and S and
includes as tuples all possible combinations of tuples from R
and S.
DIVISION
Produces a relation T(X) that includes all tuples t[X] in R(Z)
that appear in R in combination with every tuple from S(Y),
where Z = X ∪ Y.
See notes on notation in the next side
Relational Algebra Notation:

20
Database Languages
❖ Database Languages: SQL
❖ final exam: may need to write some simple SQL
21
SQL Queries(cont)
Query syntax is:
SELECT attributes
FROM relations
WHERE condition
The result of this statement is a table, which is typically displayed on output.
The SELECT statement contains the functionality of select, project and join
from the relational algebra.
22
SQL Comparisons
Comparison operators are defined on all types.
< > <= >= = !=
Boolean operators AND, OR, NOT are available within WHERE expressions to combine
results of comparisons.
Comparison against NULL yields FALSE.
Can explicitly test for NULL using:
◦ attr IS NULL attr IS NOT NULL
Most data types also have type-specific operations available (e.g., arithmetic for
numbers).
23
Relational Database Design
❖ Relational Database Design: Functional Dependency, Normal Forms,
Design Algorithms for 3NF and BCNF
24
Functional Dependencies
A function f from S1 to S2 has the property
A generalization of keys to avoid design flaws violating the above rule.
Let X and Y be sets of attributes in R.
X (functionally) determines Y , X → Y , iff t1[X] = t2[X] implies t1[Y ] = t2[Y
].
i.e., f (t(X)) = t [Y]
We also say X →Y is a functional dependency, and that Y is functionally
dependent on X.
X is called the left side, Y the right side of the dependency.
25

Armstrong’s Axioms (1974)
Notation: If X and Y are sets of attributes, we write XY for their union.
e.g., X = {A, B}, Y = {B, C}, XY = {A, B, C}
1. F1 (Reflexivity) If X ⊇ Y then X →Y .
2. F2 (Augmentation) {X → Y } |= XZ → Y Z.
3. F3 (Transitivity) {X → Y , Y → Z} |= X → Z.
4. F4 (Additivity) {X→ Y , X → Z} |= X → Y Z.
5. F5 (Projectivity) {X → Y Z} |= X → Y .
6. F6 (Pseudo-transitivity) {X → Y , Y Z → W} |= XZ → W.
26
Algorithm to Compute X+
X+ := X;
change := true;
while change do
begin
change := false;
for each FD W → Z in F do
begin
if (W ⊆ X+) and (Z X+) then do
begin
X+ := X+ ∪ Z;
change := true;
end
end
end
27
Compute a Candidate Key
Given a relational schema R and a set F of functional dependencies on
R.
A key X of R must have the property that X+ = R.
Algorithm
◦ Step 1: Assign X a superkey in F.
◦ Step 2: Iteratively remove attributes from X while retaining the
property X+ = R.
◦ The remaining X is a key.
28
Compute all Candidate Keys

29
Normal Forms
Normal Forms for relational databases:
• 1NF, 2NF, 3NF (Codd 1972)
• Boyce-Codd NF (1974)
30
First Normal Form (1NF)
This simply means that attribute values are atomic and is part of the definition
of the relational model.
Atomic: multivalued attributes, composite attributes, and their combinations
are disallowed.
There is currently a lot of interests in non-first normal form databases,
particularly those where an attribute value can be a table (nested relations).
31
Second Normal Form (2NF)
A prime attribute is one that is part of a candidate key. Other attributes
are non-prime.
Definition: In an FD X→ Y , Y is fully functionally dependent on X if there
is no Z ⊂ X such that Z → Y . Otherwise, Y is partially dependent on X.
Definition (Second Normal Form): A relation scheme is in second normal
form (2NF) if all non-prime attributes are fully functionally dependent
on the relation keys.
A database scheme is in 2NF if all its relations are in 2NF.
32
Third Normal Form (3NF)
Definition (Third Normal Form): A relation scheme is in third normal
form (3NF) if for all non-trivial FD’s of the form X→A that hold, either X
is a superkey or A is a prime attribute.
Note: a FD X → Y is trivial iff Y is a subset of X.
Alternative definition: A relation scheme is in third normal form if every
non-prime attribute is fully functionally dependent on the keys and not
transitively dependent on any key.
A database scheme is in 3NF if all its relations are in 3NF.
33
Boyce-codd Normal Form (BCNF)
Definition (Boyce-codd Normal Form):
A relation scheme is in Boyce-codd Normal Form (BCNF) if whenever
X→A holds (and X→A is non-trivial), X is a superkey.
A database scheme is in BCNF if all its relations are in BCNF.
34
On Relational Database Design

35
Dependency Preserving
36
A decomposition D={R1, …, Rn} of R is dependency-preserving
wrt a set F of FDs if:
(F1 ∪ … ∪ Fn)
+ = F+,
where Fi means the projection of F onto Ri.
Lossless-join Decomposition

37
Lossless Decomposition into BCNF
Algorithm TO_BCNF
D := {R1,R2, ...Rn}
While ∃ a Ri ∈ D and Ri is not in BCNF Do
◦ { find a X →Y in Ri that violates BCNF; replace Ri in D by (Ri − Y ) and
(X ∪ Y ); }
38
Computing a Minimum cover
A set F of FD’s is minimal if
1. Every FD X→ Y in F is simple: Y consists of a single attribute,
2. Every FD X→ A in F is left-reduced: there is no proper subset
Y ⊂ X such that X → A can be replaced with Y→A.
that is, there is no Y ⊂X such that
((F − {X → A}) ∪{Y → A})+ = F+
3. No FD in F can be removed; that is, there is no FD X→A in F such that
(F − {X → A})+ = F+
39
i.e., Iff F |= Y -> A
i.e., Iff X->A is inferred
from F – { X->A}
Computing a Minimum cover
A minimal cover (or canonical cover) for F:
◦ a minimal set of FD’s Fmin such that F
+ = F+min.
Algorithm Min_Cover
Input: a set F of functional dependencies.
Output: a minimum cover of F.
Step 1: Reduce right side.
Apply Algorithm Reduce_right to F.
Step 2: Reduce left side.
Apply Algorithm Reduce_left to the output of Step 2.
Step 3: Remove redundant FDs.
Apply Algorithm Remove_redundency to the output of Step 2.
The output is a minimum cover.
Next we detail the three algorithms (Reduce_right, Reduce_left, Reduce_redundancy) .
40
Computing a Minimum cover (cont)
1. Algorithm Reduce_right
INPUT: F.
OUTPUT: right side reduced F’.
1. For each FD X→ Y ∈ F where Y = {A1,A2, ...,Ak}, we use all X →{Ai} (for 1≤ i ≤ k) to replace X→ Y .
2. Algorithm Reduce_left
INPUT: right side reduced F.
OUTPUT: right and left side reduced F’.
1. For each X → {A} ∈ F where X = {Ai : 1 ≤ i ≤ k}, do the following. For i = 1 to k, replace X with X − {Ai} if A∈ (X − {Ai})
+.
4. Algorithm Reduce_redundancy
INPUT: right and left side reduced F.
OUTPUT: a minimum cover F’ of F.
1. For each FD X → {A} ∈ F, remove it from F if: A ∈ X+ with respect to F − {X
→{A}}.
41
Decomposition into 3NF
A lossless and dependency-preserving decomposition into 3NF is always
possible.
Algorithm 3NF decomposition (Lossless and Dependency-preserving)
1. Find a minimal cover G for F.
2. For each left-hand-side X of a functional dependency that appears in G,
create a relation schema in D with attributes {X ∪ {A1} ∪ {A2} ... ∪ {Ak}
}, where X -> A1, X -> A2, ..., X -> Ak are the only dependencies in G with X
as left-hand-side (X is the key to this relation).
3. If none of the relation schemas in D contains a key of R, then create one
more relation schema in D that contains attributes that form a key of R.
4. Eliminate redundant relations from the resulting set of relations in the
relational database schema. A relation R is considered redundant if R is a
projection of another relation S in the schema; alternately, R is subsumed
by S.
42
Overview: DBMS
❖ Disk, Buffer Replacement Policy
❖ Transaction Management
▪ ACID properties
▪ Various schedules: Serializable, Conflict-Serializable, Schedule
Graph, Wait for Graph, …
▪ Concurrency control (locking, locking with time-stamps).
43
Record Format
- Format
- Fixed-length
- Variable Length
- Fragmented free space
44
Buffer Replacement Policies
1. Least Recently Used (LRU)
◦ release the frame that has not been used for the longest period.
◦ intuitively appealing idea but can perform badly
2. First in First Out (FIFO)
3. Most Recently Used (MRU):
◦ release the frame used most recently
No one is guaranteed to be better than the others. Quite dependent on
applications.
45
Query Optimisation
- Use Index
- Hash Index
- B+-Tree Index
- Write more efficient query
- Query Optimiser
- Cost estimation
- Join Order
- Reduce number of intermediate results
46
Desirable Properties of Transaction Processing
ACID Properties
Atomicity:
A transaction is either performed in its entirety or not performed at all.
Consistency:
A correct execution of the transaction must take the database from one
consistent state to another.
Isolation:
A transaction should not make its updates visible to other transactions until it
is committed.
Durability/ Permanency:
Once a transaction changes the database and the changes are committed,
these changes must never be lost because of subsequent failure.
47
Check Conflict Serializability
◦ Algorithm
Step 1: Construct a schedule (or precedence) graph – a directed
graph.
Step 2: Check if the graph is cyclic:
• Cyclic: non-serializable.
• Acyclic: serializable.
48
Construct a Schedule Graph
Schedule Graph GS = (V, A) for a schedule S
A vertex in V represents a transaction.
For two vertices Ti and Tj, an arc Ti →Tj is added to A if
• there are two conflicting operations O1 ∈ Ti and O2 ∈ Tj,
• in S, O1 is before O2.
Recall: two operations O1 and O2 are conflicting if
• they are in different transactions but on the same data item,
• one of them must be a write.
49
Locking Rules
In this schema, every transaction T must obey the following rules.
1) If T has only one operation (read/write) manipulating an item X:
• obtain a read lock on X before reading it,
• obtain a write lock on X before writing it,
• unlock X when done with it.
2) If T has several operations manipulating X:
• obtain one proper lock only on X:
a read lock if all operations on X are reads;
a write lock if one of these operations on X is a write.
• unlock X after the last operation on X in T has been executed.
You should know Two-Phase Locking!
50
NoSQL
- Why NoSQL?
- How to choose a database model given your requirements?
- CAP Theorem
- Features (pros and cons) of different data models
51
Note 1:
Computer Updates
You must ensure that auto-updates are disabled on your computer prior
to the online assessment.
Special consideration will NOT be awarded on the grounds that your
computer performed an update during an online assessment.
52
Note 2:
If you accidently upload the wrong document or wrong version of your
exam
Students are responsible for uploading the correct version of the correct
document. Once uploaded, there will be no opportunity to replace or
re-upload your exam papers AFTER the end of the exam.
The documents submitted will be the documents that are marked.
There is NO provision for students who upload incorrect or incomplete
documents.
Therefore, you must check the work before you submit.
53
Note 3:
Communication during the exam
Students are NOT permitted to communicate with other people during
the exam (including the reading and submission periods).
Attempts to communicate with other students will be considered to be
serious academic misconduct.
This includes communication in person, by email, text, message,
telephone, or internet.
i.e., do the work yourself
54
Note 4:
Sharing answers with others or posting them online
Any attempts to collaborate or share your answers with others will be
considered a very serious case of academic misconduct
55
Note 5 (Checklist):
1. Be logged in at your computer and ready to go 15 minutes before
the exam commences.
2. Ensure your device has power, and the charger is plugged in.
3. If applicable remind your roommates or family that you’ll be
taking an exam to avoid interruptions.
56
Note 6:
If you experience other issues, take timestamped screenshots

Contact the Course Coordinator or Tutor via email to advise you are
experiencing a technical issue, as soon as possible.
57
Tips
- You can attempt the questions in any order, arrange your time
wisely.
- Read all questions carefully
- Be fully prepared before the exam: don’t forget to eat, take break and
relax yourself, no need to panic
58
My Experience Survey
The UNSW My Experience survey still open for 23T2, participation is
highly encouraged.
“Please participate in the my Experience Survey and take the
opportunity to share your constructive thoughts on your 2023 learning
experience.
Your contributions help your teachers and shape the future of education
at UNSW.”
More information: https://www.student.unsw.edu.au/myexperience
59
Thank you and all the best!