The schema of a database is the logical structure that defines the organization of data.

Schema Vs Instance

The schema defines the structure (sometimes called the intention) of the database. It is relatively static and changes only through explicit schema modification. The actual data stored at any point in time is the database instance (or extension), which must conform to the schema.

A database instance (or extension) describes the content stored in a database at a given point in time. If the database has a fixed schema, every database instance must conform to it — that is, every tuple in the instance must respect the domains, key constraints, and functional dependencies defined by the schema.

Properties

• The instance changes as data is inserted, updated, or deleted. The schema typically remains fixed.
• At any point in time, the instance must satisfy all integrity constraints declared in the schema (e.g. every super key must uniquely identify tuples, no primary key value may be null).

An entity-relationship diagram is a method of conceptually describing the schema of a database in a human viewable format.

Components

Entity

The entities of an entity-relationship diagram describes a "thing" that is capable of an independent existence that can be uniquely identified. An entity is a thing that exists either physically or logically.

An entity may be a physical object such as a house or a car (they exist physically), an event such as a house sale or a car service, or a concept such as a customer transaction or order (they exist logically as a concept).

Entities can typically be thought of as nouns. Examples include a computer, an employee, a song, or a mathematical theorem.

Relationship

The relationships of an entity-relationship diagram captures how entities are related to each other. Relationships can be thought of as verbs linking two or more nouns.

Examples include an owns relationship between a company and a computer, a supervises relationship between an employee and a department, a performs relationship between an artist and a song, and a proves relationship between a mathematician and a conjecture.

Cardinality

The cardinality of a relationship describes the number of relationships that an entity can participate in. There are generally 4 types of cardinality:

1. one-to-one - The entity A is associated with at most one entity B and vice versa
   • We could model an employees computer using a one-to-one relationship as every employee only has one computer and every computer is used by only one employee.
2. one-to-many - The entity A is associated with any number of entities B but each B is only associated with at most one entity A
   • We can model a teacher and the classes they teach with a one-to-many relationship as a class can only have a single teacher but one teacher can teach many classes.
3. many-to-one - The entity A is associated with at most one of the entities B but each B can be associated with any number of entities A (this is the inverse of one-to-many).
   • This can just model the inverse of one-to-many for example we can model a class having a single teacher but every teacher teaching multiple classes.
4. many-to-many - The entity A is associated with any number of entities B and vice versa
   • We can model the relationships between students and classes using many-to-many relationships as each student is taking multiple classes and each class has multiple students enrolled in it.

Participation

The participation of a relationship describes whether an entity must be involved in that relationship in order to exist. There are generally 2 types of participation:

1. total participation - Every instance of the entity must participate in at least one instance of the relationship.
   • We could model an employee belonging to a department using total participation as every employee must be assigned to a department.
2. partial participation - Some instances of the entity may not participate in the relationship.
   • We could model an employee managing a department using partial participation as not every employee is a manager.

Notation

When designing an entity-relationship diagram, the entities are drawn as squares with their descriptive name (typically a noun) in the centre, these are then connected to the attributes using a line which are drawn as circles with their respective attribute keys in the middle.

Relationships are drawn as a vertical rhombus (resembling a kite) with a descriptive name in the centre (typically a verb) in the centre. These relationships are then linked to their constituting entities.

Line Notation

The lines to relationships can be "plain" or have arrows, these combinations of arrows an plane lines describes the cardinality of the relationship.

Cardinality

One-to-one

Two plane lines indicate a many-to-many relationship

Example of a many-to-many relationship between actors who work on movies.

One-to-many and Many-to-one

One plane line and an arrow indicate a one-to-many or a many-to-one relationship

Example of a one-to-many relationship between directors who direct movies.

One-to-one

Two arrows indicate a one-to-one relationship

Example of a one-to-one relationship between a country and their capital.

Participation

When an entity requires total participation it's line to the relationship is drawn bolded.

Example of a one-to-many relationship between directors who direct movies, where movies are required to have a relationship to a director.

A weak entity is an entity that cannot be uniquely identified by it's own attributes alone. It instead relies on a relationship with another entity (known as it's owner entity), to uniquely identify it.

