

Disjoint Sets
SQL Tips by Donald Burleson 
Enforcing that the
two tables have no common records is a very common practical
problem. Consider a typical ObjectOriented design scenario where
the Employee type has two subtypes: FullTimeEmp and
PartTimeEmp. On the database side, suppose that there are only
two tables: FullTimeEmp and PartTimeEmp. What should
be done to enforce the uniqueness of an employee id?
Certainly, both FullTimeEmp.id and PartTimeEmp.id can
be declared to be unique, but how do we guarantee that there is no
employee, who is both full time and part time? These sets have to be
disjointed:
CREATE
MATERIALIZED VIEW fullTime_intersect_partTime
select id
from FullTimeEmp
intersect
select id
from PartTimeEmp
ALTER TABLE
fullTime_intersect_partTime
ADD
CONSTRAINT disjointClasses CHECK(id is null)
There is another,
more straightforward, but somewhat cumbersome way to approach this
problem. Like any other constraint, a unique key can be enforced via
a materialized view as well. Let's start with the smaller and easier
task of defining FullTimeEmp.id unique key. Suppose that
FullTimeEmp has two more columns: name and startedAt.
Again, we begin rephrasing the constraint as an impossible
condition:
The two employee records e1 and e2 are
contradictory whenever e1.id = e2.id, and yet either e1.name ≠
e2.name or e1.startedAt ≠ e2.startedAt. No contradictory employee
records are allowed.
It easy to express
this constraint formally:
CREATE
MATERIALIZED VIEW contradictoryEmployees
select
e1.id id from FullTimeEmp e1, FullTimeEmp e2
where e1.id
= e2.id and (
e1.name <> e2.name or e1.startedAt <> e2.startedAt
)
ALTER TABLE
fullTime_intersect_partTime
ADD
CONSTRAINT disjointClasses CHECK(id is null)
It is obvious that
the number of inequality comparisons would grow with the number of
columns in the table. This is why I referred to this approach as
cumbersome. Some RDBMS implementations introduce a ROWID
pseudo column, which is guaranteed to be unique. This allows
comparing ROWIDs instead of actual values:
CREATE
MATERIALIZED VIEW contradictoryEmployees
select
e1.id id from FullTimeEmp e1, FullTimeEmp e2
where e1.id
= e2.id and e1.rowid <> e2.rowid
ALTER TABLE
fullTime_intersect_partTime
ADD
CONSTRAINT disjointClasses CHECK(id is null)
Without ROWIDs
the constraint is actually weaker than a unique key, as it cannot
distinguish duplicate records. Duplicate records do not exist in set
semantics, but SQL operates with bags. One extra nested materialized
view is needed to exclude duplicates.
The final solution
is only one step away. Simply declare the unique key constraint on a
materialized view, which is the union of FullTimeEmp and
PartTimeEmp tables. However, the union is not defined on
tables which are incompatible,
and in fact, it is easy to imagine that tables corresponding to
different subclasses have different attributes. The concern about
union not being defined for incompatible relations has already been
addressed in the previous chapter, where the outer union was
introduced.
There is another
reason why this solution is less elegant than the one with disjoint
set constraint. The outer join view is not empty, which implies
storage overhead. Although in principle the RDBMS engine could
flatten nested materialized views, do not expect this to be
implemented anytime soon.
Disjoint Intervals
Consider a list of
intervals:
table
Intervals (
head
integer,
tail
integer
)
We would like to
declare these intervals as mutually disjoint.
In math, disjoint
intervals are defined as sets that do not intersect with each other.
This definition, however, is not very useful in this situation since
the intervals disjoint condition must be formulated in terms of
intervals boundaries.
Once more the
constraint is rephrased as an impossible condition:
The intervals [head1,tail1] and
[head2,tail2] overlap whenever head2 is between head1 and tail1. No
overlapping intervals are allowed.
Wait a minute,
something must be wrong here! The interval overlapping condition has
to be symmetric with respect to both intervals, but the formal
statement written does not look symmetric at all. Indeed, what if
interval [head2,tail2] covers [head1,tail1]? Then
head2 is not between head1 and tail1, and yet the
intervals do overlap. This nonsymmetry is illusory, however.
Let's write the
constraint formally:
CREATE
MATERIALIZED VIEW overlapping_intervals
select
i1.head h
from
intervals i1, intervals i2
where
i2.head between i1.head and i1.tail
ALTER TABLE
overlapping_intervals
ADD
CONSTRAINT no_overlapping_intervals CHECK(h is null)
This query shows
that i1 and i2 iterate over the set of all intervals,
each pair of intervals [a,b] and [c,d] in the set
would be considered twice: first time when i1.head = a,
i1.tail = b, i2.head = c, i2.tail = d, and second
time when i1.head = c, i1.tail = d, i2.head = a,
i2.tail = b. This reasoning, however, exposes a bug in the
implementation. Could i1 and i2 be the same interval?
One more predicate must be added that excludes this possibility:
CREATE
MATERIALIZED VIEW overlapping_intervals
select
i1.head h
from
intervals i1, intervals i2
where
i2.head between i1.head and i1.tail
and
(i2.head <> i1.head or i2.tail <> i1.tail)
ALTER TABLE
overlapping_intervals
ADD
CONSTRAINT no_overlapping_intervals CHECK(h is null)
Alternatively, an
asymmetric join condition could have been used, and each pair of
intervals only considered once. A
total order
is defined among all the intervals so that for each pair of
intervals i1 and i2 either i1
precedes i2,
or i2 precedes i1. The lexicographical order
comparison predicate i2.head < i1.head or (i2.head = i1.head and
i2.tail < i1.tail) defines a total order. The constraint can now
be written as follows:
Consider all the
pairs of intervals such that [head_{1},tail_{1}]
precedes [head_{2},tail_{2}]. They overlap whenever
head_{2} is less than or equal to tail_{1}. Again,
no overlapping intervals are allowed.
And formally as:
CREATE
MATERIALIZED VIEW overlapping_intervals
select
i1.head h
from
intervals i1, intervals i2
where
(i2.head < i1.head or
i2.head = i1.head and i2.tail < i1.tail)
and
i2.head <= i1.tail
ALTER TABLE
overlapping_intervals
ADD
CONSTRAINT no_overlapping_intervals CHECK(h is null)