# Re: The wisdom of the object mentors (Was: Searching OO Associations with RDBMS Persistence Models)

Date: 2 Jun 2006 14:36:47 -0700

Message-ID: <1149284207.265913.251110_at_c74g2000cwc.googlegroups.com>

<< This is "complex constraint". I have the whole chapter about them.
Here

is the section about overlapping intervals.>>Complex maybe but
nevertheless very common.

Several solutions have been proposed but only at applicative level
(VIEWS, PROCEDURES, TRIGGERS) but none satisfactory at data definition
level because the ASSERTION SQL statement has not been implemented. I
specified this example of constraint to illustrate one current strong
limitation of SQL . Thank you for bringing some insight (I will check
your solution tomorrow). (in fact, and you probably know the problem
gets much worse when you add additional conditions such as adding a
delay, which I spared MIkito to do)...

vadimtro_at_gmail.com wrote:

*> 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 - 23:36:47 CEST