Weak entities must participate in a one-to-many relationship with it's owner entity, called it's identifying relationship (typically a belongs to relationship). Weak entities must have total participation in their identifying relationships sets meaning every weak entity must be related to an owner.

The identifying key of a weak entity is a combination of it's own partial key (discriminator) and the primary key of the owner entity. In a entity-relationship diagram the identifying key is underlined with a dashed line, and weak entities are drawn with thick lines and the same with their identifying relationship.

In the same way as object oriented languages represent inheritance attributes can be inherited through generalization. This is a done through a IsA relationship between two or more entities.

In a entity-relationship diagram we show this be drawing a relationship with a triangle with the label IsA and then connecting it to the relevant entities. On corner (the "top") is connected to the "parent" entity (the one which we inherit attributes from) and then the opposite face is connected to any entities which inherit it's attributes.

Specialization is a method of dividing entities into their sub-entities based on it's characteristics. This is a done through a IsA relationship between two or more entities.

In a entity-relationship diagram we show this be drawing a relationship with an upside down triangle with the label IsA and then connecting it to the relevant entities. On the upper face (the "top") is connected to the "parent" entity (the one which we specialize from) and then the opposite faces are connected to any entities which are specializations of that entity.

Aggregation is a method of modelling relationships between other relationships which is typically not allowed in entity-relationship diagrams. This is most useful for adding descriptive attributes or relationships to existing associations.

We show aggregation in a entity-relationship diagram by surrounding the entities to be aggregated in a dashed box and then drawing a line from the relationships.

SQL is a language for representing operations and relationships in a relational database. SQL was original based on relational algebra and can be broken down into two sub languages DDL and DML.

Sub Languages

CREATE TABLE person (
	person_id SMALLINT UNSIGNED PRIMARY KEY,

	first_name VARCHAR(20) NOT NULL,
	last_name VARCHAR(20) NOT NULL
);

ALTER TABLE person
ADD middle_name VARCHAR(20) NOT NULL;

DROP TABLE IF EXISTS person;

CREATE TABLE person (
	person_id SMALLINT UNSIGNED PRIMARY KEY,
	--                          ^–------––– Constraint

	first_name VARCHAR(20) NOT NULL,
	--                     ^–––––––– Constraint
	last_name VARCHAR(20) NOT NULL
	--                    ^–––––––– Constraint
);

CREATE TABLE enrollment (
    student_id INT UNSIGNED NOT NULL,
    course_id  INT UNSIGNED NOT NULL,
    enrolled_on DATE NOT NULL,

    PRIMARY KEY (student_id, course_id),
    
    FOREIGN KEY (student_id) REFERENCES student(student_id),
    FOREIGN KEY (course_id)  REFERENCES course(course_id)
);

CREATE VIEW person_details AS
SELECT 
	person_id,
	first_name,
	last_name
FROM person
WHERE person_id > 0;

DROP VIEW IF EXISTS person_details;

CREATE OR REPLACE VIEW person_details AS
SELECT 
	person_id,
	first_name,
	last_name,
	middle_name
FROM person
WHERE person_id > 0;

Functional dependence describes a relationship between attributes of a relation. If the attribute Y is functionally dependent on X (X Y) it holds that for every pair of tuples with attributes X and Y, if the X values are equal then the Y values must also be equal.

For example consider a relation with the attributes PostalCode, City, and Province. If PostalCode City, Province, then for all tuples in the relation, if they have equal PostalCode values, they must have the same City and Province.

The symbol can be read as determines. For example X Y can be read as either X functionally determines Y or X determines Y.

Functional dependence can indicate to us that we're storing redundant data and can help us decompose relations without losing information.

Deriving Additional Functional Dependences

Given a set of functional dependences for a relation we can derive additional functional dependences through the following methods:

Axioms

