Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: The wisdom of the object mentors (Was: Searching OO Associations with RDBMS Persistence Models)

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

From: <vadimtro_at_gmail.com>
Date: 2 Jun 2006 13:47:31 -0700
Message-ID: <1149281251.119519.18100@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 - 15:47:31 CDT

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US