The Relational Model

COMP107 Lectures 2020-12-04

Relations

A relation is an ordered list of tuples:

• Relation $R=$ set of all pairs $(\text{Computer Scientist}$$,\text{Language they designed})$.
• $R=\{(x,y)\in C\times P \text { such that } x$$ \text{ is the designer of } y\}$.

Relational Model

An application of concepts from a branch of mathematics (relational algebra) to the problem of storing large amounts of data.

Driving principle is that all data can be represented as a set of relations:

• A relation has a name.
• A relation is a collection of related data values.
  • Visualised as a “table” of values.
    • Where each “row” is a “fact”.
  • In relational jargon a row is called a Tuple.
• Column names interpret the meaning of the values in each row.
  • We call them attributes.

Relation v.s. Schema

The relation is the collection of related data and the Schema is the description of the database.

Say that we want to express a relation schema for the relation LECTURERS. We would represent this like so:

LECTURER(StaffNo,FirstName,SecondName,Office,Department)

A relation is the predicate which states which combinations of values of the set of attributes of the schema, according to the domains, is to be considered valid at a given time:

This can be written as: $s(\text{LECTURERS})=\{t_1,t_2,t_3\}$

The relation above states that there are 3 valid tuples:

t1 = <534663,Ada,Lovelace,G23,Comp.Science>
t2 = <583240,Alan,Turing,2.08,Mathematics>
t3 = <678090,Grace,Hopper,1.10,Comp.Science>

To indicate a value in a tuple then you would say: t3.Office=1.10 or t3[Office]=1.10.

Properties of Relations

• A Relation is defined as a set of tuples.

  Elements have no order among them (by definition of set!)

  • This means that tables with different ordering of rows represent the same relation.

    Additionally the order of the attributes and values are not important either as long as the order is maintained between the tuples.

  • Sets have no duplicates, as such you must have all unique rows.

    • In the relational model, this can only happen by playing with attributes. In this case we need a key.

• Each value in a tuple is atomic - the relational model is flat.

  • This means that multi-valued attributes are not allowed.
    • First normal Form
  • Composite attributes are not allowed and have to be implemented in another manner.

Keys

Keys are sets of attributes of a relation with special properties.

Superkey (SK)

A set of attributes such that no two distinct tuples in any state $r$ of $R$ can have the same value for it.

• Eg. StaffID+Surname is a superkey.

Key (K)

A Key is a Superkey of $R$ such that, if you remove any attribute from it, you are left with a set of attributes that is not a Superkey of $R$ any more.

• You may have more than one key (e.g. StaffID and NIN)

Primary key

Designated explicitly among candidate keys.

Entity Integrity

Property of relational DBs that ensures that that there are no duplicate tuples within each relation. This translates into:

• Each relation must have a primary key.
• No primary key value can be NULL.
  • For searching purposes, but more importantly for referring to other tuples when we implement relationships.

Relations v.s Relationships

The concept of relationship is not represented explicitly in a relational DB.

graph LR
a[ ] --> b{ }
b --> c[ ]

• Thus, there is no physical link from one table to another to indicate two tuples in a relationship.

It is represented logically, by a using keys and other attributes that replicate values across tables.

• So relational DBs have by definition some level of redundancy.

Foreign Keys

Foreign key are attributes in a relation that reference a tuple in another relation, by using that relation’s primary key.

Constraints

• Foreign key fields can have any name.
  • But they are usually given the same name as the corresponding primary key they refer to.
• Foreign keys must have the same data type as the corresponding primary key they refer to.
• Foreign keys must only contain values which are at that moment in time existing within the primary key.

  • To add a Lecturer in AI you need to create the Department first.

    This means that to use a value that is part of a foreign key in another table it first must exist in the table you are taking the values from.

Referential Integrity

A property in relational DB that maintains consistency among tuples.

Foreign key rules for ensuring referential integrity:

• The attributes in FK have the same domain(s) as the primary key attributes PK.
• Each value of FK in each tuple at any time either occurs as a value of PK for some other tuple at the same time, or is NULL.

Types of relationship

One-to-Many

One tuple may be related to more than one tuple, but not vice versa.

For example: One Department may have many Lecturers (but one Lecturer belongs to only one Department).

When implementing one-to-many relationships:

• The values of the foreign key (FK) of one table must be present among the values of the primary key in the other table for the relation to exist (“referential integrity”).
• Not symmetrical: can have value in the primary key that are not in the FK (individuals which are not related to others, e.g. Departments that do not have Lecturers…)

Many-to-Many

One tuple may be related to more than one tuple, and vice versa.

For example: One Lecturer may teach several Courses, and the same Course may be taught by more than one Lecturer.

When implementing many-to-many relationships:

• You can’t implement many-to-many relationships directly.
  • They are rendered by composing two one-to-many relationships.
  • Need an intermediate table.
  • Constraints on the two one-to-many relationships hold as usual.

One-to-One

One tuple is related to one other tuple only.

For example: Each Department can have only one Head, and each Lecturer can only be head of one Department.

When implementing one-to-one relationships:

• As for 1:N, the values of the foreign key (FK) of one table must be present among the values of the primary key in the other table for the relation to exist (“referential integrity”).
• Not symmetrical - can have value in the primary key that are not in the FK.
• FK defined so that it cannot contain duplicate values.

Constraints on the FK - Examples

• One Lecturer can have many Teaching Duties (one-to-many relationship).
• One Course may be part of many Teaching Duties (one-to-many relationship).

This implements the fact that Lecturers and Courses are in a many-to-many relationship.

Semantic Integrity

In addition to Entity Integrity and Referential Integrity:

• Set of constraints that are specific of the semantic (meaning) of the model the database is representing.
• Typically cannot be expressed within a relation definition.
  • Typically because they involve complex verifications.
  • E.g. “the salary of a lecturer cannot be higher than the salary of the head of department”.
• Defined by using triggers and assertions (more in comp207).

Other Constraints

Functional Dependency Constraints

• Establish a functional relationship among two sets of attributes.
• Value of one set determines a unique value of the other set.
• At the basis of the normalisation process.

State constraints

• Define the constraints that a valid state of the database must satisfy.

Transition constraints

• Define how to deal with state changes in the database.

University Database Definition

The database comprises 4 relations:

LECTURERS (StaffNo,1stName,2ndName,Office,Department)
DEPARTMENTS (Department,Address, Head)
COURSES (Course,Semester,CourseDep)
TEACHINGDUTIES (StaffNo,Course)

The section in the () are the schemas of the relation.

Where the following referential constraints exist:

TEACHINGDUTIES.StaffNo references LECTURERS.StaffNo
TEACHINGDUTIES.Course references COURSES.Course
LECTURERS.Department references DEPARTMENTS.Department
COURSES.CourseDep references DEPARTMENTS.Department
DEPARTMENTS.Head references LECTURERS.StaffNo

This is the list of foreign and primary keys. They don’t necessarily need the same name.