The following axioms (known as Armstrong's Axioms) are sound and complete — they can derive all and only the functional dependencies that are logically implied by a given set. A set of axioms can be used to transform functional dependences

1. Reflexivity: If Y X, then X Y (ie. City, Major City).
2. Augmentation: If X Y, then X, Z Y, Z for any Z (ie.SID City, then SID, Major City, Major).
3. Transivity: If X Y and Y Z, then X Z (ie. SID City and City AreaCode, then SID AreaCode)

These axioms can then be used to derive a few additional rules for ease of use

1. Union: If X Y, and X Z then X Y, Z (eg. SID AreaCode and SID City, then SID AreaCode, City)
2. Decomposition: If X Y, Z then X Y and X Z (eg. SID AreaCode, City then SID AreaCode and SID City)

Closure Method

Alternatively we can use the "closure method", given a set of attributes X we denote the closure of it as X. If X is a super key X contains all attributes of the schema.

The algorithm is expressed as

Let Closure = X Until Closure doesn't change do if a, ..., a C is a functional dependence and {a, ..., } Closure then add C to Closure

Example

Consider the schema SupplierPart(supplierName, city, status, partNumber, partName, quantity) and the functional dependences

• supplierName city
• city status
• partNumber partName
• supplierName, partNumber quantity

Find the closure of supplierName, partNumber, supplierName, and partNumber.

(supplierName, partNumber) = {supplierName, partNumber}

supplierName city is a functional dependence and {supplierName} is a subset of (supplierName, partNumber) so we add city to (supplierName, partNumber).

(supplierName, partNumber) = {supplierName, partNumber, city}

city status is a functional dependence and {city} is a subset of (supplierName, partNumber) so we add status to (supplierName, partNumber).

(supplierName, partNumber) = {supplierName, partNumber, city, status}

partNumber partName is a functional dependence and {partNumber} is a subset of (supplierName, partNumber) so we add partName to (supplierName, partNumber).

(supplierName, partNumber) = {supplierName, partNumber, city, status, partName}

supplierName, partNumber quantity is a functional dependence and {supplierName, partNumber} is a subset of (supplierName, partNumber) so we add quantity to (supplierName, partNumber).

(supplierName, partNumber) = {supplierName, partNumber, city, status, partName, quantity}

We've exhausted all function dependences so this is our final closure. This final closure contains all attributes of the schema so we know (supplierName, partNumber) is a super key.

supplierName = {supplierName}

supplierName city is a functional dependence and {supplierName} is a subset of supplierName so we add city to supplierName.

supplierName = {supplierName, city}

city status is a functional dependence and {city} is a subset of supplierName so we add status to supplierName.

supplierName = {supplierName, city, status}

We've exhausted all functional dependencies which are contained in the closure so this is our final closure.

partNumber = {partNumber}

partNumber partName is a functional dependence and {partNumber} is a subset of partNumber so we add partName to partNumber.

partNumber = {partNumber, partName}

We've exhausted all functional dependencies which are contained in the closure so this is our final closure.

Using those three closures we can see that supplierName, partNumber is a candidate key as reducing either supplierName or partNumber means the key is no longer a super key.

A super key is a set of one or more attributes in a schema that uniquely identifies a tuple.

Formally, a set of attributes is a super key for a relation schema if for every valid instance :

Equivalently, is a super key if holds and the closure contains all attributes of the schema.

Every relation always contains at least one super key: the trivial key, which is the set of all its attributes.

Example

Consider a table Employee with the following attributes

• EmployeeID: Unique ID assigned by the company
• SSN: Social Security Number
• Name: Name of the employee
• Department: The department the employee works at

Some examples of super keys are the following sets:

• {EmployeeID}: Is unique for every Employee
• {SSN}: Like the ID is unique for every Employee
• {EmployeeID, Name}: Via reflexivity as Name is redundant.
• {EmployeeID, SSN, Name, Department}: The trivial super key which already contains all columns.

A candidate key is any super key which cannot be further reduced by removing attributes — that is, no proper subset of it is also a super key.

Formally, a set of attributes is a candidate key for a relation schema if:

1. is a super key
2. No proper subset is a super key ( is minimal).

Every relation has at least one candidate key. All candidate keys of a relation have the same property of uniquely identifying tuples — the choice of which one to designate as the primary key is a design decision.

Example

Consider a table Employee with the following attributes

• EmployeeID: Unique ID assigned by the company
• SSN: Social Security Number
• Name: Name of the employee
• Department: The department the employee works at

Some examples of it's candidate keys are the following sets:

• {EmployeeID}: Is unique for every Employee
• {SSN}: Like the ID is unique for every Employee

Conversely non-candidate keys which are still super keys are the following

• {EmployeeID, SSN}: The SSN or EmployeeID are redundant keys to identify a record.
• {EmployeeID, Name}: The Name attribute is redundant.

A primary key is a designated candidate key that is primarily used to identify records.

Example

Consider a table Employee with the following attributes

• EmployeeID: Unique ID assigned by the company
• SSN: Social Security Number
• Name: Name of the employee
• Department: The department the employee works at

Some examples of it's candidate keys are the following sets:

• {EmployeeID}: Is unique for every Employee
• {SSN}: Like the ID is unique for every `Employee

Given this list of candidate keys we can choose the primary key to be either EmployeeID or SSN. Typically we would choose EmployeeID to be our primary key as we would probably be generating it whereas SSN would be entered by the user.

A normal form is a property of a relation schema that characterizes it in terms of the redundancy it permits. Normal forms are defined with respect to functional dependencies (and in higher forms, multivalued and join dependencies) that hold on the schema.

Normal forms are ordered by strictness. Each successive normal form imposes additional constraints that eliminate further classes of redundancy:

That is, every BCNF relation is in 3NF, every 3NF relation is in 2NF, and every 2NF relation is in 1NF.

Summary

The goal of applying successively stricter normal forms is to minimize update anomalies (insertion, deletion, and modification anomalies) that arise from redundant data storage without losing information. The process of restructuring a schema to satisfy a normal form is called database normalization.

First normal form is the most basic normal form. A relation is in first normal form if and only if every attribute contains only atomic (indivisible) values — that is, no attribute holds a set, list, or nested relation as its value.

Definition

A relation schema is in first normal form if for every valid instance :

• The domain of each attribute contains only atomic values.
• Each tuple assigns exactly one value from the domain to each attribute.

This is essentially a requirement of the relational model itself. E.F. Codd's original definition of a relation requires that all attribute values are atomic, so any valid relation is in 1NF by definition.

Violations

A relation violates 1NF when an attribute contains:

• Multi-valued fields — e.g. a PhoneNumbers attribute storing {555-1234, 555-5678}.
• Composite fields — e.g. a FullName attribute storing a structured value with sub-components FirstName and LastName.
• Nested relations — e.g. an Orders attribute containing an entire table of order records within a single tuple.

Resolving Violations

To bring a relation into 1NF:

1. Multi-valued attributes are resolved by creating a separate tuple for each value, or by decomposing the multi-valued attribute into a separate relation.
2. Composite attributes are resolved by replacing them with their atomic components.

Note

Most modern relational database systems enforce atomicity at the storage level, making 1NF violations uncommon in practice. However, the theoretical distinction remains important as 1NF is the foundation upon which all higher normal forms are built.

Second normal form is a normal form used in database normalization. Second normal form requires that a schema is in 1NF and that every non-key attribute is fully functionally dependent on the entire primary key, meaning no non-key attribute depends on only part of a composite key.

Definition

A schema is in second normal form if:

• It is in 1NF.
• There are no partial functional dependencies, that is no non-key attribute X is dependent on a proper subset of the primary key.

Example

Consider a table Toothbrush with the following attributes

• Manufacturer
• `Model
• ManufacturerCountry

and the following functional dependencies

• Manufacturer, Model ManufacturerCountry
• Manufacturer ManufacturerCountry

Is Toothbrush in 2NF? Justify why or why not and if it isn't decompose it such that it is.

Toothbrush is not in 2NF because ManufacturerCountry is only dependent on Manufacturer not on Model. To reconcile this we decompose it into two new tables

Toothbrush with the following attributes

• Manufacturer
• `Model

and Manufacturer

• Manufacturer
• ManufacturerCountry

Third normal form is a normal form used in database normalization. Third normal form eliminates transitive dependencies of non-key attributes on the primary key.

3NF is strictly weaker than BCNF. The difference is that 3NF permits a non-trivial FD when is prime, even if is not a super key. BCNF does not allow this exception.

The advantage of 3NF over BCNF is that it is always possible to find a decomposition into 3NF that is both loseless and dependency-preserving, which is not always achievable for BCNF.

Definition

A schema is in third normal form if for every non-trivial functional dependency (where is a single attribute) at least one of the following holds:

• is a super key.
• is a prime attribute (i.e. is a member of some candidate key).

Equivalently, a schema is in 3NF if it is in 2NF and no non-prime attribute is transitively dependent on any candidate key.

A transitive dependency exists when and , where is not a super key and is a non-prime attribute. In this case is a transitive dependency through .

Example

Consider a schema Student(StudentID, Department, DepartmentHead) with the following functional dependencies:

• StudentID Department
• Department DepartmentHead

The only candidate key is {StudentID}.

This schema is in 2NF (the key is a single attribute, so partial dependencies are impossible), but it is not in 3NF because DepartmentHead is transitively dependent on StudentID through Department:

Here Department DepartmentHead violates 3NF because Department is not a super key and DepartmentHead is not a prime attribute.

To bring it into 3NF, we decompose into:

• Student(StudentID, Department)
• Department(Department, DepartmentHead)

Boyce-Codd normal form is a normal form used in database normalization and is a slightly stricter version of 3NF. Boyce-Codd normal form removes all redundancies based on functional dependence.

Definition

If a schema is in Boyce-Codd normal form all of it's functional dependencies X Y satisfy at least one of the following conditions:

• X Y satisfies reflexivity (Y X).
• X is a super key for the schema.

If a relational schema is in BCNF, then it is automatically also in 3NF because BCNF is a stricter form of 3NF.

Example

Consider a table Address with the following attributes

• HouseNumber
• Street
• City
• Province
• PostalCode

and the following functional dependencies

• HouseNumber, Street, PostalCode → City
• HouseNumber, Street, PostalCode → Province
• PostalCode → City
• PostalCode → Province

Is Address in BCNF? Justify why or why not and if it isn't decompose it such that it is.

Address is not in BCNF.

The candidate key is {HouseNumber, Street, PostalCode} (its closure yields all attributes). The dependencies PostalCode → City and PostalCode → Province violate BCNF because PostalCode alone is not a super key for Address.

To bring it into BCNF, we decompose using the violating dependency PostalCode → City, Province:

• PostalArea(PostalCode, City, Province): Here PostalCode is a super key, so all functional dependencies satisfied.
• Address(HouseNumber, Street, PostalCode): No non-trivial functional dependencies remain that violate BCNF.

This decomposition is loseless because the common attribute PostalCode is a super key for PostalArea.

Relational algebra is a procedural query language that defines a set of operations on relations. Each operation takes one or more relations as input and produces a new relation as output. This closure property means operations can be composed arbitrarily. Relational algebra serves as the theoretical foundation for query languages such as Structured Query Language.

Fundamental Operations

The six fundamental operations are sufficient to express any relational algebra query. All other operations can be derived from these.

Selection ()

Selects tuples from a relation that satisfy a given predicate.

where is a boolean predicate over attributes.

Example: returns all students older than 21.

Projection ()

Selects specified attributes from a relation, removing duplicates from the result.

Example: returns only the name and department of each employee.

Union ()

Returns all tuples that appear in either of two union-compatible relations.

Requires and to have the same arity and domain-compatible attributes.

Set Difference ()

Returns all tuples in the first relation that are not in the second.

Cartesian Product ()

Combines every tuple of one relation with every tuple of another.

where denotes the concatenation of the two tuples.

Rename ()

Renames either the relation or its attributes.

renames relation to with attributes renamed to .

Derived Operations

These operations can be expressed in terms of the fundamental operations but are used so frequently that they have their own notation.

Intersection ()

Returns tuples present in both relations.

Natural Join ()

Combines tuples from two relations that agree on all common attributes, then projects out the duplicate columns. The natural join is central to the theory of lossless-join decomposition.

Division ()

Returns tuples in that are associated with every tuple in . Useful for "for all" type queries.

Assignment ()

Assigns the result of a relational algebra expression to a temporary relation variable. This is purely notational convenience for breaking complex expressions into steps.

Properties

Selection is idempotent: .