Inclusion Dependencies in SQL

March 5, 2014

Constraints have always been under appreciated in database practice. Today we’ll focus on inclusion dependencies, which in SQL community are better known as foreign keys. Let’s start with an example borrowed from David Spivak’s work on categorical foundation of databases — the familiar Employees table

Employees = [empno mgr dept]
               1    3   10
               2    2   20
               3    4   10
               4    4   10
               5    4   10

together with constraint

“For every employee e, the manager of e works in the same department
that e works in.”

One may argue that this is not very realistic constraint. If an employee and his manager have to be in the same department, then an employee and his manager’s manager have to be in the same department as well. Then, by transitivity it follows that the entire hierarchy tree of employees must be in the same department. If hierarchy graph is disjoint (i.e. a forest of trees), then the department number is just a label distinguishing a connected component of hierarchy.

Yet, a business rule is just that: an [arbitrary] rule, which is silly to argue with. Let see if we can formally enforce it. For each pair (mgr,dept) there should exist a pair (emp,dept). That sounds like inclusion dependency, so one may be tempted to enforce it as a foreign key:

CREATE TABLE employees (
    empno INT, 
    mgr INT,
    dept INT,
    PRIMARY KEY (empno,dept) ,
    CONSTRAINT fk FOREIGN KEY fk (mgr,dept)
    REFERENCES employees (empno,dept)

So far, so good. However, the initial enthusiasm of discovering foreign keys referencing the same table hits the first snag:

insert into emps (empno,mgr,dpt) values(3,4,10);

SQL Error: Cannot add or update a child row: a foreign key constraint fails (`test`.`employees`, CONSTRAINT `fk` FOREIGN KEY (`mgr`, `dept`) REFERENCES `employees` (`empno`, `dept`) ON DELETE NO ACTION ON UPDATE NO ACTION)

A bug? Nope. Apparently, the constraint doesn’t allow to insert an employee before manager. The correct table update sequence should be like this:

insert into emps (empno,mgr,dpt) values(4,4,10);
insert into emps (empno,mgr,dpt) values(3,4,10);

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: