Functional Dependencies¶
If for any given value of x there is only one value for y, or none, then y is functionally dependent on x.
In other words, a given value for x points to a certain value for y. This is written as
x → y
Note that different values of x can point to the same value y; but a given value of x cannot point to more than one value for y.
In the following table some data about suppliers is stored:
- each suppliers is identified by an ID
- a supplier is located in a city
- the status is an attribute of the supplier; however, it is actually a size code for the city
ID | Name | City | Status |
---|---|---|---|
1 | Smith | New York | 3 |
2 | Jones | New York | 3 |
3 | Black | Los Angeles | 3 |
4 | Brown | Denver | 2 |
5 | White | Denver | 2 |
6 | Green | Salem | 1 |
For the table above we have ID → NAME, STATUS, CITY and CITY → STATUS
When we look at functional dependencies, we distinguish between:
(a) the value of a relation or table at some point in time
(b) the set of all possible values of a relation
We are usually interested in (b).
Functional dependencies are fundamental for practical applications. A good table design helps to automatically enforce functional dependencies.
Deriving Functional Dependencies¶
Given a set of functional dependencies we can derive further FDs that must also hold, e.g. given
ID → NAME, STATUS, CITY
we can derive (among others):
- ID → NAME
- ID → NAME, STATUS
- ID → STATUS, CITY
Trivial Dependencies¶
Trivial Dependencies: e.g. ID → ID
A FD is trivial if the right-hand side is a subset of the left-hand side.
Armstrong Axioms¶
These axioms give us a set of rules to manipulate functional dependencies.
Let A, B, C arbitrary subsets of attributes of relation R, and denote AB the union of A and B.
Reflexivity: if B is a subset of A, then A → B
Augmentation: if A → B, then AC → BC
Transitivity: if A → B and B → C, then A → C
First rule = definition of trivial FD
Rules are complete: all implied FDs can be derived
Rules are sound: no additional FDs (not implied by S) can be so derived
Several more rules can be derived to simplify the practical task of manipulating FDs:
Decomposition: if A → BC, then A → B and A → C
Union: if A → B and A → C, then A → BC
Composition: if A → B and C → D, then AC → BD
Self-determination: A → A
Example¶
A → BC, B → E, CD → EF
E.g. project management: A EMPID, B DEPID, C MGR, D PROJID, E DEPNAME, F PERCTIME
Show: AD → F
In other words, show that in this application the percentage of time worked on a project is determined by employee and project.
- A → BC
- A → C (decomposition)
- AD → CD (augmentation)
- CD → EF
- AD → EF (transitivity)
- AD → F (decomposition)
The functional dependency AD → F can be derived with a suitable choice of operations.
Exercise¶
bc → a, de → c, a → bcde
Show that bc → d
Integrity¶
Ensure that the data is correct.
This is one of the main benefits of using a relational database; however, it does not happen automatically. We have to design our tables properly.
Constraints¶
These rules restrict the data that can be stored. If an attempt is made to violate such a rule, the DB systems responds with an error message. State Constraints
These type of constraints are widely supported by relational DB systems.
Type and values of individual Attributes, e.g.
- WEIGHT >= 0.0
- STATUS >= 1 and STATUS <= 100
Constraints on a Relation
- unique SID
- no supplier with CITY = 'London' and STATUS != 20
Constraints on the whole Database, e.g.
- no supplier with STATUS < 20 (in relation S) and QTY > 500 (in relation SP)
Relation Predicate¶
Logical AND of all relation constraints
Golden Rule¶
No update operation may leave any relation in a state violating its predicate
Transition Constraints¶
These type of constraints are typically not supported by the DB system out of the box, and have to be implemented by application logic i.e. we must program them.
Example: relationship status
Valid transitions
- Single to Married
- Married to Divorced
- Married to Widowed
Not valid
- Single to Widowed
- Single to Divorced
- Widowed to Divorced
Keys¶
When functional dependencies have been identified the next step is to define keys for relations.
Candidate Key¶
A candidate key K for a given relation is a set of attributes with
- Uniqueness: no distinct tuples with same value for K
- Irreducibility: no subset of K has Uniqueness
Every relation has at least one candidate key: if we cannot find any subset of attributes that form a candidate key we can use the complete set of attributes.
Note that strictly speaking this does not hold for tables, since a table can contain multiple identical rows; however, we will assume that our tables do not contain multiple identical rows.
In SQL we can define a primary key for a table, e.g. the ID in the suppliers table above. The consequence is that we cannot have two suppliers with the same ID.
If there is only one candidate key we will usually choose it for the primary key.
In case of more than one candidate key: choose one as primary key, the others are alternate keys
Superkey¶
A superkey is unique, but not necessarily irreducible
It follows that every candidate key is also a superkey, but not vice versa.
Foreign Key¶
A foreign key is a set of attributes F in relation B, where
- there is another relation A with candidate key C
- each value of F in B is identical to the value of C in some tuple in A
The value of F is a reference to the tuple containing C.
Example: we have two tables for customers and orders, and orders must refer to existing customers
- table CUST contains data about our customers
- table ORDR records the orders received
- each value of ORDR.CUST must be equal to an existing value of CUST.ID
In such situations the customer table is often called the parent or master, while the order table is the child or detail: the child depends on the parent.
Referential Integrity¶
Ensure valid foreign key values.
SQL options¶
in the CREATE TABLE statement:
PRIMARY KEY implies NOT NULL i.e. must have a value
UNIQUE can be NULL i.e. without value, not practical for identifiers
REFERENCES A(C)
- foreign key, this column references column C in table A
- optional: ON DELETE
- RESTRICT to cases without matching tuples
- CASCADE delete matching tuples
- SET NULL not a contradiction to definition since NULL is not a value
Example: Supplier and Parts¶
We want to keep track of our suppliers and record which supplier deliver which parts. We put the data about the suppliers in table S and the parts data in table P. Since we get certain parts from certain suppliers, we record that data in another table SP.
%load_ext sql
The sql extension is already loaded. To reload it, use: %reload_ext sql
We create a DB for this example:
%sql sqlite:///suppliers.db
The following is specific to SQLite: If we want foreign keys enabled we need to use the PRAGMA statement below; otherwise, foreign key constraints can be entered (as part of a CREATE TABLE statement), but they will not be enforced.
%%sql
PRAGMA foreign_keys = ON;
* sqlite:///suppliers.db Done.
[]
To make sure that all the code in this notebook can be run repeatedly from top to bottom we drop the tables if they already exist.
We will enforce referential integrity i.e. data in SP relies on data in S and P; in other words, SP is the child, while S and P are the parents.
Because of referential integrity, and the fact that we want to be able to run all the code in this notebook repeatedly, when the tables already exist, we must delete the tables in the proper order: first the children/details, then the parents/masters.
%%sql
drop table if exists SP;
drop table if exists S;
drop table if exists P;
* sqlite:///suppliers.db Done. Done. Done.
[]
Now we create out supplier table:
- The supplier ID is the identifying attribute.
- Given a value for ID we always find one supplier, or none; never more than one.
- Because of the PRIMARY KEY definition the DB will ensure this constraint.
- If we try to enter a supplier with an ID that already exists the DB will respond with an error message.
%%sql
create table S (
ID int primary key,
NAME varchar(20),
STATUS numeric(5),
CITY varchar(20)
);
* sqlite:///suppliers.db Done.
[]
The table exists and is empty. We fill it with some data.
%%sql
insert into S values (1, 'Smith', 3, 'New York');
insert into S values (2, 'Jones', 3, 'New York');
insert into S values (3, 'Black', 3, 'Los Angeles');
insert into S values (4, 'Brown', 2, 'Denver');
insert into S values (5, 'White', 2, 'Denver');
insert into S values (6, 'Green', 1, 'Salem');
* sqlite:///suppliers.db 1 rows affected. 1 rows affected. 1 rows affected. 1 rows affected. 1 rows affected. 1 rows affected.
[]
To make sure that this actually worked we generate a list of the records in the table.
%%sql
select * from S;
* sqlite:///suppliers.db Done.
ID | NAME | STATUS | CITY |
---|---|---|---|
1 | Smith | 3 | New York |
2 | Jones | 3 | New York |
3 | Black | 3 | Los Angeles |
4 | Brown | 2 | Denver |
5 | White | 2 | Denver |
6 | Green | 1 | Salem |
In the same fashion we create a table for some parts. Again the ID identifies the part, therefore we define it as the primary key.
%%sql
create table P (
ID int primary key,
NAME varchar(20),
COLOR varchar(20),
WEIGHT numeric(5,1)
);
* sqlite:///suppliers.db Done.
[]
Again, insert some data and check the contents of the table:
%%sql
insert into P values (1, 'Nail', 'Gray', 12);
insert into P values (2, 'Bolt', 'Black', 17);
insert into P values (3, 'Screw', 'Gray', 17);
insert into P values (4, 'Screw', 'Silver', 14);
insert into P values (5, 'Hub', 'Silver', 12);
insert into P values (6, 'Cog', 'Gray', 19);
select * from P;
* sqlite:///suppliers.db 1 rows affected. 1 rows affected. 1 rows affected. 1 rows affected. 1 rows affected. 1 rows affected. Done.
ID | NAME | COLOR | WEIGHT |
---|---|---|---|
1 | Nail | Gray | 12 |
2 | Bolt | Black | 17 |
3 | Screw | Gray | 17 |
4 | Screw | Silver | 14 |
5 | Hub | Silver | 12 |
6 | Cog | Gray | 19 |
In this example, we get parts from various suppliers. Not all suppliers deliver all parts. The following table SP allows us to deal with every possible situation:
- a supplier delivers all parts
- a supplier delivers some parts
- a supplier delivers no parts (no entry in the table)
Similar for the parts; if a part is delivered by no supplier, it has no entry in the SP table.
We want to ensure referential integrity:
- Values for supplier ID must be present in table S, and
- values for part ID must be present in table P.
- Otherwise, the DB system will respond with an error message.
Because of the REFERENCES definitions the DB will enforce these constraints:
%%sql
create table SP (
SID int references S(ID),
PID int references P(ID),
QTY numeric(6));
* sqlite:///suppliers.db Done.
[]
Now we can insert sensible values:
- supplier IDs must exist in table S
- part IDs must exist in table P
%%sql
insert into SP values (1, 1, 300);
insert into SP values (1, 2, 200);
insert into SP values (1, 3, 400);
insert into SP values (1, 4, 200);
insert into SP values (1, 5, 100);
insert into SP values (1, 6, 100);
insert into SP values (2, 1, 300);
insert into SP values (2, 2, 400);
insert into SP values (3, 2, 200);
insert into SP values (4, 2, 200);
insert into SP values (4, 4, 300);
insert into SP values (4, 5, 500);
select * from SP;
* sqlite:///suppliers.db 1 rows affected. 1 rows affected. 1 rows affected. 1 rows affected. 1 rows affected. 1 rows affected. 1 rows affected. 1 rows affected. 1 rows affected. 1 rows affected. 1 rows affected. 1 rows affected. Done.
SID | PID | QTY |
---|---|---|
1 | 1 | 300 |
1 | 2 | 200 |
1 | 3 | 400 |
1 | 4 | 200 |
1 | 5 | 100 |
1 | 6 | 100 |
2 | 1 | 300 |
2 | 2 | 400 |
3 | 2 | 200 |
4 | 2 | 200 |
4 | 4 | 300 |
4 | 5 | 500 |
☆ Answer the following questions by looking at the data.
- Which suppliers deliver all parts?
- Which suppliers deliver no parts?
- Which parts are delivered by all suppliers?
- Which parts are delivered by no suppliers?
Which of these questions could be answered easily by using an operation from relational algebra?
The beauty of Jupyter notebooks is that they support experimentation in a straight-forward fashion. Feel free to create more tables for subjects of your interest, and see what kind of information they can store.
Views¶
A view is a named relational expression, from a practical point very similar to a defined function without parameters in programming languages.
%%sql
drop view if exists GS;
create view GS as select id, status, city from S where status > 1;
* sqlite:///suppliers.db Done. Done.
[]
The view can be used in select statements just like a table:
%%sql
select * from GS;
* sqlite:///suppliers.db Done.
ID | STATUS | CITY |
---|---|---|
1 | 3 | New York |
2 | 3 | New York |
3 | 3 | Los Angeles |
4 | 2 | Denver |
5 | 2 | Denver |
Advantages of Views
- Security: force access through view, hide data
- Shorthand, macro
- Different users see same data in different ways
- Logical data independence
Multi-user DB systems typically let us define permissions for individual tables and views, which allows us to implement various schemes for security and user roles; views come in very handy in such an environment.
☆ Logical data independence¶
Immunity of users and programs to changes in the logical structure of the database (conceptual level)
- Growth
- new attributes
- new relations
- Restructuring
- E.g. split relation in two and provide view instead
- Select should work
- Expect problems with updates
Catalog Tables¶
When everything in a relational DB system is stored in tables, the data on which users and tables exist is also stored in tables: the catalog tables. They contain Metadata i.e. data about data:
- information about tables and their columns
- optimizer information (indexes, physical storage structures, ..)
- security constraints
This is also stored in database tables, the catalog tables. Therefore can be queried in the same form as user tables, using SQL
With the help of these meta-tables the DB system allows for changing the structure of user tables, even when they already contain data, e.g. to add a column:
ALTER TABLE table_name ADD COLUMN column_definition ;
SQLite takes a fairly unusual approach to this topic by storing the SQL statement that created the object, rather than the structural information on columns and their data types. Because of this, the ALTER TABLE command is severly limited in SQLite.
%%sql
select * from sqlite_master;
* sqlite:///suppliers.db Done.
type | name | tbl_name | rootpage | sql |
---|---|---|---|---|
table | S | S | 2 | CREATE TABLE S ( ID int primary key, NAME varchar(20), STATUS numeric(5), CITY varchar(20) ) |
index | sqlite_autoindex_S_1 | S | 3 | None |
table | P | P | 4 | CREATE TABLE P ( ID int primary key, NAME varchar(20), COLOR varchar(20), WEIGHT numeric(5,1) ) |
index | sqlite_autoindex_P_1 | P | 5 | None |
table | SP | SP | 6 | CREATE TABLE SP ( SID int references S(ID), PID int references P(ID), QTY numeric(6)) |
view | GS | GS | 0 | CREATE VIEW GS as select id, status, city from S where status > 1 |
For comparison, Postgres uses a separate catalog table to store information on the columns of user tables. This allows for the full range of ALTER TABLE commands, and makes it easy to e.g. query the names of all numeric columns:
Postgres:
SELECT table_name,column_name FROM information_schema.columns WHERE data_type = 'numeric';
table_name | column_name |
---|---|
p | weight |
s | status |
sp | qty |
Exercises¶
- Create the S, P, and SP tables in your own notebook.
- Experiment with various INSERT operations and test if the DB actually ensures all constraints.
- Create some views
Create some more tables on a topic of your interest, and fill them with some data, such as
chess club: each club has a number of players, clubs meet on certain dates for tournaments, games player have winners and losers, how does this affect the rating of players
hunting trips: which animals can be shot when and where, and how much does it cost; which trips provide for certain elements, such as specific types of animals and season
classical music: which recordings exist of which pieces, written by which composer, who are the participating interpreters, with roles depending on the work
Create some views on your data that help with various aspects, such as user roles