in

The ORM Foundation

Get the facts!

Exclusion constraints

Last post 03-19-2014 12:29 by Ken Evans. 41 replies.
Page 1 of 3 (42 items) 1 2 3 Next >
Sort Posts: Previous Next
  • 03-14-2014 15:58

    Exclusion constraints

    Postgresql since version 9.0, supports the notion of exclusion constraints, which are a generalization of uniqueness constraints. Exclusion constraints are particularly helpful when dealing with datatypes like ranges, where equality is not necessarily the most helpful operator. 

    With exclusion constraints one can state that a certain time interval may not overlap with another time interval. 

    I was wondering whether ORM is able to state similar constraints and if not, whether there is an interest in adding such a feature.

  • 03-14-2014 19:43 In reply to

    Re: Exclusion constraints

    Hello Niels,

    The ORM specification includes exclusion constraints. (By "ORM specification", I'm referring to the explanations in the 2008 book written by Terry & Tony.)

    However, not all the features mentioned in the book have yet been implemented in the NORMA tool. In addition, the DDL generators in NORMA are at different stages of evolution. So you might try building a model using the exclusion constraints that you want to use and then comparing the DDL that NORMA generates for  Postgresql with the DDL that NORMA generates for SQL Server.

    Matt and Terry have been informed and one of them should respond in the near future with a more precise technical comment.

    If you are not yet familiar with NORMA, you could post some examples of what you have in mind and I will show you how they can be expressed in ORM.

    Ken 

     

     

  • 03-15-2014 9:42 In reply to

    Re: Exclusion constraints

    Hello Ken,

    Thank you for your quick response to my question.

    Back in the 1990s, I worked for a company where we used Infomodeller for our database design, and I very much liked the approach. Ever since I have used the schema techniques on a more informal basis (white board drawing, pen and paper design), but haven't yet caught up with the most recent ORM tools. As a result I am unfamiliar with NORMA. Can you recommend the cheapest Visual Studio version that fully supports NORMA? I won't be using VS for anything else, since all my development takes place in Eclipse, so I don't want to spend more money than necessary.

    A typical use case for the exclusion constraints of Postgresql would be that of scheduling a classroom.

    Suppose we have classrooms and teachers and we want to register the reservations of each class room by each teacher.

     We end up with two objects (teacher and class room) and a ternary relation (class room reservation) consisting of:

    • teacher
    • class room
    • reservation datetime range

    In this case we have two exclusion constaints:

    • no two classroom reservations can exist with the same teacher and overlapping reservation datetime range
    • no two classroom reservations can exist with the same classroom and overlapping reservation datetime range
    The Postgresql DDL definition would look like this:

    CREATE TABLE classroom (
        id integer NOT NULL
    );

    CREATE TABLE teacher (
        id integer NOT NULL
    );

    CREATE TABLE classroom_reservation (
        teacher integer NOT NULL,
        classroom integer NOT NULL,
        reservation_period tstzrange NOT NULL --tstzrange is a timestamp with timezone range datatype
    );


    ALTER TABLE ONLY classroom
        ADD CONSTRAINT classroom_pk PRIMARY KEY (id);


    ALTER TABLE ONLY teacher
        ADD CONSTRAINT teacher_pk PRIMARY KEY (id);
     
    ALTER TABLE ONLY classroom_reservation
        ADD CONSTRAINT teacher_reservation_period_ec EXCLUDE USING gist (teacher WITH =, reservation_period WITH &&);
     
    ALTER TABLE ONLY classroom_reservation
        ADD CONSTRAINT classroom_reservation_period_ec EXCLUDE USING gist (classroom WITH =, reservation_period WITH &&);

    -- End definition
     
    The first exclude constraints tells us that we have to exclude a new classroom_reservation record when there is an existing record in the classroom_reservation table, where the binary operation "=" performed on the teacher column of the two records yields true, and the binary operator "&&" (overlap on ranges) yields true when performed on the classroom_reservation_period column of the two records.
     
    The second exclude constraint is analogous, except that it is for for the pair classroom/reservation_period.
     
    I would be interested to learn how this can be expressed in ORM.
     
    Niels 
  • 03-15-2014 16:26 In reply to

    Re: Exclusion constraints

     Hello Niels,

    I'm working on a model for your "teacher, classroom,booking" problem and I hope to have it done by sometime tomorrow.

    In the meantime, I found several offers for Visual Studio on Ebay.co.uk. Many of them are in the £50 to £100 range.
    Matt has said that there are no functional differences between the various versions of NORMA in the library so I suggest that you look on Ebay and choose the most recent version that is at an acceptable price point for you.

    I use VS 2013 but I also use VS for lots of other things as well. VS2013 has a better integration of SQL Server than any of the other versions but if you are using Postgresql then I suppose you wont care about that.

    Ken

     

  • 03-15-2014 19:12 In reply to

    Re: Exclusion constraints

     Hello Ken

    I am looking forward to see what you are brewing, and thanks for the information about VS. 

    Niels 

     

  • 03-16-2014 9:05 In reply to

    Hi Niels,

    I have "brewed" a model that includes a bit more context than your example. Why? Well, I thought that a slightly bigger model would be more helpful in showing the relationship between ORM and PostgreSQL.

    I just put three files into the Library:

    1: The object-role model itself (a .orm file made with NORMA running in Visual Studio 2010) 

    2: A pdf that shows the objec-role model, a relational schema, some verbalization and the DDLfor PostgreSQL

    3: A verbalization of the complete model. This is in a .htm file that you can browse.

    You will find three files here  

     No doubt the first thing that you wil say is "Where are the exclusion constraints that I asked for?"

    Well, the way I approach modeling is to begin by looking at the facts and then making a model that seems to represent them.
    In your example, I solved the "overlapping times" problem by making a quaternary that only allows one reservation for each hour that each classroom is available. You can see an example of using the "HourSlot" idea on page 225 of Terry's book.

    Ken



  • 03-16-2014 11:52 In reply to

    Re: Exclusion constraints

    Hello Ken,

    Thank you for your example. I greatly appreciate the effort you put into answering my question.

    Let me start with a practical note: I get "Access denied. You do not have permissions to perform the requested action", when trying to download the files you created (I was logged on when trying to download). 

    Now to the model itself. It has a unicity constraint on person, classroom, date. Meaning, no person can book the same classroom more than once on the same day. What I wanted expressed, and maybe I wasn't completely clear, is that no person can make two reservations for the same time interval, and no two classrooms can be reserved for the same time interval.

    With the solution presented, a person can make reservations for all ten classrooms on the same day and within the same hourslot, but is not allowed to make a reservation to the classroom on the same day, but at different time slots. Also a classroom can be reserved by more than one person at the same time.

    Accepting the hourslot approach, I believe, there need to be two unicity constraints:

    • person, date, hourslot
    • classroom, date, hourslot 

    Now to the beef of the matter. The hourslot method works if reservations are made with an hourly granularity. If however we want to make a reservation of the classroom for two or more hours (not an uncommon situation, in my experience), we'd have to create separate reservations for each hourslot, This not only doesn't reflect reality, where we have one reservation, it also makes looking up the start and end of the reservation more cumbersome.

    The hourslot method also makes reservations of smaller granularity impossible. This may not necessarily be an issue when reserving classrooms, but there are other resource reservation situations imaginable, where such finer granularity is required. Of course we can replace hourslot with a more fine grained measure of time, but that only exacerbates the problems when we have to make reservations for longer stretches of time.

    Niels 

     

  • 03-16-2014 13:05 In reply to

    Re: Exclusion constraints

     Hello Niels,

    The nice thing about ORM is that it is really easy to change the model based on feedback from the people who have "the problem".
    I have always found it easier to start with a "straw man" model rather than from a blank sheet because this makes it much easier for people to see when a model does not express their requirements. 

    So here is a new model fragment with associated verbalization. Does that do what you want?

    You may have noticed that the model in the library is version 4 and the attached fragment is version 5.
    That's because initially I played about with various models that used StartTime, Duration and EndTime. where EndTime  was derived from the calculation "StartTime+Duration".   

    One problem I faced is that the public release of NORMA is not encoded with a "derivation rule" function so I tried to make a model using a version of NORMA that is available to anyone who downloads the public release.  

    As you say, the HourSlot method can easily be changed (for example) to a TwoHourSlot method, or a MinuteSlot method or to any other time duration.

    But there is another aspect to this. For example a security person might want to be able to reserve (aka "block") some combination of classrooms  e.g. "all classrooms on the second floor for a whole morning". This would mean that we would need fact types that expressed these needs.

    Ken

     


  • 03-16-2014 15:15 In reply to

    Re: Exclusion constraints

     Hi Ken,

    The model as it is now, comes much closer to the specification we started with, however it is not exactly what I was trying to accomplish.

    A great model should in principle be able to express all that is needed to derive the desired implementation. Whether that derivation is algorithmically implemented in a tool is a different issue.

    The model we have come up with so far, is what I would call a work-around. It is able to express some of the properties of the specification, but not all of them, and as a result a derivation of the database schema I gave earlier in this thread from this model is in principle impossible. 

    What we miss in the first place is a value type that is able to express ranges. Such a value type has operations single valued types don't have, such as: overlap, containment and adjacency. Without using a range value types, we may never come to a derivation of the schema given,

    Also, the unicity constraint is not general enough to express the specification since the only operation supported in a unicity constraint is equality, while the desired operator is overlap.

    These two aspects lead to a solution that is not optimal.

    The desired derivation is one where we can add reservations of any duration (with a granularity of micro-seconds) as single facts, while the model we have come up with so far, only allows us to add reservations of a fixed duration, having to add multiple facts when the duration is larger than the fixed grain chosen.

    Is it fair to say that exclusion constraints cannot be expressed in ORM in its current incarnation? (This is by no means meant as criticism. Sometimes models are able to express things that cannot yet be implemented, and sometimes things can be implemented that cannot yet be modeled.)

    Niels

  • 03-16-2014 15:33 In reply to

    Re: Exclusion constraints

     Niels,

    I agree that the time-slot approach is not generally suitable. The right way to handle your non-overlapping time constraint in ORM is unfortunately not possible with the freeware version, only with NORMA Pro. You need to use value comparison expressions to enforce the range (min1 >= max2 or max1 <= min2).

    Even NORMA Pro does not yet map these to SQL, either for Postgres nor any other SQL.

    In my Constellation Query Language (CQL, a plain-text rendering of ORM2) I plan to introduce temporal uniqueness constraints. Currently, uniqueness constraints are expressed with the phrase "at most one" or "exactly one", e.g. "Person is married to at most one Person (as Spouse)". The temporal form adds "at a time", which turns a binary fact type into a ternary: "Person is married to at most one Person (as Spouse) at a time". The selection of the data type for representing time is a mapping pragma. For more info on CQL, please refer to http://dataconstellation.com/ActiveFacts/.

  • 03-16-2014 17:01 In reply to

    Re: Exclusion constraints

    Hello Clifford,

    Forgive me my ignorance. I wasn't even aware of the existence of two separate versions of NORMA.

    Frankly, I am not necessarily enamoured with graphical notation only, so I don't necessarily care so much about a tool, as much as about the modelling language itself (its axioms, theorems etc.).

    My experience with Infomodeller, almost two decades ago was on one hand pleasant, since I liked the modelling capabilities, on the other hand I found the input methods time consuming. Sometimes textual input in a symbolic language works much faster than handling a GUI.

    I do like graphical notation when doing brainstorming, and it's great documentation when the model is final. In between those two phases of a project, I personally prefer a more algebraic approach.

    In short, I'd like to see ORM the language as separate from ORM the notation/tooling, and focus on the former. Unfortunately, I have not been able to find a true language specification. I take it Terry Halpin's book should be considered the language specification, although it aims to be something beyond just a specification.

    Your temporal example, is exactly what I want to use exclusion constraints for, to register facts with both a validity range (a fact is valid during a certain time interval) and a system range (the fact is stored during a certain time interval). As such, I find your CQL an interesting approach, although personally I would prefer a slightly more symbolic notation. The programmer in me likes to see arrows, brackets, operators etc. It makes a text easier on the eye, in my personal opinion.

    Is CQL a one-man endeavour, or is there a larger community involved in it?

    Niels 

  • 03-16-2014 18:11 In reply to

    Re: Exclusion constraints

    The ORM notation doesn't have a graphical way to represent complex constraints anyway, and NORMA Pro has a rather difficult editor for them. The verbalisation it provides is very nice, however, much more fluent than CQL provides. To some extent it's unavoidable that CQL is less fluent, since it's required to be machine-processable.

    You ask for ORM "the language" to be separate from the notation/tooling. This is the role of the metamodel. My metamodel was, I believe, the first complete published metamodel from an actual implementation. It's not perfect, but it does actually work. However, in the six intervening years, a lot of work by the FBM Working Group to producing a common shared metamodel for exchange of fact-based models, integrating ORM (with CQL) and NIAM and trying to also incorporate the other dialects. This metamodel is approaching its first release. I'm sure it will create a good deal of excitement, although it's still not sophisticated enough to express complex queries of constraints of the kind we're discussing here.

    The ActiveFacts project which produced CQL is open source, but I've had very few external contributions. In truth, I haven't worked hard enough to develop a community of users, because so much work always remains to be done that I feel the remaining limitations would create a support burden. It's time for that to change however, as I've successfully executed a number of highly complex commercial projects with the tool, so it can be used successfully. To engage with the core of CQL there's quite a conceptual learning curve, but to write new generators is quite simple, requiring familiarity with less than 5% of the overall codebase. My son (who's also a programmer) wrote the MySQL generator within two hours of his first exposure to the project. So it's definitely possible to contribute, or to bend CQL to your own needs.

    As far as an intermediate symbolic notation between ORM diagrams and plain text, I initially set out to create a Ruby DSL that supports fact-based modeling. The activefacts-api Ruby gem now fills that need. However, it's limited to binary fact types, has no instance verbalisation, and veers too close to an attribute-oriented form to be a good introduction to conceptual modeling using a fact-based approach. Simply put, it cannot yield the organisational communication advantages of a proper fact-oriented approach. I wanted to avoid the need for domain experts to learn any special symbols, or to install any software, and that's why CQL exists. I've found that it works well for that. I modelled the incredible complexity of "award allowances" for payroll under the Australian Industrial Awards system, entirely in CQL, and was able to validate the CQL with business payroll experts who have never been programmers nor exposed to modeling concepts. They were able to read the CQL themselves, statement by statement, and pass meaningful comment at each step. To my mind, that is the ultimate validation of my approach.

  • 03-16-2014 18:41 In reply to

    Re: Exclusion constraints

     NORMA doesn't yet provide graphical support for those two constraints. Nor does it directly support a temporal range data type.

    As discussed below, there are multiple ways (I show two ways) to model the basic scenario, but currently those constraints need to be added as textual constraints and implemented manually. 

    We added support for graphical value-comparison constraints a few months ago, but these are not sufficient to capture the two constraints under discussion.

    Model 1 Fact Types (role names shown in square brackets):

    F1: Teacher(.Nr) reserved ClassRoom(.Nr) for Period. -- Add UCs on the role-pairs for (teacher, period) and for (classroom, period) assuming these are desired.

    F2: Period started on DateTime [start]

    F3: Period ends on DateTime [end] 

    Use F2 and F3 to identify Period as a coreferenced entity type.

     

    Model 2 Fact Types (each is mandatory, and n:1):

    Reservation(.Nr) is by Teacher(.Nr).

    Reservation is for ClassRoom(.Nr).

    Reservation starts on DateTime.[start]

    Reservation ends on DateTime. [end]

    Instead of identifying a reservation by a reservation number (recommended), you could identify it by combining teacher, room and start. At any rate (teacher, room start) and (teacher, room. end) have external UCs so they determine a reservation..

    Add value comparison constraint: For each Reservation, start < end. (you can do this graphically)

    As an example, one of the two required constraints may be stated informally as  "No distinct reservations of a given classroom may non-trivially overlap in time" (if one reservation starts the instant the other ends, this is trivial overlap, which I will allow -- I'm ignoring finer points about discrete vs continuous time).

    This constraint may be formally specified in FORML as follows: 

    For each Reservation1, Reservation2 and Classroom

    if Reservation1 <> Reservation2 and Reservation1 is for that ClassRoom and Reservation2 is for that ClassRoom

    then (Reservation1.end <= Reservation2.start or Reservation1.start >= Reservation2.end) .

     We are currently working on extending NORMA to support such constraints and map them to implementation targets such as relational databases. But this is not yet done, so in the meantime I suggest adding the constraints as notes and implementing them manually. 

    Cheers

    Terry 

     

     

    .

  • 03-16-2014 19:13 In reply to

    Re: Exclusion constraints

    Thank you Terry,

    That completely answered my original question.

    Would it be feasible to have compound value types, such as range, point, line, circle, polygon etc., such that phrases like "Reservation1.end <= Reservation2.start or Reservation1.start >= Reservation2.end" can be replaced by something like Reservation1 does not overlap with Reservation2?

    Various relational database products have native support for compound datatypes, making the mapping from model to implementation easier.

    Having a value type range, would also help avoid the trivial overlap situations, by defining a range to be eg. left inclusive-right exclusive, or any other variation on that theme.

    Niels 

  • 03-16-2014 21:11 In reply to

    Re: Exclusion constraints

    Niels,

    "overlaps with" names a family of predicates that generate a derivable fact type for each of a number of data types (time interval, circle, etc), in just the same way that value comparison predicates (greater then, equal, etc) or arithmetic (addition, multiplication) generate fact types over numbers (e.g. "a = b+c" is an alternate reading for "b = a-c", etc). 

    I'd like to see all the fact types that are intrinsic to data types being explicitly modelled in the ORM metamodel, instead of just being lumped into a fixed algebraic capability of a tool. I've started down this path with CQL, but my data typing system is weak (rather: non-opinionated :)) and so I have not been able to complete this yet.  It seems that this capability would allow direct mapping to DBMS implementations where the appropriate features exist.

    Compound datatypes are like entity types, for example date (Y/M/D). ORM tools should allow literal values for such types, and should model the fact types that relate a date instance to a year, a month, and a day.

Page 1 of 3 (42 items) 1 2 3 Next >
© 2008-2014 The ORM Foundation: A UK not-for-profit organisation -------------- Terms of Service