Re: The wisdom of the object mentors (Was: Searching OO Associations with RDBMS Persistence Models)
Date: 2 Jun 2006 13:47:31 -0700
Message-ID: <1149281251.119519.18100_at_i40g2000cwc.googlegroups.com>
Cimode wrote:
> Table Definition
> > ROOM: room_number(PK natural int)
> > ROOM_RESERVATION: reservationid(PK surrogate int), reservation_client(FK int on CLIENT), reservation_roomnumber(FK int on ROOM), reservation_startdate(datetime), reservation_enddate(datetime)
> > CLIENT: name
> > No room should be occupied at the same time.
This is "complex constraint". I have the whole chapter about them. Here is the section about overlapping intervals.
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 don't intersect with each other . This definition, however, isn't very useful in our situation, since we have to formulate the intervals disjoint condition in terms of intervals boundaries.
Ones more, we begin rephrasing the constraint 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! Interval overlapping
condition has to be symmetric with respect to both intervals, while the
formal statement that we wrote doesn't look symmetric at all. Indeed,
what if interval [head2,tail2] covers [head1,tail1]? Then head2 is not
between head1 and tail1, and yet intervals do overlap. This
non-symmetry is illusory, however.
Figure 4.3: Overlapping intervals always have the head of one interval bounded between the ends of the other interval.
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)
We see 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 our implementation. Could i1 and i2 be the same interval? We have to add one more predicate 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, we could have used asymmetric join condition, and consider each pair of intervals once only. We define a total order among all the intervals so that for each pair of intervals i1 and i2 either i1 precedes i2, or i2 precedes i1. Lexicographical order i2.head < i1.head or i2.head = i1.head and i2.tail < i1.tail is a total order. Then, we can redefine the constraint as follows: Consider all the pairs of intervals such that [head1,tail1] precedes [head2,tail2]. They overlap whenever head2 is less than or equal to tail1. Again, no overlapping intervals are allowed. Formally,
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)
Received on Fri Jun 02 2006 - 22:47:31 CEST