Introduction to the Relational Algebra

What, why & who for ?

This document essentially contains an introduction to the relational algebra that is implemented in SIRA_PRISE. Depending on your background, you may already have some or very extensive knowledge about the subject, in which case you probably do not need to read this document.

If, however, your knowledge of and about the Relational Model of Data was primarily/solely obtained through the usage of SQL-based systems, and terms such as "relvar", "relation" and "tuple" sound completely unfamiliar to you, then carefully studying this document is probably a sine qua non for you to understand and effectively use this new system you've got in your hands.

This introduction is subdivided in several parts : 

  • The first part, "Terminology", defines the components that lay the foundation for any relational database : type, value, tuple, relation, ...  It is rather mathematical in nature and may therefore seem to be a bit alienating ("What the hell do IT professionals need mathematics for ?"), but let me assure you that understanding this part really is relevant and really is needed for you to understand part two properly.
  • Part two, "Relational Algebra", offers a detailed definition and discussion of all the operators of the algebra, which is the part of the relational model that every database user employs in every single query he/she writes and/or executes.
  • Part two introduces the operators of the algebra, making abstraction of a very particular data type called the interval type. SIRA_PRISE offers support for interval types, and the third part, "The RA and interval types", introduces how the operators of the algebra behave when faced with relations that hold interval-typed attributes.

Terminology

You may have wondered, at some time, why "Relational databases" (and "Relational dbms's") are called how they are. You may have assumed that it must have had something to do with this thing called "Entity-Relationship modeling" that you may already have practiced at some point in your career. Your assumption was wrong. In fact, the first mention of the term "relational" in the context of data management even predates the invention of E/R modeling ... So where dóes the term come from ?

Well, the term comes from something that we have presumably all been taught about in our math classes, somewhere between the age of 10 and 20, that thing being the "relation". The Relational Model of Data (RM for short) is no more or less than a mechanism to represent data in general, and which has that same mathematical concept of a relation as its key building brick. Before digging into the details of the algebra, it is first necessary to define a couple of terms that are frequently used when talking about the RM. That is where we will start this introduction of the relational algebra.

  1. Set

    Lots of people collect things. Stamps, coins, rare books, art reproductions or even original art masterpieces, just name it and someone exists who collects it. You probably have spent some time in your life too, trying to build up some collection. If you have, doubtless that there have been some items that you have managed to collect more than once. It was problaby fun trading those "duplicates" with fellow collectors for items that you had not yet managed to collect. Well, a "collection" is a very fundamental concept in mathematics, one that is in fact needed to define what a "set" is.

    In mathematics, a "collection" is, loosely speaking, any possible gathering in any possible quantity of any possible things. The gathering of (chair, cloud, oak tree, chair) is a collection. Note that the collection has two chairs.

    Now, if a collection has the particular property that none of the items in the collection appear more than once, then we call this collection a "set". This property turns out to be a very useful and important one, and therefore sets, and set theory, are very important in mathematics. So important in fact that relational database technology could and would not even have been invented without them. Important enough also, to be repeated in bold :

    A set is a collection that does not contain duplicates.
    Something that does contain duplicates, is not a set.

  2. Type/Value

    1. Definition

      So {A,1,oak tree,patent} is a set. {A,patent,A} is not. Now, in the context of data management problems, which is what we're interested in, sets such as those are of course not very useful. In the context of data management, sets are mostly useful only if the items they contain are in some way "alike". In that context, we usually deal with sets that contain only numbers, only dates, or some such. Useful sets in data management are sets such as {Monday, Tuesday, Wednesday, Thursday, Friday} and {true, false}. Without attempting a formal and precise definition of the term, we can (and do) say that a Type is such a "useful" set. And a Value is one of the items contained in a Type. Which brings us to :

      A Type is a set of Values.

    2. Additional remarks

      In data management, we will often need to speak about, or refer to, such Types. For that reason, it is customary that all the Types we use are assigned a name. The type {Monday, Tuesday, Wednesday, Thursday, Friday}, e.g. could be assigned the name 'Weekdays'. The type {true, false}, e.g. could be assigned the name 'Boolean'. Such that we can say :

      A Type is a named set of Values.

      You might wonder at the mutual dependency in the definition here. A type is a set of values, and a value is an item in a type. In the end, that doesn't really define much, does it ? Shouldn't we have some other definition of what a 'Value' is ? Well, for the purpose of this introduction, that isn't really necessary. The reason for this is that the RM (and the algebra) can work with just any set of types. The RM does not "fall apart" if the set of integers is not defined as a type, nor does the algebra. (It would be difficult to build a useful database without that type, but that's another issue.) And the most important consequence is that this observation is equally valid "the other way round" : the RM does not stop you from defining whatever type you like. The RM gives you no answer to the question when or why something is a value, and when or why not. As far as the RM is concerned, a value is whatever you want it to be, and a type is whatever set you define it to be. It only depends on whether you have a useful purpose for the type or not. A set such as {Em, C, G, ...} might look pretty insane and useless to most readers, but a guitar player would certainly have some good uses for a type holding the guitar chords as values ...

  3. Cartesian product

    1. Definition

      Looking at our example types Weekday and Boolean, it's not difficult to see how one can "pick a value from the first type, then pick a value from the second one, then arrange those two picked values to form a pair.". One example of such a pair would be (Monday, false). There are 10 such pairs possible, and those 10 pairs can be gathered into a set. Such a set turns out to be a very important concept in mathematics too, so important in fact that the concept of such a set is given a name : the "Cartesian Product".

      The Cartesian product of two sets is the set of all possible pairs formed from the items in those two sets.

    2. Remarks

      The term "Cartesian product" is not often encountered in the world of RM. The reason for this will become clear in the next few sections. Nevertheless it is worthwhile to reiterate in a more informal manner : A Cartesian product is a set, and the things that we find in that set are "pairs of other things", and those "other things" are precisely the things that are part of one of the sets that were used to form the Cartesian product.

  4. Relation (Traditional mathematics version)

    1. Definition

      Traditional set theory then goes on to define the concept of a "Relation" :

      A Relation is a subset of a Cartesian product of two sets.

    2. Remarks

    3. Examples of such relations are then : {(Monday, false),(Monday, true)}, {}, {(Tuesday, false),(Thursday, true)}, ...

      Once again it is worthwhile to reiterate in a more informal manner : A Relation is a set, and the things that we find in that set are "pairs of other things", and those "other things" are precisely the things that are part of one of the sets that were used to form the Cartesian product of which the Relation happens to be a subset.

  5. Generalized product

    1. Definition

      Following this definition, a relation can be (and is indeed) defined as being a set of pairs. For the context of data management problems, this definition isn't so useful, however. Indeed, when recording data about our customers, sales, ..., we usually record a lot more things than just two. So for the specific purpose of data management, the concept of a relation had to be "adapted" somewhat ("generalised" is the correct word, actually) to cater for that problem. It is not difficult to see how this can be done : instead of "picking values from two types and arrange those", one can also "pick one value from each of any number of types, and arrange those". The set that is formed by gathering all possible such combinations, is no longer called the "Cartesian" product, but rather the "generalized" product :

      The generalized product of n types is the set of all possible combinations of values formed from those n types

    2. Additional Remarks

      The term "generalized product" is not often encountered in the RM world. It only serves as a step-up to the definition of what a Relation is in the RM world.

      Once again it is worthwhile to reiterate in a more informal manner : A Generalized Product is a set, and the things that we find in that set are "combinations of other things", and those "other things" are, precisely, the Values that are part of one of the Types that were used to form the Generalized Product.

      An important remark is to be made here. The generalized product is defined to be a set, specifically. And when defining a Type, it was said that a type is a set, and that the items that a type contains are called 'Values'. So the question could arise, if a generalized product is a set, and all it takes to be a type is to be a set of values, could we regard a generalized product as a type, and the items that the generalized product contains as values ? The answer to whether we can is obviously 'yes', but more important, is there any benefit in doing so ? This issue will be addressed when discussing a.o. the GROUP operator of the algebra, but it is worthwhile to remember already now :

      Each generalized product can be considered as a Type in its own right

  6. Relation (Relational Model Version)

    1. Definition

      The concept of a Relation can now be generalized as follows (and it is this definition that is the cornerstone of the RM - and thus of the algebra too) :

      A Relation is a subset of the generalized product of n types

    2. Additional Remarks

      Informally, this translates to "A Relation is a set, and the things that we find in that set are "combinations of other things", and those "other things" are, precisely, the Values that are part of one of the Types that were used to form the Generalized Product that the Relation happens to be a subset of.".

      It is also important to remember that, in the context of the Relational Model of Data, the word "Relation" always means the kind of set defined here, and not to the more "traditional" definition that we were/are usually taught in our math classes.

  7. Tuple

    1. Definition

    2. The items found in a Relation (RM version) are then "pairs" having three, or twenty, or in fact any number of values. The name "pair" of course then becomes somewhat inappropriate to label such things, and of course, it is also desirable to just have a term, preferably other than "combination of n Values", to use whenever we want to refer to these things that form a Relation. That term is "Tuple".

      A Tuple is one item of/in the generalized product of n types,

      A Tuple is a combination of values drawn from n types

    3. Additional Remarks

    4. First and foremost, we have already established that a generalized product can be considered as a type in its own right. Implying that the things that such a generalized product contains, are themselves 'values'. Given that we have just baptised these things as 'Tuples', we can conclude :

      A tuple is, itself too, a value.

      Given that a generalized product contains only tuples as its members, and given that a Relation was defined to be a subset of a generalized product, the following is obviously true :

      A Relation is a set of tuples (formed from n types)

  8. Application to data management

    By now, the question may rise, "How is all of this useful to the field of databases ?". The answer to this question is best illustrated by revisiting the previously given WeekDay/Boolean example. The "Generalized Product" as previously defined, when applied to the Weekday/Boolean example can be represented as follows :

    Monday true
    Monday false
    Tuesday true
    Tuesday false
    Wednesday true
    Wednesday false
    Thursday true
    Thursday false
    Friday true
    Friday false

    One tuple of this "Generalized Product" can be represented as follows :

    Wednesday false

    And one Relation that is a subset of this "Generalized Product" can be represented as follows :

    Monday true
    Tuesday true
    Wednesday false
    Thursday true
    Friday true

    These representations may start ringing a bell. They all look like a table, and that's not coincidence. When doing your database work, you probably refer to these things as "row" and "table", which are the "synonyms" that were introduced by SQL (the language that you probably use -in some dialect- to manage your databases) for the terms "tuple" and "relation", respectively.

    For the purposes of the present document (which is to clarify the algebra), it is not that terribly incorrect to think of a tuple as "being a row" and of a relation as "being a table". However, the algebra is defined in terms of tuples and relations, not in terms of rows and tables (they are not truly the same thing), so this document will consistently use the terms "tuple" and "relation".

    Nevertheless, for a proper understanding of other textbooks that attach more importance to using formally precise terminology, it is indeed important for your attention to be drawn to

  9. Some crucial issues

    1. The SQL word "table".

      In SQL, the "table" is undoubtedly a rather important concept.  But what exactly does the SQL term "table" refer to ?  You have just been presented three different things that are all three also tables, and only the third one of them would really correspond to the meaning that SQL attaches to the word. The second one would rather correspond the the SQL term "row", and the first one wouldn't really correspond to any SQL term at all ... This only goes to show how SQL's choice of terminology leads to a regrettable blurring between concepts that are quite distinct, as far as the theoretical foundations of the RM are concerned. The mathematical objects that have been presented here are really quite distinct, and in fact the only thing they have in common is that the same presentational technique (a table) might be used to visualise them. But that does not make the visualised mathematical concepts themselves, identical.

    2. A relation is a set ...

      There is a very important consequence that derives from the way that the concept of a Relation is defined. A relation is a set, and a set is defined to be a collection that has no duplicates. See the consequence ? No tuple can appear twice in a relation. Or else it is no longer a relation.

      SQL deviates from this principle, and you may wonder whether that is really so problematic. It is beyond the scope of this document to discuss the issue profoundly, suffice it to say that SIRA_PRISE faithfully follows the following rule (which stems from the way the RM is defined) :

      No tuple can ever appear twice in a relation

    3. ... of tuples, formed from n Types

      It might have gone unnoticed, but another crucial thing is the 'n' in the definition. In the example of the Weekday/Booleans, does the generalized product contain any tuple of only one value ? Or can it possibly contain any tuple in which, e.g., the day is _not_ a weekday ? Obviously, the answer to both these questions is "no". And given that a relation is a subset of this generalized product, the same goes for any relation over those types.

      SQL deviates from this principle by offering the possibility to include nulls in its rows. On this issue too, entire libraries have already been filled with the discussion of whether or not this is really a problem. Once again, it is beyond the scope of this document to add to that discussion, so once again it is only observed here (and important to remember) that SIRA_PRISE faithfully applies the rules of the model :

      In a Relation, all tuples contain an equal number of values, and that number of values is equal to the number of Types that the generalized product was defined with
      No tuple can contain any value that is not a value of the corresponding Type

    4. Attributes

      When we mentioned the definition of Cartesian product and the pairs of values that it consists of, we incorrectly spoke of the Cartesian product as being "the set of all such possible pairs". You may have noticed the error : the ordering of the values in the pair was overlooked. It was tacitly assumed that the values picked from the "first" type would have to occupy the first position in the pair, and the values picked from the "second" type would have to occupy the second position in the pair. Otherwise it would also have been possible, in the given example, to construct pairs such as (false, Friday).

      So in the way that mathematics usually deals with relations and such, the order of the values is important and relevant. Implying that if we are given such a pair, and we need to "extract" a value from such a pair, then we need to know whether it is the first or the second value we're interested in.

      Given that we're interested in data management, and that we will often be using relations and tuples with a significantly larger number of values, is that an interesting way to work ? Let's imagine we have some generalized product of 20 types (think of this as the declaration of a 20-column table), and all programs that operate on that table must refer to the values as "the sixteenth value", or "the thirteenth value" (for lack of another means to refer to those values precisely and unambiguously). Apart from the fact that it is mentally very tiring to write programs in that mode (causing way more programmer errors), consider what would need to be done if at one point in time we no longer needed the "third" value, and wanted to remove the corresponding type from the generalized product ("drop the column from the table"). All references in all programs to values beyond the third would have to be decreased by one ...

      That's definitely not a good idea. Which is why the RM explicitly states that all values in a tuple must be associated with a name, and that that name should be the only way available to address that value.

      You probably observed that the tables the previous example lacked something essential, and indeed you were right. What was lacking were precisely the names which are needed to establish "addressibility" of the values in the tuples. These names are called the attribute names. The table from the examples should actually have looked more like the following :

      DAY GOTOSCHOOL
      Monday true
      Tuesday true
      Wednesday false
      Thursday true
      Friday true

      Now, what does this prescription imply for the tuples that the algebra works with ? For the tuples and/or relations themselves, in fact it doesn't make so much of a difference. But it does for the way in which we represent those tuples and/or relations. When we have the attribute names, we can represent a tuple of this relation in a non-tabular way too : {DAY:Monday, GOTOSCHOOL:true}. And it wouldn't make a difference if we wrote {GOTOSCHOOL:true, DAY:Monday} instead.

      Likewise, the ordering of neither the rows nor the columns in the tabular representation of a relation is material. The following relation is exactly the same as the previous one :

      GOTOSCHOOL DAY
      true Thursday
      true Tuesday
      false Wednesday
      true Monday
      true Friday

      In general, it can therefore be stated that :

      The RM has no concept of ordering or ordinal position of attributes within tuples, no concept of ordering or ordinal position of attributes within relations, and no concept of ordering or ordinal position of tuples within relations.

      Observe that the purpose of the attribute names implies that an attribute name cannot appear twice in a tuple. If an attribute name were allowed to appear twice in a tuple, then we would no longer be able to use that attribute name to uniquely identify the value of that attribute in a tuple. We can therefore also say :

      A tuple is a set of named attribute values

    5. Some more terminology and properties

      Having put all this in place, we can make a number of important observations and define a few more useful terms wrt the RM.

      We have already observed that in a relation, each tuple has an equal number of attribute values (and that number is equal to the number of types that were used to define the generalized product). That number is typically referred to as the degree of the relation and its tuples. SQL users may think of this as the "number of columns in a table".

      Given that a relation is defined to be a set, it follows naturally that a number of concepts from set theory in mathematics apply equally well to relations. One such concept is the number of tuples that the relation has. In set theory, this number is called the cardinality of the set. The RM has retained the term and speaks of the number of tuples in a relation as that relation's cardinality. (Since we have established that a tuple is also a set, it is theoretically possible to speak of the cardinality of a tuple, too. However, since this concept has already been baptised "degree", that is usually not done.)

      It will also be clear that in a relation, all tuples will not only hold an equal number of attribute values, but the set of attribute names used to refer to those values, will be the same no matter which tuple one looks at. It will furthermore be clear (even if it has not been stated explicitly) that the values in any two tuples for a certain attribute name, will be values from the same type, specifically. There will be no two tuples where one has a value from GregorianDate in attribute X, and the other has a value from some other type in attribute X.

      It is thus possible to list all the attribute names of a relation, and next to each name put the name of the type from which the tuples draw their values for that attribute. In the example given previously, this list would look like : GOTOSCHOOL:Boolean, DAY:Weekday. This list is typically referred to as the heading of the relation and of the tuples.

    6. What about the keys of a relation ?

      Keys are, obviously, an important concept in relational databases. But as far as the purpose of this page is concerned, which is to explain the algebra, and to introduce the terminolgy that is needed to do so, the concept of keys bears no relevance.

      In fact, it is, strictly speaking, even plain wrong to speak of "the key of a relation". In the RM, a key is something that applies to a relation variable, not to the values (the relations) such a variable possibly contains. A key is, in a sense, nothing more than a user-friendly facility that allows to define certain specific classes of database constraint. This chapter does not deal with constraints, and so there need be no mention here of the concept of 'keys'.

Relational Algebra

  1. The term 'algebra'

    Time to start talking about the algebra. You may wonder at the idea of an 'algebra' with relations ... Wasn't 'algebra' about computing ? And isn't computing performed on numbers exclusively ? The answer is, obviously, 'no'. George Boole defined an algebra that allowed us to do computations on the logical truth values 'true' and 'false'. An algebra exists that allows us to do computations on matrices. The operations of union, intersection and difference as they are applied in set theory, form an algebra that is used to do computations on sets. And so on and so on ...

    Then what does it take to 'be an algebra' ? How is it that the Relational Algebra (RA for short) is indeed an algebra ? Well, an algebra is essentially nothing but a set of computation operators. Ordinary arithmetic on numbers, e.g., is an algebra consisting of the operators addition, subtraction, multiplication, division, exponentiation. Set algebra includes the operators union, intersection and difference. Likewise, the RA is essentially just a set of operators that "compute" with relations as they have been defined in the introductory chapters.

    And just as the addition and multiplication operators operate (in their most basic form) on two numbers to yield another number, so will an operator of the RA (commonly referred to as a 'relational operator') in its most basic form operate on two relations to yield another one.

  2. Do I really need an algebra to manipulate the data in my databases ?

    You might think that the answer to this question is 'no'. After all, you've been using SQL for years already perhaps, and no one's ever mentioned the word 'algebra' in connection to SQL, right ? Well, it may be right that you've never heard anyone mention the word 'algebra' in connection with SQL. Nevertheless, the connection does indeed exist. The SQL language has, since day 1 of its existence, been intended as an implementation of the RA. Every query that you write is nothing more or less than an expression, a formula, of the RA. So if you've been using SQL, you've probably already written dozens of expressions of the algebra. You just weren't aware.

  3. A short note on 'value vs. variable' and operator nesting

    We mentioned earlier that, as far as the purpose of the present document is concerned, it is not terribly wrong to think of a relation as 'being a table'. At this point, however, we should clarify an important distinction that SQL mostly fails to make, and hence that SQL users mostly fail to recognize. When programming, you probably define variables that you subsequently use to store values in. You do so by "declaring" those variables with a certain name (e.g. int c;), after which you can assign a value to (i.e. store a value in) that same variable (e.g. c=1;). You usually also declare the type of values that the variable is allowed to store (integers in the example).

    In much the same sense, SQL's tables can also be considered a "variable" of the programming system. Not one that is declared locally for some small program procedure, but rather one that is declared globally for every program that accesses the database. (The C programming language, and probably lots of others too, has the concept of 'static external' variables, which is somewhat similar.) As any other variable, it can be considered as "storing", or "containing" a value. That value being, precisely, the relation that consists of all the tuples that were "added" (and not yet deleted back again). A variable that is declared to contain integer values specifically, is usually referred to as an "integer variable". By analogy, the RM uses the term "relation variable" for a variable that is declared to contain relation values specifically. RM literature often abbreviates that term to "relvar".

    SQL blurs this distinction rather seriously by using the word 'table' for both of these concepts (the word stands both for the variable and for the -relation- value it contains).

    When discussing the operators of the RA, it is important to remember that they always deal with relation _values_ specifically, without any consideration as to where and/or how that relation value originated. In particular, an operator of the RA does not prescribe that its input can only be a "table" (in the 'variable' sense of the word). Quite the contrary : it is perfectly possible for the input of a relational operator to be some other expression of the RA. The input to a projection can be the result of a restrict, and the input to that restrict can be the result of a join, etc. etc. In other words : expressions of the RA can have any arbitrary level of nesting, just so long as those expressions themselves evaluate to relation values, i.e. yield a relation value.

  4. The syntax employed in the examples.

    The examples in the discussion of the relational operators below, will adhere closely to the syntax used by SIRA_PRISE.  For purposes of readability however, certain expressions in the examples will not be given using the syntactic notation used by SIRA_PRISE.  This is mainly for purposes of readability, and for maintaining a higher degree of "visual familiarity" towards database users who are used to SQL expressions.

  5. The operators of the algebra

  6. The operators that we will be introducing here, are the following : restriction, projection, extension, renaming, the transform shorthand, intersection, union, difference, join, division, semijoin, semidifference, symmetric difference, left join, transitive closure, generalized transitive closure, grouping, ungrouping, aggregation and summarization.

    Note that the operators' "definitions" as we will present them here are not always "formal" definitions. The only goal we try to achieve is to explain the basic operation that the operator stands for, which can often be achieved equally well by explaining the basic algorithm it performs. The formal definitions for the operators can be found in the javadoc for the operators.

    1. Restriction

    2. Often we will want to inspect a relation value and "retain" only those tuples of the inspected relation that satisfy certain conditions. The restriction operator is the operator that can perform that task for us. The restrict operator takes a relation as input, plus a boolean expression, and yields a relation consisting of all and exactly those tuples of the input relation for which the boolean expression evaluates to 'true'.

      The following example lists all the attributes whose defined maximal length exceeds 256 :

      Restriction :
      ARG RESTRICTCONDITION RESTRICT
      MAXIMUMLENGTH ATTRIBUTENAME
      124 CLIENTID
      2147483647 OPERANDSIGNATURE
      1022 CONSTRAINTLABEL
      786428 SP_EXPRESSION
      252 TYPESIZEHINT
      126 SPECIESNAME
      786428 RELVARPREDICATE
      126 NLSPECIESNAME
      786428 CONSTRAINTMESSAGETEXT
      1048572 CERTIFICATE
      gt(maximumlength,256)
      MAXIMUMLENGTH ATTRIBUTENAME
      2147483647 OPERANDSIGNATURE
      1022 CONSTRAINTLABEL
      786428 SP_EXPRESSION
      786428 RELVARPREDICATE
      786428 CONSTRAINTMESSAGETEXT
      1048572 CERTIFICATE

      Observe that just any boolean expression is allowed as the restrict condition, and that there is no obligation for the expression defining this restrict condition to reference any attribute of the relation that is restricted. So the following expressions are all valid :

      • RESTRICT(R , false)
      • RESTRICT(R , true)
      • RESTRICT(R , 1 = 1)
      • RESTRICT(R , 1 = 2)
      A degenerate restrict condition :
      ARG RESTRICTCONDITION RESTRICT
      MAXIMUMLENGTH ATTRIBUTENAME
      2147483647 OPERANDSIGNATURE
      1022 CONSTRAINTLABEL
      786428 SP_EXPRESSION
      786428 RELVARPREDICATE
      786428 CONSTRAINTMESSAGETEXT
      1048572 CERTIFICATE
      boolean(false)
      MAXIMUMLENGTH ATTRIBUTENAME

      Another thing that may be less obvious : the boolean expression can itself be of arbitrary complexity, and can also contain references to other relation variables ! It is, e.g. perfectly possible to check whether an integer attribute in some tuple contains a value that is equal to the cardinality of some other relvar, as in 'X where score = cardinality(Y)', where score is an attribute of X, Y is some other database relvar, and cardinality is an operator that returns the number of tuples in (the relation that) its argument (evaluates to).

    3. Projection

    4. In information processing, it is very unlikely that all programs will always need to inspect the values of all attributes in a relation. Often, databases also contain 'comment' fields and 'label' fields which only serve a descriptive purpose, and which often aren't needed by the programs that do the "core business" of the organisation.

      So it might be interesting to be able to build, starting from a given relation, another relation that has only the attributes we really need. This is precisely what the projection operator can do for us. The projection operator takes a relation as one argument, and a set of attributenames as the other (where obviously, that set can only contain names of attributes that effectively appear in the relation). It then produces a relation that holds one tuple for each combination of values that appears in the input relation for the given list of attributes (that tuple being precisely that combination of values).

      Important : take a close look at the way the definition for the result of the projection operator is formulated. The result of a projection contains one tuple "for each combination of values found for the projection attributes in the input relation". Nothing is said about how many times this "combination of values" appears in the input, or how it would affect the number of times this "combination of values" appears in the result. In fact, it would be a violation of the relational model if any such thing were said. Any such "combination of values" can only appear once in the result anyway, otherwise the result wouldn't be a relation. Remember that the projection operator is supposed to return a relation, that a relation was defined to be a set of tuples, and that therefore, the result of a projection cannot possibly contain the same tuple >1 times. Otherwise, the result of the projection would not be a relation anymore (at least not guaranteeably in all cases). It is important to remember that the projection operator of the algebra always "eliminates duplicates" in its result. 

      Projection will eliminate duplicates :
      ARG PROJECTSPEC PROJECT
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      (PAGESIZE)
      PAGESIZE
      16384
      32768
      49152
      Projection on no attributes at all is supported :
      ARG PROJECTSPEC PROJECT
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      ()

      This example illustrates that it is problematic to visualise a relation with one tuple and no attributes as a table with one row and no columns (some browsers may allow you to observe that the line around this table is a bit thicker than the lines around the other tables), so things might be a little clearer if we just write an equality test ( EQ(TABLE_DEE, ... ) ) of the result with TABLE_DEE (the nilary relation value that includes the zero-tuple in its body) :

      Query result :
      ARG PROJECTSPEC EQUAL_TO_TABLE_DEE
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      () True
    5. Extension

    6. Sometimes, it is interesting to be able to "derive" values for additional attributes in a relation, based on the attributes that are already there. Application programs may benefit if the dbms can handle these kinds of "derivation" for them, rather than having to do it themselves. This is precisely what the extension operator can do. The extension operator takes a relation as one argument, and a set of extension specifications as its second argument. An extension specification consists of both an attribute name and an expression that will determine the values of the additional attribute for each tuple of the relation argument : for each tuple in the relation argument, every expression in the set of extension specifications is evaluated. For each such expression, the value obtained is "appended" to the tuple as the value of the attribute the expression corresponds to.

      The following example uses the extend operator to compute the length of the name of the various dbms files :

      Extension :
      ARG EXTENDSPEC EXTEND
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      namelength(length(filename))
      NAMELENGTH FILENAME PAGESIZE
      15 BW_SPECIES.SPDB 32768
      23 BW_POSSIBLESPECIES.SPDB 16384
      20 DATABASECATALOG.SPDB 32768
      20 BW_SPOTSXSPNAME.SPDB 49152
      13 BW_SPOTS.SPDB 16384

      A few rather obvious rules apply to the extension specifications : it is obviously illegal to specify an attribute name that already exists in the input relation (otherwise the result would contain two attributes of the same name, which is against the rules that the RA imposes on its relations), and it is equally illegal to specify an attribute name twice in the set of extension specifications, for the same reason.

      Like with restrict, just any expression can be specified, just as long as it does not contain references that the system is unable to resolve. In particular, literals are also valid expressions in an extend specification, as are expressions that somehow refer to other database relvars, including the SIRA_PRISE context relvars :

      Extension with an expression involving a [context] relvar reference :
      ARG EXTENDSPEC EXTEND
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      currentdate(currentdate)
      CURRENTDATE FILENAME PAGESIZE
      CURRENTDATE
      2015-08-08
      BW_SPOTSXSPNAME.SPDB 49152
      CURRENTDATE
      2015-08-08
      DATABASECATALOG.SPDB 32768
      CURRENTDATE
      2015-08-08
      BW_SPECIES.SPDB 32768
      CURRENTDATE
      2015-08-08
      BW_SPOTS.SPDB 16384
      CURRENTDATE
      2015-08-08
      BW_POSSIBLESPECIES.SPDB 16384

      Note that care must be taken, however, to avoid the emerging of runtime exceptions, such as division by zero. If an extend expression involves an operator invocation that potentially gives rise to such exceptions, it is the programmers responsibility to take all necessary measures to prevent/avoid them.

    7. Renaming

    8. Attribute renaming is an operator that is very similar to projection and extension, and can in fact even be considered as a (very particular) combination of both. The prime reason why it exists as a separate operator nevertheless, is that it is rather frequently needed in combination with the join operator (which will become clear when we discuss that operator).

      Its operation should be clear simply by its name : it does nothing than produce a relation value that has exactly the same set of tuples (at least as far as the attribute values they hold are concerned), but where some of those attribute values now appear under another attribute name.

      Formally, that is realised by giving as the operator's second argument a set of rename specifications. Each rename specification consists of two attribute names, the first one of which must refer to an existing attribute in the input relation, and the second one of which defines the name under which the concerned attribute values will appear in the result of the operator's invocation.

      SIRA_PRISE's RENAME is "parallel", meaning that it is not required that each individual new name be a name that does not appear in the argument. It is sufficient that there will be no duplicate names after ALL renaming has been applied. This facilitates "swapping" of attribute names :

      A "parallel" RENAME :
      ARG RENAMESPEC RENAME
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      (FILENAME,PAGESIZE,PAGESIZE,FILENAME)
      FILENAME PAGESIZE
      32768 DATABASECATALOG.SPDB
      16384 BW_SPOTS.SPDB
      49152 BW_SPOTSXSPNAME.SPDB
      16384 BW_POSSIBLESPECIES.SPDB
      32768 BW_SPECIES.SPDB
    9. The Transform shorthand

    10. Often, combinations of PROJECT/EXTEND/RENAME are needed in order to produce the desired result from a given relation. In many of these cases, the needed combination of invocations of these three can be combined into a single invocation of TRANSFORM. The features of the three operators combined into TRANFORM are as follows :

      • Like EXTEND, TRANFORM has the ability to compute values for extra new attributes in the relations produced.
      • Like PROJECT, TRANFORM has the ability to discard some attributes from the input relation, as well as to simply retain some others.
      • Like RENAME, TRANFORM has the ability to "copy over" values from input to output, but to make them appear under a new attribute name.

      The following examples illustrate these abilities :

      Extend, Project and Rename combined into one :
      ARG TRANSFORMSPEC TRANSFORM
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      (pagesize,name(lowercase(the_string(filename))))
      NAME PAGESIZE
      bw_species.spdb 32768
      databasecatalog.spdb 32768
      bw_possiblespecies.spdb 16384
      bw_spotsxspname.spdb 49152
      bw_spots.spdb 16384

      Note how :

      • the PAGESIZE attribute is "copied over" since it is mentioned in the transform spec without being accompanied by a computational formula
      • the FILENAME attribute is "projected away" by transform since it is not mentioned in the transform spec as an output attribute
      • the NAME attribute is "added" to the result since it is mentioned in the transform spec, accompanied by a computational formula to produce a lowercase rendering of the FILENAME attribute of the input
    11. Union

    12. The union operator is intuitively easy to understand, because of its similarity to the union operator of classical set algebra. The union operator of the RA takes two relations as argument, and yields a relation that contains all and exactly those tuples that appear in either of the two input relations. Observe that of course once again, the relational requirement of "no duplicate tuples" holds. Observe too that the heading of both arguments must be identical, for the result to be a valid relation. This means that the relation arguments of the union operator must have the same number of attributes and the same set of attribute names, and for each pair of equally-named attributes, the type of that attribute must also be the same. Relations for which this condition holds are generally said to be "union-compatible".

      The following example shows that UNION always eliminates duplicates :

      A UNION of identical relations :
      ARG1 ARG2 RESULT
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
    13. Intersection

    14. The relational intersection operator closely resembles its counterpart of classical set algebra. It takes two relations as input value, and yields a relation containing all and exactly those tuples that appear in both arguments. Observe that this implies that both arguments must be union-compatible.

      Relational intersection :
      ARG1 ARG2 INTERSECT
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_POSSIBLESPECIES.SPDB 16384
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_POSSIBLESPECIES.SPDB 16384
    15. Difference

    16. As is the case with union and intersection, so does the relational difference operator resemble very closely its counterpart in classical set algebra. As can be expected, the relational difference operator takes two relation values as argument, and yields a relation containing all and exactly those tuples which do appear in the first argument (the minuend), but do not appear in the second (the subtrahend).

      The following example employs the relational difference to find all the dbms files that have an 'O' in their name, but not a 'C' :

      Relational difference :
      ARG1 ARG2 MINUS
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_POSSIBLESPECIES.SPDB 16384
      FILENAME PAGESIZE
      BW_SPOTSXSPNAME.SPDB 49152
      BW_SPOTS.SPDB 16384
    17. Join

    18. The join operator implemented by SIRA_PRISE is the natural join operator. This operator is defined as follows :

      If one relation has heading {a, b, c, ..., m, n, ...}, and another relation has heading {m, n, ..., v, w, x, ...}, then the natural join of these relations is a relation with heading {a, b, c, ..., m, n, ..., v, w, x, ...}, i.e. all the attributes that appear in the heading of either relation also appear in the heading of the join (but in line with the prescriptions of the RA, they do so only once).

      A tuple {a1, b1, c1, ... m1, n1, ..., v1, w1, x1, ...} will appear in the resulting relation if (and only if) : (A) a tuple {a1, b1, c1, ... m1, n1} appears in the one argument of the join, and (B) a tuple {m1, n1, ..., v1, w1, x1, ...} appears in the other argument of the join.

      Observe that this definition holds equally well for the case where the set of attributes {a, b, c, ...} is actually empty (argument 1 has all attributes in common with argument2), the case where the set of attributes {m, n, ...} is actually empty (arguments have no attribute in common), and the case where the set of attributes {v, w, x, ...} is actually empty (argument 2 has all attributes in common with argument 1).

      The set of attributes {m, n, ...} is commonly referred to as the set of "join attributes". It follows from this definition that the set of join attributes is determined by (and only by) the heading of its arguments. Furthermore, the condition for "joining" two tuples is that all values in those two tuples appearing for a join attribute, must be equal. Natural join does not allow to specify that the "join condition" is satisfied if join attributes are unequal.

      If you're used to using SQL, those two properties may seem like a rigid restriction, but they can be easily overcome, and both by using the RENAME operator mentioned earlier. Renaming a join attribute in only one argument has the effect of "moving the attribute out of the set of join attributes", which already solves the first problem.

      As for the second problem, assuming that we wanted a join condition to be something similar to 'A.m1 > B.m1', we can simply rename the m1 attribute in one of both join arguments to move it "outside the set of join attributes", and then apply the greater-than condition in a restrict applied to the result of the join. This need not imply that the join is first computed completely before the restrict condition is applied.

      The following examples illustrate the characteristics of the natural join operator by showing the result when the two ARG relations are joined to produce the result listed under JOIN :

      Natural JOIN :
      ARG1 ARG2 JOIN
      STORAGESPACEID PAGECOUNT FILENAME
      1 2250 BW_SPOTS.SPDB
      2 23 DATABASECATALOG.SPDB
      17 30 DATABASECATALOG.SPDB
      51 412 DATABASECATALOG.SPDB
      3 650 BW_SPOTSXSPNAME.SPDB
      117 8 DATABASECATALOG.SPDB
      3 605 DATABASECATALOG.SPDB
      10 191 DATABASECATALOG.SPDB
      1 50 BW_POSSIBLESPECIES.SPDB
      52 43 DATABASECATALOG.SPDB
      145 57 DATABASECATALOG.SPDB
      21 610 DATABASECATALOG.SPDB
      65 150 DATABASECATALOG.SPDB
      1 2850 BW_SPECIES.SPDB
      15 24 DATABASECATALOG.SPDB
      54 14 DATABASECATALOG.SPDB
      22 14 DATABASECATALOG.SPDB
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      STORAGESPACEID PAGESIZE PAGECOUNT FILENAME
      1 32768 2850 BW_SPECIES.SPDB
      54 32768 14 DATABASECATALOG.SPDB
      65 32768 150 DATABASECATALOG.SPDB
      22 32768 14 DATABASECATALOG.SPDB
      15 32768 24 DATABASECATALOG.SPDB
      10 32768 191 DATABASECATALOG.SPDB
      21 32768 610 DATABASECATALOG.SPDB
      117 32768 8 DATABASECATALOG.SPDB
      51 32768 412 DATABASECATALOG.SPDB
      1 16384 50 BW_POSSIBLESPECIES.SPDB
      3 49152 650 BW_SPOTSXSPNAME.SPDB
      2 32768 23 DATABASECATALOG.SPDB
      3 32768 605 DATABASECATALOG.SPDB
      52 32768 43 DATABASECATALOG.SPDB
      145 32768 57 DATABASECATALOG.SPDB
      1 16384 2250 BW_SPOTS.SPDB
      17 32768 30 DATABASECATALOG.SPDB

      Joins can also be performed with relation-typed attributes among the join attributes. The following is such an example, producing a tuple in the result because the OPERANDSIGNATURE attribute values are equal between the arguments :

      A natural join involving relation-valued attributes as join attributes :
      ARG1 ARG2 RESULT
      TYPENAME OINM OPERANDSIGNATURE
      BOOLEAN MATCHES
      TYPENAME ORDINAL
      STRING 1
      STRING 2
      OINM2 TYPENAME2 OPERANDSIGNATURE
      CONCAT STRING
      TYPENAME ORDINAL
      STRING 1
      STRING 2
      TYPENAME OINM2 OINM TYPENAME2 OPERANDSIGNATURE
      BOOLEAN CONCAT MATCHES STRING
      ORDINAL TYPENAME
      1 STRING
      2 STRING
    19. Division

    20. Occasionally, businesses are interested in things like "the list of customers who already have all possible types of insurance policy", or "employees who have followed all training programs they were eligible for", or some such. Ever wondered how you would write such a query in SQL, without using any program code ? To get to the solution, a little rephrasing of the stated problem (e.g. the customers with all types of insurance policy) will be helpful : "the list of customers for which no insurance policy type can be found such that that customer does not have a policy of that particular type". The SQL for this might look something like :

      SELECT ... FROM CUSTOMERS WHERE NOT EXISTS (SELECT ... FROM POLICYTYPE WHERE NOT EXISTS (SELECT ... FROM POLICY WHERE POLICY.CUSTNO = CUSTOMERS.CUSTNO AND POLICY.TYPE = POLICYTYPE.TYPE))

      Queries such as these constitute an invocation of the relational division operator. This example sufficiently reveals that the relational division is a rather complex operator. Furthermore, it is an operator that isn't needed all that often, and is therefore usually not easily understood. The complexity of its semantics are also revealed by the fact that it needs three relation arguments to work on (inspect the SQL version closely to verify this).

      In order to explain the operator as intuitively as possible, we name the three relations that are an argument to the division the subject (customers in the SQL example), the intersection (policies in the SQL example) and the target (policy types in the SQL example).

      Essentially, what the operator does, is to process the subject relation on a tuple-per-tuple basis. For each such tuple (e.g. each customer), it looks up (in the intersection relation) a "complete" set of information relating to that subject tuple (e.g. the "complete" set of all policy types that this customer has subscribed), and then checks if that "complete" set of information is a superset of the target (e.g. all possible policy types), i.e. whether all entries in the target can also be found in the "complete set of information" from the intersection relation. If it is, then the subject tuple is included in the result of the division, otherwise it is not.

      Given that the operator needs to deal with "sets of information", we will later see that there are better ways to deal with this kind of problem.

      You might wonder why we want the check against the target to be a superset test, and not an equality test. After all, surely there can't be policies of a policy type that doesn't exist, can there ? Possibly true, but the target might also be "all policy types that already have been commercialised by our company for more than 20 years". In which case there could definitely be a policy type subscribed by a customer that does not appear in the target relation of the division.

      There actually are quite a lot of subtleties such as this one related to the definition of the division operator. Others are to do with restrictions that are either or not imposed on the heading of the three arguments.

      Which is yet another reason why the operator is rarely talked of. In fact, the operator is mentioned here more for completeness' sake and to draw the reader's attention to the class of problems it was aimed to solve.

    21. Semijoin

    22. In our discussion of join, we have seen that the heading of the result is the union of all attributes that appear in either one of the join arguments. Quite often though, this is not exactly what we need. Quite often we are only interested in knowing for which tuples of one relation, a "corresponding" tuple can be found in another relation, without needing to know the actual contents of that corresponding tuple.

      This is why the semijoin operator is usually defined as a separate operator, and indeed supported by SIRA_PRISE. The result of the semijoin of two arguments is the same as if the join of the two arguments were computed, and that result projected back again to just the attributes of the first argument of the join.

      The following examples illustrates semijoin :

      Semijoin :
      ARG1 ARG2 SEMIJOIN
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      CATEGORY PAGESIZE
      big 32768
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
    23. Semidifference

    24. Just as we often find ourselves confronted with the need to know for which tuples of a relation there exists a corresponding tuple in another relation, so do we find ourselves often confronted with the need to know for which tuples of a relation there does not exist a corresponding tuple in some other relation. This is precisely what the semidifference operator does.

      The result of the semidifference operator is equal to the (relational) difference of the first argument and the semijoin of the two arguments :

      Semidifference :
      ARG1 ARG2 SEMIMINUS
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      CATEGORY PAGESIZE
      big 32768
      FILENAME PAGESIZE
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
    25. Left join

    26. Natural join has the property that it only includes tuples in the result if in the "second" relation, at least one tuple is found whose attribute values match the attribute values of the tuple (of the "first" relation) that is being joined to. This is often useful, but it is also often quite annoying. Often, we want to retain all tuples from one of the join arguments, regardless of whether any matching tuples exist in the other argument. This is where LEFTJOIN is useful. The prescriptions of the relational model require, however, that the result contains a value for each attribute of that other argument. In order to be able to comply to that rule, a third argument must be provided which lists all the attribute values that are to be included in the result for tuples of the first argument, for which no matching tuples could be found in the second.  LEFTJOIN(R1,R2,attrvalues)  is thus semantically equivalent to UNION(JOIN(R1,R2),EXTEND(SEMIMINUS(R1,R2),attrvalues)) :

      Left join :
      ARG1 ARG2 expressions LEFTJOIN
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      CATEGORY PAGESIZE
      big 32768
      category(string(unknown))
      CATEGORY FILENAME PAGESIZE
      unknown BW_POSSIBLESPECIES.SPDB 16384
      big DATABASECATALOG.SPDB 32768
      unknown BW_SPOTS.SPDB 16384
      big BW_SPECIES.SPDB 32768
      unknown BW_SPOTSXSPNAME.SPDB 49152
    27. Symmetric difference

    28. Symmetric difference is sometimes considered in the relational algebra, seeing as it has a corresponding counterpart in set algebra. The operator is defined to be semantically equivalent to (RA MINUS RB) UNION (RB MINUS RA). Note that, just as in set theory, this is also equivalent to (RA UNION RB) MINUS (RA INTERSECT RB).

      Yet iow, it means symmetric difference will yield a relation that holds all the tuples that appear in exactly one of the two arguments :

      Symmetric difference :
      ARG1 ARG2 XMINUS
      RELVARNAME
      CONSTRAINTMESSAGETEXT
      INDEXATTRIBUTE
      RELVARNAME
      DATABASECONSTRAINTCHECK
      SYSTEMDEFINEDCONSTRAINT
      ASSIGNMENTCONSTRAINT
      ASSIGNMENTCONSTRAINTCHECK
      CONSTRAINTMESSAGETEXT
      ATTRIBUTELENGTHCONSTRAINT
      DATABASECONSTRAINT
      CONSTRAINTINVOLVESRELVAR
      TUPLECONSTRAINT
      RELVARNAME
      DATABASECONSTRAINTCHECK
      SYSTEMDEFINEDCONSTRAINT
      ASSIGNMENTCONSTRAINT
      ASSIGNMENTCONSTRAINTCHECK
      ATTRIBUTELENGTHCONSTRAINT
      DATABASECONSTRAINT
      CONSTRAINTINVOLVESRELVAR
      TUPLECONSTRAINT
      INDEXATTRIBUTE
    29. Transitive Closure

    30. Have you ever needed to process a bill-of-materials structure, trying to find out, e.g. all the parts in which a certain given part is used, either directly or indirectly ? Then you probably know the problems you get confronted with trying to solve this with SQL. There's no problem finding out in which parts y a certain given part x is used directly. There's no problem finding out all the parts z in which any part y is used in which the given part x is used. There's no problem finding out all the parts x in which any part z is used in which any part y is used in which the given part x is used. There's no problem computing the union of all of these. The problem is where to stop.

      In the early days, you either had to choose some upper limit, but then if the real number of "levels of containment" in the database exceeded that limit, your query produced incorrect results. Or else you had to code an iteration process yourself until you no longer found any part in which any part was used in which any part was used in which any part was used in which part x was used ...

      Later, SQL came up with the possibility of writing recursive queries, relieving the programmers of having to write the iteration process themselves. But I think most of you who have already written recursive queries will agree that writing these is still rather unintuïtive and error-prone. At least, that's my personal opinion.

      The operator of the RA that is "underneath" all of this, is called transitive closure. Transitive closures are typically applied to relations that represent the edges of a graph, that is, that represents the "direct" parent-child relationships between the nodes of such a graph. The essence of transitive closure is that if its resulting relation shows the existence of a path from any node1 to any node2, as well as the existence of a path from that same node2 to any node3, the it should also show the existence of a path from node1 to node3.

      Here is an example from the SIRA_PRISE catalog. The catalog holds definitions for "virtual relvars", which are essentially nothing but an assigned shorthand name for some other expression that may be defined in terms of other relvars. So there is a "definitional dependency" between such a virtual relvar and the relvars that appear in its defining expression. However, those "relvars that appear in its defining expression", may themselves be virtual relvars too, that depend in turn upon other relvars defined in the catalog. And so on and so on and so on ...

      The following example shows a relation that reflects the "direct" dependencies between virtual relvars and the relvars in terms of which they are defined, and its transitive closure.

      Transitive closure of virtual relvar dependencies :
      ARG TCLOSESPEC TRANSITIVE CLOSURE
      REFERENCEDRELVARNAME RELVARNAME
      POSSREPCOMPONENT TYPEDIRECTLYREFERENCEDBY
      UDTPHYSICALPOSSREPCOMPONENT TYPEDIRECTLYREFERENCEDBY
      INTERVALTYPE TYPESUPERTYPES
      DATAACTIONREFERENCES RELVARCLUSTER
      DATABASECONSTRAINTCHECK RELVARCLUSTER
      JAVABACKEDTYPE TYPESUPERTYPES
      ASSIGNMENTCONSTRAINTCHECK RELVARCLUSTER
      TRIGGEREDDATAACTION RELVARCLUSTER
      INTERVALTYPE TYPEDIRECTLYREFERENCEDBY
      USERDEFINEDTYPE TYPESUPERTYPES
      KEYATTRIBUTE RELVARKEYDEFS
      VIRTUALRELVARREFERENCES VIRTUALRELVARDEPENDENCYGRAPH
      TYPEDIRECTLYREFERENCEDBY TYPEDEPENDENCYGRAPH
      KEY RELVARKEYDEFS
      CONSTRAINEDTYPE TYPESUPERTYPES
      CONSTRAINTINVOLVESRELVAR RELVARCLUSTER
      CONSTRAINEDTYPE TYPEDIRECTLYREFERENCEDBY
      VIRTUALRELVARREFERENCES RELVARCLUSTER
      (RELVARNAME,REFERENCEDRELVARNAME)
      REFERENCEDRELVARNAME RELVARNAME
      POSSREPCOMPONENT TYPEDIRECTLYREFERENCEDBY
      UDTPHYSICALPOSSREPCOMPONENT TYPEDIRECTLYREFERENCEDBY
      INTERVALTYPE TYPESUPERTYPES
      DATAACTIONREFERENCES RELVARCLUSTER
      INTERVALTYPE TYPEDEPENDENCYGRAPH
      DATABASECONSTRAINTCHECK RELVARCLUSTER
      JAVABACKEDTYPE TYPESUPERTYPES
      ASSIGNMENTCONSTRAINTCHECK RELVARCLUSTER
      TRIGGEREDDATAACTION RELVARCLUSTER
      INTERVALTYPE TYPEDIRECTLYREFERENCEDBY
      USERDEFINEDTYPE TYPESUPERTYPES
      KEYATTRIBUTE RELVARKEYDEFS
      VIRTUALRELVARREFERENCES VIRTUALRELVARDEPENDENCYGRAPH
      UDTPHYSICALPOSSREPCOMPONENT TYPEDEPENDENCYGRAPH
      POSSREPCOMPONENT TYPEDEPENDENCYGRAPH
      TYPEDIRECTLYREFERENCEDBY TYPEDEPENDENCYGRAPH
      KEY RELVARKEYDEFS
      CONSTRAINEDTYPE TYPEDEPENDENCYGRAPH
      CONSTRAINEDTYPE TYPESUPERTYPES
      CONSTRAINTINVOLVESRELVAR RELVARCLUSTER
      CONSTRAINEDTYPE TYPEDIRECTLYREFERENCEDBY
      VIRTUALRELVARREFERENCES RELVARCLUSTER
    31. Generalized Transitive Closure

    32. While TCLOSE allows us to figure out which nodes of a graph are -indirectly- connected to which other nodes (if the graph is represented as a binary relation of immediately connected nodes), that information often isn't sufficient. Quite often, we also want to know certain "properties" of the path that connects one node with another. One very popular case in point is the count of edges on such a path. GTCLOSE can provide us with such information. We will explain the operation of GTCLOSE by highlighting the differences with TCLOSE.

      The <AttributeNamePair> list to be specified in GTCLOSE has exactly the same syntax and semantics as it has in TCLOSE : it determines which attributes of one tuple of a pair under consideration must be equal to which attributes of the other tuple of the pair. Contrary to TCLOSE, however, it is not required that all attributes of the relational expression subjected to GTCLOSE, are mentioned in the <AttributeNamePair> List. (In fact it would kind of defeat the purpose of GTCLOSE, seeing as in that case no additional path information would be computed, and the expression would degenerate to just regular TCLOSE.)

      The <GTCloseDef> clauses must name all the attributes of the <RelationalExpression> that are not mentioned in any <AttributeNamePair>, plus the expression that will determine the value for attributes included in the result. In the example below, EDGECNT is such an attribute. The <Expression> that defines the computation, can reference any attribute of any of the two tuples of the pair of tuples that have been matched for inclusion, by prefixing an attribute name with either __L__ or __R__ . In the example, we take the sum of the EDGECNT values that are present in the two tuples being matched. If two tuples from the initial relation are being matched, then their EDGECNT values will be 1, resulting in an EDGECNT value of 2. If this new tuple is then subsequently matched with some other tuple of the initial relation, the two EDGECNT values summed will be 2 and 1, resulting in an EDGECNT value of 3 in then new tuple. (and so on and son on.)

      Quite often, we will want to produce these kind of closures starting from a relation that just holds identifications of connected nodes, but no attributes (and corresponding values) for the type of information we want to obtain about the paths in the graph that the closure finds between connected nodes. So it will be a typical pattern that we will have to first extend that "binary" relation with "seed values" for the extra attributes at hand. In the example, we set the "seed value" for the EDGECNT attribute to 1, reflecting the fact that immediately connected nodes have an edge count between them of 1.

      The EDGECNT example is one where "directionality" doesn't matter, but this isn't always the case. If we wanted to produce, say, a comma-separated list of all the intermediate nodes between two indirectly connected nodes, we'd have to do the following :

      1. "seed" the initial tuples with a PATH attribute value of the zero-length string (STRING())
      2. in the computation formula for the PATH attribute, specify the concatenation of __L__PATH, the comma character, the connecting node name (__L__REFERENCEDRELVARNAME or __R__RELVARNAME), comma character, __R__PATH

      This example illustrates that the importance of choosing the right prefix for the involved attribute, as well as the fact that the computations do not always exclusively depend on the matching tuples' attribute values for the attribute being computed. The example code and resulting value are below (ARG value not being shown):

      gtclose(extend(virtualrelvarreferences,(edgecnt(int(1))path(string()))),
              (relvarname,referencedrelvarname),
              (edgecnt(plus(__L__edgecnt,__R__edgecnt))path(concat(__L__path,concat(string(,),concat(the_string(__R__relvarname),concat(string(,),__R__path)))))))
      REFERENCEDRELVARNAME RELVARNAME PATH EDGECNT
      TRIGGEREDDATAACTION RELVARCLUSTER 1
      UDTPHYSICALPOSSREPCOMPONENT TYPEDEPENDENCYGRAPH ,TYPEDIRECTLYREFERENCEDBY, 2
      DATAACTIONREFERENCES RELVARCLUSTER 1
      VIRTUALRELVARREFERENCES VIRTUALRELVARDEPENDENCYGRAPH 1
      INTERVALTYPE TYPEDIRECTLYREFERENCEDBY 1
      UDTPHYSICALPOSSREPCOMPONENT TYPEDIRECTLYREFERENCEDBY 1
      CONSTRAINEDTYPE TYPESUPERTYPES 1
      KEYATTRIBUTE RELVARKEYDEFS 1
      USERDEFINEDTYPE TYPESUPERTYPES 1
      POSSREPCOMPONENT TYPEDEPENDENCYGRAPH ,TYPEDIRECTLYREFERENCEDBY, 2
      TYPEDIRECTLYREFERENCEDBY TYPEDEPENDENCYGRAPH 1
      CONSTRAINEDTYPE TYPEDEPENDENCYGRAPH ,TYPEDIRECTLYREFERENCEDBY, 2
      KEY RELVARKEYDEFS 1
      INTERVALTYPE TYPESUPERTYPES 1
      POSSREPCOMPONENT TYPEDIRECTLYREFERENCEDBY 1
      JAVABACKEDTYPE TYPESUPERTYPES 1
      CONSTRAINTINVOLVESRELVAR RELVARCLUSTER 1
      VIRTUALRELVARREFERENCES RELVARCLUSTER 1
      CONSTRAINEDTYPE TYPEDIRECTLYREFERENCEDBY 1
      ASSIGNMENTCONSTRAINTCHECK RELVARCLUSTER 1
      DATABASECONSTRAINTCHECK RELVARCLUSTER 1
      INTERVALTYPE TYPEDEPENDENCYGRAPH ,TYPEDIRECTLYREFERENCEDBY, 2

      It may be somewhat unintuitive why the __R__relvarname had to be used in order to obtain the correct name for the connecting node between "matched edges". As a visual aid, here is a representation of how "__L__" tuples are matched with "__R__" tuples :

      relvarname in produce tuple matching attributes referencedrelvarname in produced tuple
      __L__relvarname __L__referencedrelvarname  
        __R__relvarname __R__referencedrelvarname
    33. Grouping

    34. Time to revert to the bit of theory from the introductory chapters. In section 2.5.2, it was already established that a Generalized product, and thus a relation too, can be considered as a type in its own right. There is an important consequence : we can use that type to define a relation heading and declare a certain attribute in that heading to be of this type ! The value that such an attribute will take on, will be a tuple value specifically (remember that a generalized product/relation is a set of tuples, so if the relation is the type, the values drawn from it must be tuples).

      However, this theoretical possibility is actually not all that interesting. There is little (actually nothing) that one can represent using a single tuple that one cannot represent using the needed number of separate attributes. It is far more interesting to have the possibility to have attributes inside a tuple that take on a relation value. Indeed, there is one thing that a relation value can represent and that other representations cannot handle, and that is the empty relation (or empty set).

      But if we want that possibility, what type do we draw those values from ? We haven't encountered any kind of set yet that had relations as its members. We do need such a set if we want relations to be drawn as values from a type. That set is not so difficult to define : given a generalized product, we can "construct" the set of all possible subsets of that generalized product (In mathematics, this is known as the powerset of a set). Remember that since we named such a subset a relation, we have actually defined a set of all possible relations of a certain heading.

      Relations are, themselves, values too, and relation attributes can therefore be declared to be of another relation type. Such attributes are called 'Relation-valued attributes' (RVA's for short).

      In RA, two operators can be defined that allow us to manipulate relations in connection with RVA's : GROUP and UNGROUP. The former essentially serves the purpose of "creating" relations that have a relation-valued attribute, and UNGROUP essentially does the opposite.

      GROUP takes as its first argument a relation value, and as its second argument a "grouping specification". This "grouping specification" consists of an attribute name for the relation that the GROUP operator will produce, and a set of attribute names that appear in the input relation.

      GROUP will produce a relation of degree n+m, where n is the number of attributes of the input that have not been mentioned in any grouping specification, and m is the number of grouping specifications. Observe that n can be zero. The n attributes that have not been mentioned in any grouping specification will also appear in the heading of the relation produced by GROUP. The other m attributes in the result of GROUP will have the name specified in the grouping specification, and be relation-typed (i.e. those will be RVA's in particular). For each of these m relation-typed attributes, the heading of their relation value will consist of all and exactly those attributes from the (heading of the) input relation that were specified in the grouping specification for that relation-typed attribute.

      Below is an example of using the GROUP operator to list relvar keys and the attributes that make them up.

      Grouping that relation with this grouping specification, will yield the relation :

      Grouping attributenames :
      ARG GROUPSPEC GROUP
      ERRORCODE ATTRIBUTENAME
      245 RELVARNAME
      258 STORAGESPACEID
      244 RELVARNAME
      274 RECORDTYPENAME
      274 ORDINAL
      242 TYPENAME
      256 ATTRIBUTENAME
      245 RECORDTYPENAME
      244 RECORDTYPENAME
      250 RELVARNAME
      254 RELVARID
      242 COMPONENTNAME
      246 ERRORCODE
      248 ATTRIBUTENAME
      268 ERRORCODE
      258 FILENAME
      245 ORDINAL
      248 RELVARNAME
      256 RELVARNAME
      244 ATTRIBUTENAME
      255 RELVARNAME
      274 RELVARNAME
      attributenames(attributename)
      ERRORCODE ATTRIBUTENAMES
      245
      ATTRIBUTENAME
      RECORDTYPENAME
      ORDINAL
      RELVARNAME
      274
      ATTRIBUTENAME
      RECORDTYPENAME
      ORDINAL
      RELVARNAME
      255
      ATTRIBUTENAME
      RELVARNAME
      248
      ATTRIBUTENAME
      ATTRIBUTENAME
      RELVARNAME
      242
      ATTRIBUTENAME
      COMPONENTNAME
      TYPENAME
      256
      ATTRIBUTENAME
      ATTRIBUTENAME
      RELVARNAME
      268
      ATTRIBUTENAME
      ERRORCODE
      244
      ATTRIBUTENAME
      ATTRIBUTENAME
      RECORDTYPENAME
      RELVARNAME
      246
      ATTRIBUTENAME
      ERRORCODE
      254
      ATTRIBUTENAME
      RELVARID
      258
      ATTRIBUTENAME
      FILENAME
      STORAGESPACEID
      250
      ATTRIBUTENAME
      RELVARNAME
      RVA nesting can be done to more than one level :
      ARG GROUPSPEC GROUP
      ERRORCODE RELVARNAME ATTRIBUTENAMES
      361 CLUSTEREDRECORDSPACELOCATTRS
      ATTRIBUTENAME
      FILENAME
      ATTRIBUTENAME
      STORAGESPACEID
      360 CLUSTEREDRECORDSPACELOCATTRS
      ATTRIBUTENAME
      FILENAME
      STORAGESPACEID
      ORDINAL
      keys(errorcode,attributenames)
      KEYS RELVARNAME
      ERRORCODE ATTRIBUTENAMES
      360
      ATTRIBUTENAME
      FILENAME
      STORAGESPACEID
      ORDINAL
      361
      ATTRIBUTENAME
      FILENAME
      ATTRIBUTENAME
      STORAGESPACEID
      CLUSTEREDRECORDSPACELOCATTRS
      Multiple groupings can be specified, creating multiple RVA attributes in one go :
      ARG GROUPSPEC GROUP
      RECORDTYPENAME STSPID FILENAME MAXL RELVARNM
      R0_ACC 51 DATABASECATALOG.SPDB 320 ACC
      R1_ACC 10 DATABASECATALOG.SPDB 320 ACC
      storagespaces( filename,stspid ) recordtypes( recordtypename,maxl)
      STORAGESPACES RELVARNM RECORDTYPES
      STSPID FILENAME
      51 DATABASECATALOG.SPDB
      10 DATABASECATALOG.SPDB
      ACC
      RECORDTYPENAME MAXL
      R0_ACC 320
      R1_ACC 320

      Observe from this last example that by doing this "multiple grouping", you have actually "lost information", in that you have lost the "connection" between, e.g., recordtype R0_ and STSPID 51, and it will be impossible to reconstitute the original relation from the grouped one using UNGROUP.

      As a final note, you might suspect a similarity here with SQL's GROUP BY ... construct here. That is not quite correct. The SQL construct corresponds more to the SUMMARIZE operator, which will be explained later. "Common" SQL actually does not have a counterpart to the GROUP operator, because it has no way to expose a table as an attribute value to the user (The SQL standard does have ways to achieve that, but it is seriously clunky, certainly not all SQL implementations will support it, and even with an SQL implementation that supports it, the feature is used only rarely, if at all). As far as the link to SQL is important, the GROUP BY clause creates a table with _EXACTLY THE SAME ROW COUNT AS THE INPUT_, with just a few "invisible ties" between the rows that are "grouped together". The GROUP opeator described here does something quite different, affecting the cardinality of the result quite seriously.

      An important point to make about the GROUP operator is that it can provide a substitute for the DIVIDEBY operator discussed earlier. Setting up an expression using the GROUP operator that produces the same result as some invocation of DIVIDEBY is still somewhat tricky and elaborate, but it is certainly doable.

    35. Ungrouping

    36. It will now also be intuitively clear what the purpose is of UNGROUP : that is precisely to "revert" relations such as those produced by GROUP, to a relation that does not have any (or certainly less) relation-typed attributes.

      There are certain relation values that GROUP cannot produce, but for which UNGROUP nevertheless has well-defined results. In particular, GROUP can never produce a relation value that has a relation-valued attribute for which the empty relation appears as a value in the result of the GROUP invocation. UNGROUP must, however, be able to deal with such relations. In particular, it will do so by not including a corresponding tuple in its result.

      An Ungrouping over "operandsignature" - note how the empty RVA makes "PI" disappear from the result :
      ARG UNGROUP
      OPINVNM RETURN OPERANDSIGNATURE
      PI FLOAT
      TYPENAME ORDINAL
      PLUS AVERAGE
      TYPENAME ORDINAL
      AVERAGE 2
      AVERAGE 1
      PLUS SCALEDNUMBER
      TYPENAME ORDINAL
      SCALEDNUMBER 1
      SCALEDNUMBER 2
      PRIORLONG LONG
      TYPENAME ORDINAL
      LONG 1
      PRIORDATE DATE
      TYPENAME ORDINAL
      DATE 1
      PLUS TIMEOFDAY
      TYPENAME ORDINAL
      TIMEOFDAY 1
      TIMEOFDAY 2
      PLUS INT
      TYPENAME ORDINAL
      INT 2
      INT 1
      PRIORINT INT
      TYPENAME ORDINAL
      INT 1
      PLUS FLOAT
      TYPENAME ORDINAL
      FLOAT 1
      FLOAT 2
      PLUS LONG
      TYPENAME ORDINAL
      LONG 2
      LONG 1
      PLUS BIGINT
      TYPENAME ORDINAL
      BIGINT 1
      BIGINT 2
      TYPENAME ORDINAL OPINVNM RETURN
      INT 1 PRIORINT INT
      AVERAGE 1 PLUS AVERAGE
      AVERAGE 2 PLUS AVERAGE
      SCALEDNUMBER 1 PLUS SCALEDNUMBER
      TIMEOFDAY 1 PLUS TIMEOFDAY
      INT 1 PLUS INT
      SCALEDNUMBER 2 PLUS SCALEDNUMBER
      LONG 1 PRIORLONG LONG
      TIMEOFDAY 2 PLUS TIMEOFDAY
      INT 2 PLUS INT
      FLOAT 2 PLUS FLOAT
      FLOAT 1 PLUS FLOAT
      LONG 1 PLUS LONG
      LONG 2 PLUS LONG
      DATE 1 PRIORDATE DATE
      BIGINT 1 PLUS BIGINT
      BIGINT 2 PLUS BIGINT
    37. Aggregation

    38. The aggregation operator is not commonly defined as a separate operator of the RA. It is specific to SIRA_PRISE, and the reason is that, despite the fact that it is basically just a building block on which the summarization operator builds, it may nevertheless in certain specific cases be useful to expose aggregation as a separately existing operator to the user. Summarization also becomes easier to explain once aggregation has been defined.

      The aggregation operator takes one relation as an input argument, and a set of aggregation specifications as its second argument. Each aggregation specification consists of an attributename for the relation produced by the operator, the name of an associative operator that will produce the aggregated attribute value in the resulting relation, and an expression defining the value to be aggregated.

      The aggregation operator produces its result by proceeding as follows :

      First, for each aggregation spec an intermediate result is initialized to the identity value of the associative operator named in the aggregation spec.

      Then, the entire input relation is processed on a tuple-per-tuple basis, and for each tuple :

      The value of each expression in an aggregation spec is evaluated for that tuple, and that value (v) is then "aggregated" into the intermediate result by invoking the associative operator named in the aggregation spec with as arguments both the intermediate result and the obtained value v.

      When all tuples of the input relation are processed, a singleton relation is produced with one attribute per aggregation spec, where the value for each attribute is the last "intermediate" result of that aggregation spec.

      E.g. an aggregation spec COUNT(PLUS(INT(1))), will evaluate the literal value 1 for each tuple, invoke the PLUS operator for each tuple, and produce a tuple holding an attribute COUNT whose value is equal to the last "intermediate result" obtained (which will thus be equal to the number of tuples in the input relation).

      Likewise, an aggregation spec COUNT(PLUS(ATTR)), will evaluate the attribute ATTR for each tuple and sum those.

      Aggregation, showing the evaluation of a literal for each tuple, an attribute of each tuple, and an expression involving attributes of each tuple :
      ARG AGGREGATESPEC AGGREGATE
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      silly(plus(pagesize)) silly2(mult(tofloat(pagesize))) count(plus(int(1)))
      SILLY2 COUNT SILLY
      1.4167099448608936E22 5 147456

      The associative operator in an aggregation can also be one of the interval operators. In the case of IINTERSECT, this can give rise to the empty interval appearing as a value in a relation (this is the only way this can happen in SIRA_PRISE) :

      Aggregation - a very very special case :
      ARG AGGREGATESPEC AGGREGATE
      PS
      BEGIN(16384)END(16385)
      BEGIN(49152)END(49153)
      BEGIN(32768)END(32769)
      iintersect(iintersect(ps))
      IINTERSECT
      BEGIN(16384)END(16384)

      Observe that AGGREGATE requires its operator to be both associative and commutative on the corresponding expression type. But then how about computing averages, which is perhaps the most common form of aggregation ? To do averaging, SIRA_PRISE requires the use of the PLUS operator, which operates, not on any number type, but on the special-purpose type AVERAGE :

      AGGREGATE(DBMSFILE,(AVGPAGESIZE(PLUS(AVERAGE(COUNT(1)VALUE(TOFLOAT(PAGESIZE)))))))

      Using AGGREGATE to compute averages :
      ARG AGGREGATESPEC AGGREGATE
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      AVGPAGESIZE(PLUS(AVERAGE(COUNT(1)VALUE(TOFLOAT(PAGESIZE)))))
      AVGPAGESIZE
      COUNT(5)VALUE(29491.199999999997)

      Observe the following points :

      1. The operator name is PLUS
      2. The expression aggregated is a value selector of type AVERAGE
      3. That value selector selects values with two components, an observation count and an observation value
      4. The observation count component is of type INT
      5. The observation value is of type FLOAT
      6. Getting the 'FLOAT' value of the PAGESIZE attribute, involves invoking the TOFLOAT "conversion" operator

      Cumbersome, but it works, and at least it is explicit about the observation count, also in the following case :

      AGGREGATE(TABLE_DUM,(AVG(PLUS(AVERAGE(COUNT(1)VALUE(FLOAT(1)))))))

      AVG
      COUNT(0)VALUE(0.0)

      Another example which finds the length of the longest scalar type :

      AGGREGATE(DBMSFILE,(LONGESTLENGTH(MAX(MAXIMUMSIZE))))

      Using aggregation to find the highest appearing value :
      ARG AGGREGATESPEC AGGREGATE
      FILENAME PAGESIZE
      DATABASECATALOG.SPDB 32768
      BW_SPECIES.SPDB 32768
      BW_SPOTSXSPNAME.SPDB 49152
      BW_POSSIBLESPECIES.SPDB 16384
      BW_SPOTS.SPDB 16384
      LONGESTPAGESIZE(MAX(PAGESIZE))
      LONGESTPAGESIZE
      49152

      Aggregation on empty inputs yields the aggregation operator's identity element, if that exists :

      Aggregation on empty inputs :
      ARG AGGREGATESPEC AGGREGATE
      FILENAME PAGESIZE
      longestpagesize(max(pagesize)) shortestpagesize(min(pagesize)) totalpagesize(plus(pagesize))
      TOTALPAGESIZE LONGESTPAGESIZE SHORTESTPAGESIZE
      0 -2147483648 2147483647
    39. Summarization

    40. Summarization is basically the operator underlying SQL's GROUP BY construct. In terms of the RA, it can be defined as a combination of invocations of GROUP and AGGREGATE.

      Summarization takes three arguments : a relation R to be summarized, a set of attributenames A defining which "groups of tuples" of R will be summarized together, and a set of summarization specs S which are completely identical in nature to the aggregation specs presented in the foregoing section.

      Summarization essentially obtains its result by performing the following steps :

      First, GROUP R such that all attributes mentioned in A are retained, and all the other attributes of R become a member of a single relation-valued attribute RVA.

      Then, process the result of that grouping on a tuple-per-tuple basis, where for each tuple, the relation value of its RVA attribute is aggregated using the given summarization / aggregation specs, and a resulting tuple is produced with all attributes in A, plus the RVA attribute, whose value will be the singleton relation obtained from the aggregation.

      Then, that relation is UNGROUPED back again. The result will thus be a relation whose heading has all attributes mentioned in A, plus one attribute per summarization spec. The values for these latter attributes will be values that have been computed by the aggregation mechanism.

      As an example, we show how to obtain summary information about the system's DBMSFILEs and the STORAGESPACEs they hold :

      Using SUMMARIZEBY to obtain storagespace counts and storagespace pagecounts per dbms file:
      ARG SUMMBYSPEC AGGREGATESPEC SUMMARIZEBY
      STORAGESPACEID PAGECOUNT FILENAME EXTENTSCOUNT
      145 57 DATABASECATALOG.SPDB 30
      22 14 DATABASECATALOG.SPDB 30
      1 2850 BW_SPECIES.SPDB 10
      15 24 DATABASECATALOG.SPDB 30
      21 610 DATABASECATALOG.SPDB 30
      3 605 DATABASECATALOG.SPDB 30
      10 191 DATABASECATALOG.SPDB 30
      52 43 DATABASECATALOG.SPDB 30
      3 650 BW_SPOTSXSPNAME.SPDB 10
      1 50 BW_POSSIBLESPECIES.SPDB 10
      1 2250 BW_SPOTS.SPDB 10
      17 30 DATABASECATALOG.SPDB 30
      117 8 DATABASECATALOG.SPDB 30
      2 23 DATABASECATALOG.SPDB 30
      65 150 DATABASECATALOG.SPDB 30
      51 412 DATABASECATALOG.SPDB 30
      54 14 DATABASECATALOG.SPDB 30
      (filename) storagespacecount(plus(int(1))) pagecount(plus(pagecount))
      PAGECOUNT FILENAME STORAGESPACECOUNT
      2850 BW_SPECIES.SPDB 1
      2181 DATABASECATALOG.SPDB 13
      50 BW_POSSIBLESPECIES.SPDB 1
      650 BW_SPOTSXSPNAME.SPDB 1
      2250 BW_SPOTS.SPDB 1
  7. A remark on associativity

  8. The relational operators union, intersect, symmetric difference and join have been defined here in such a way that they accept exactly two arguments. However, it happens to be the case that these operators have the mathematical property of being associative. SIRA_PRISE therefore allows invocations of these operators to have more than two arguments.

    The theoretical possibility of invocations of these operators with only one argument, or with no arguments at all, is syntactically not supported by SIRA_PRISE. If these operators are invoked in the context of an aggregation or summary, then SIRA_PRISE will compute the results correctly.

The RA and interval types

  1. Rationale

  2. It's quite likely that you have already run into the need for your databases to keep track of historical data. It's an old problem, and existing technology does not really offer a comfortable or easy way for programmers to deal with it. Note very carefully that I haven't said "the Relational Model does not offer ...". That is due to the fact that the relational model does offer an adequate solution for the problem, it's just that the currently existing implementations of the model don't offer an adequate solution.

    If you have had to design a database that kept track of historical data, then your solution probably was to "add a startdate to the table, and include that in the key". You may or may not have included an enddate in the table too, and depending on whether or not you did, found yourself confronted to either one of the following two problems for which no easyly written and easily maintainable solution exists :

    If you do include an enddate, how will you prevent some row in your table from "overlapping" with another row (and possibly even contradict with that other row).

    If you do not include an enddate, what is the query that will give you the applicable enddate for a certain row, if requirements are such that both the start date and the end date are needed ?

    In general, you will probably have found that writing queries becomes a very tedious and error-prone process, right up to the point where writing correct queries actually becomes a real nightmare.

    There does, however, exist a much better solution to the problem. That solution is explained thoroughly in the TDATRM and TaRT books. These books are strongly recommended reading for any programmer who has to deal with historical data. The solution is based on the usage of what is called "interval types".

    SIRA_PRISE implements a solution based on interval types that is inspired by said book. There does exist a significant difference in approach between the book and SIRA_PRISE, but that difference does not show up in the results that the relational operators produce. So, as far as the relational operators (as implemented in SIRA_PRISE) themselves are concerned, I believe they behave identically to the behaviour depicted in the book. Which is what matters.

  3. The interval type

  4. The word 'interval' may vaguely ring a bell. You may remember having been taught about them in your math classes, and maybe wondered what good it all was. Well, the 'interval type' used here is exactly the same kind of thing.

    Consider two attributes in a relvar called 'STARTDATE' and 'ENDDATE' respectively, both declared to be of type DATE. The rest of the attributes contain the "actual" information, e.g. :

    NAME DISCIPLINE STARTDATE ENDDATE
    Bob Beamon Long Jump 1968-07-24 1998-06-18

    You can probably guess what this row intends to declare : Bob Beamon held the world record Long Jump from 1968-07-24 to 1998-06-18. Now, what "meaning" can be ascribed to these dates, what "things" do these dates tell us ? Two are rather obvious : one being that way precisely on july, 24 of 1968, Bob Beamon acquired the world record, and another one being that precisely on june, 18 of 1998, he lost the world record to someone else who did better. But there's a third thing they tell us, and that's about all the dates that are "between" these two dates : we can say Bob Beamon was the world record holder on all these dates in between, too.

    In that sense, the two dates are somehow "closely related", or it might even be said that in that sense, they actually "belong together". Expressing that "belonging together" is precisely what is done by representing these dates as an interval :

    NAME DISCIPLINE DURING
    Bob Beamon Long Jump 1968-07-24 - 1998-06-18

    Note that this table now has only three columns, representing the fact that there now are only three attributes in the relation. Note also that this 'DURING' attribute is not an attribute of type DATE (indeed it does not contain a valid date), but rather of type 'INTERVAL of DATE'.

    Informally, one can think of this interval as "representing a set of dates", where this set has the particular property that there does not exist a date that is "in between" the start and end dates, and where that date is not a member of the set. In other words, the set represented by this interval is "contiguous", meaning that all the dates it contains form a contiguous series.

    One might think that, by replacing the two DATE attributes with one single INTERVAL value, we have lost the possibility to obtain the actual date when Bob Beamon acquired his world record. Indeed, there no longer is an actual date value in the relation. Obviously, this is undesirable, and this must be catered for. That is done by defining a set of operators to deal with values of an interval type which allow us to manipulate these interval values. The most important of them are : STARTPOINTOF (synonymous to THE_BEGIN as well as THE_FROM), ENDPOINTOF (synonymous to THE_END, and disregarding the issue of closed/closed vs. closed/open interpretation of the bounds, also to THE_TO), IUNION, IINTERSECT, and IMINUS. Another important class of operators in connection with interval types are similar to those known as "Allen's operators", after the man who first proposed them. They allow to verify whether two interval values are adjacent, overlapping, disjoint, contained within one another, etc. etc.

    STARTPOINTOF will "retrieve" the start date from an interval value, ENDPOINTOF will "retrieve" the end date from such an interval value. The other three are the obvious equivalents of the like-named operators of the set algebra (this makes sense since an interval can indeed be thought of as being a set). Obviously, the interval versions of these operators must ensure that the value they produce is indeed still an interval (e.g. the set union of two "contiguous" sets is not necessarily itself a "contiguous" set).

  5. Packed form of a relation

  6. The information contained in the 'world-records' example can be represented in a multitude of ways, of which only the simplest was given. Another relation representing exactly the same information is, e.g., the following :

    NAME DISCIPLINE DURING
    Bob Beamon Long Jump 1968-07-24 - 1995-03-10
    Bob Beamon Long Jump 1992-01-12 - 1998-06-18

    Yet another one might be, e.g. :

    NAME DISCIPLINE DURING
    Bob Beamon Long Jump 1968-07-24 - 1995-03-10
    Bob Beamon Long Jump 1995-03-10 - 1998-06-18

    In the first example, the two tuples both ascribe the world record for the same discipline to the same person, for two different periods, but those periods overlap. In the second example, once again the world record for the same discipline is ascribed to the same person for two different periods, and allthough they no longer overlap, it is still the case that the two periods together form one single, contiguous, span of time.

    In the first example, that causes a form of reduncancy to appear in the database : for the period from 1992-01-12 to 1995-03-10, there are two distinct tuples each saying who held the world record in that particular period. If someone later discovered that this information is actually incorrect, then two distinct tuples would have to be corrected. All such forms of reduncancy are certainly undesirable. The second example does not suffer from this kind of redundancy, but nevertheless it is still a "more complicated" way of saying the very same thing compared to what is also said by the single-tuple example at the beginning of this section. More complexity without additional value, is also undesirable.

    So it is therefore, in general, desirable that the interval values in the database are "as large as possible", without losing or corrupting any information. If a relation heading has at most one interval-typed attribute, then there is exactly one relation that satisfies that criterion. That relation is said to be in "packed form". Relations in packed form have the desirable properties that there are no points within the intervals for which the same logical proposition is implied by two distinct tuples, and that there are no two distinct tuples that can be "merged into one" whilst maintaining the same "information set".

    Since these properties are desirable, it is also desirable that the relational operators always produce relations that are in packed form. That is why, by default, the operators discussed in the foregoing section will ALWAYS produce relations that are in packed form. The following sections will :

    1. discuss the impact that the presence of interval-typed attributes has on the operation and/or results of the relational operators defined in the foregoing section,
    2. discuss all the additional operators supported by SIRA_PRISE for dealing with relations holding interval-typed attributes specifically. These are PACK, UNPACK, UNIONUSING, MINUSUSING, INTERSECTUSING, JOINUSING, and a set of "derivatives" of these including XMINUSUSING, SEMIJOINUSING, SEMIMINUSUSING and LEFTJOINUSING,
    3. discuss whether the "always produces a relation in packed form" is implemented by the operator doing its own explicit invocation of PACK, or just by relying on the input being packed, knowing that its own operation cannot affect pack state of the relation. (If the latter, feeding the operator with a relation that was explicitly UNPACKed, will not produce a packed relation, somewhat contrary to the "results always packed " claim.)
  7. The relational operators and Interval types

    1. PACK

      Most of the time, it is desirable for relations to be in packed form. SIRA_PRISE facilitates that by always packing the results of a relational operator invocation, with one exception, which is when the obvious purpose of the operator invocation is to explicitly obtain unpacked results (see UNPACK). However, when more than one interval-typed attribute is part of the relation, multiple packed forms are possible, and SIRA_PRISE has to choose one "arbitrarily". SIRA_PRISE chooses the one which has the list of PACK attributes in lexicographical order, but sometimes it might be needed to obtain one of the other packed forms. For that purpose, the PACK operator is explicitly exposed.

      The PACK operator takes a relational expression for argument, plus an ordered list of attributes in that relation (all of which must be interval-typed in the input relation). Call that list of interval-typed attributes the "pack list", and call the set of all other attributes the "nonpack" attributes (note that there may be interval-typed attributes of the relation among them). Informally, the results of an invocation of the PACK operator satisfy the following properties :

      • If a combination of point values, covered by the interval values for the attributes in the PACK list, appears in the input relation for a certain combination of attribute values for the attributes in the nonpack list, then exactly one tuple will be in the output relation such that its interval values for the pack list cover the concerned point values, and the nonpack attribute values are the same as the input.
      • The interval values for the pack attributes in the output relation will be as large as possible, with the goal of maximizing interval values for the first attribute in the pack list taking precedence over trying to maximize values for the second, etc. etc.

      Some examples should clarify this a lot :

      relation(body(tuple(x(intinterval(from(4)to(7)))y(intinterval(from(1)to(4)))) tuple(x(intinterval(from(1)to(3)))y(intinterval(from(1)to(13))))))
      PACKing was automaticallly done in lexicographical order (X,Y) :
      X Y
      BEGIN(1)END(8) BEGIN(1)END(5)
      BEGIN(1)END(4) BEGIN(5)END(14)

      Packing that value on (Y,X) :

      Query result :
      ARG PACK_Y_X
      X Y
      BEGIN(1)END(4) BEGIN(5)END(14)
      BEGIN(1)END(8) BEGIN(1)END(5)
      X Y
      BEGIN(1)END(4) BEGIN(1)END(14)
      BEGIN(4)END(8) BEGIN(1)END(5)

      PACK does not guarantee that the result has the minimum possible cardinality :

      PACK can possibly _increase_ the cardinality of the result, compared to the input :
      ARG PACK_Y_X
      X Y
      BEGIN(1)END(10) BEGIN(1)END(10)
      BEGIN(7)END(24) BEGIN(8)END(34)
      X Y
      BEGIN(7)END(10) BEGIN(1)END(34)
      BEGIN(10)END(24) BEGIN(8)END(34)
      BEGIN(1)END(7) BEGIN(1)END(10)

      PACK is also useful for achieving the functionality of TDATRM's / TaRT's "USING equality". Instead of comparing two relations directly using the relation equality operator, compare their packed forms (packed on the same pack list, of course) :

      The EQ column shows the result of EQ(ARG1,ARG2), the EQUSING columns shows the result of EQ(PACK(ARG1 , ...),PACK(ARG2 , ...)) :
      ARG2 ARG1 EQ EQUSING
      X Y
      BEGIN(1)END(4) BEGIN(1)END(14)
      BEGIN(4)END(8) BEGIN(1)END(5)
      X Y
      BEGIN(1)END(4) BEGIN(5)END(14)
      BEGIN(1)END(8) BEGIN(1)END(5)
      False True
    2. UNPACK

      The UNPACK operator from TDATRM is one one would typically want to avoid using as much as possible. Basically, what it does is include a tuple in the result for each and every combination of point values covered by the input relation (that is, covered by the interval values that appear in the relation for the attributes mentioned in the unpack list), with single-point interval values for the attributes specified in an unpack list. However, a use case has been revealed where it can actually serve us well, and that is the case of "generating sequences". If for any valid reason, you need a relation with one tuple for each number in a range (that range must be over an ordinal type otherwise we'd be generating infinite relations), then the UNPACK operator helps you do this at the snap of a finger.

      Unpacking a single interval-typed attribute :
      ARG UNPACK
      II
      BEGIN(1)END(9)
      II
      BEGIN(7)END(8)
      BEGIN(8)END(9)
      BEGIN(3)END(4)
      BEGIN(5)END(6)
      BEGIN(1)END(2)
      BEGIN(6)END(7)
      BEGIN(2)END(3)
      BEGIN(4)END(5)

      Observe that the attribute type for II is still the INTERVAL type, and not the underlying point type. For obtaining the relation holding the series of values of the underlying point type, we still have to apply a transformation :
      TRANSFORM(... , NUMBER(THE_FROM(II))) :

      Query result :
      ARG SERIES
      II
      BEGIN(1)END(9)
      NUMBER
      4
      3
      2
      1
      5
      7
      6
      8

      It should now be obvious why invocations of the UNPACK operator are exempted from the general rule that results from relational operator invocations are always automatically PACKed.

      One final example to illustrate UNPACK's devastating combinatorial explosion (just because we couldn't resist ):

      UNPACK can produce big piles of tuples :
      ARG UNPACK_OVER UNPACK
      II LL DD
      BEGIN(1)END(4) BEGIN(8)END(12) BEGIN(2015-07-30)END(2015-08-02)
      ii,dd,ll
      II LL DD
      BEGIN(2)END(3) BEGIN(10)END(11) BEGIN(2015-07-31)END(2015-08-01)
      BEGIN(1)END(2) BEGIN(10)END(11) BEGIN(2015-07-31)END(2015-08-01)
      BEGIN(3)END(4) BEGIN(10)END(11) BEGIN(2015-07-31)END(2015-08-01)
      BEGIN(1)END(2) BEGIN(8)END(9) BEGIN(2015-07-31)END(2015-08-01)
      BEGIN(1)END(2) BEGIN(9)END(10) BEGIN(2015-07-30)END(2015-07-31)
      BEGIN(2)END(3) BEGIN(9)END(10) BEGIN(2015-07-30)END(2015-07-31)
      BEGIN(2)END(3) BEGIN(8)END(9) BEGIN(2015-07-31)END(2015-08-01)
      BEGIN(3)END(4) BEGIN(11)END(12) BEGIN(2015-08-01)END(2015-08-02)
      BEGIN(2)END(3) BEGIN(11)END(12) BEGIN(2015-08-01)END(2015-08-02)
      BEGIN(3)END(4) BEGIN(8)END(9) BEGIN(2015-07-31)END(2015-08-01)
      BEGIN(1)END(2) BEGIN(11)END(12) BEGIN(2015-08-01)END(2015-08-02)
      BEGIN(2)END(3) BEGIN(11)END(12) BEGIN(2015-07-30)END(2015-07-31)
      BEGIN(3)END(4) BEGIN(11)END(12) BEGIN(2015-07-30)END(2015-07-31)
      BEGIN(2)END(3) BEGIN(9)END(10) BEGIN(2015-08-01)END(2015-08-02)
      BEGIN(3)END(4) BEGIN(9)END(10) BEGIN(2015-08-01)END(2015-08-02)
      BEGIN(1)END(2) BEGIN(9)END(10) BEGIN(2015-08-01)END(2015-08-02)
      BEGIN(3)END(4) BEGIN(9)END(10) BEGIN(2015-07-30)END(2015-07-31)
      BEGIN(1)END(2) BEGIN(11)END(12) BEGIN(2015-07-30)END(2015-07-31)
      BEGIN(1)END(2) BEGIN(11)END(12) BEGIN(2015-07-31)END(2015-08-01)
      BEGIN(3)END(4) BEGIN(11)END(12) BEGIN(2015-07-31)END(2015-08-01)
      BEGIN(3)END(4) BEGIN(9)END(10) BEGIN(2015-07-31)END(2015-08-01)
      BEGIN(1)END(2) BEGIN(8)END(9) BEGIN(2015-08-01)END(2015-08-02)
      BEGIN(3)END(4) BEGIN(8)END(9) BEGIN(2015-07-30)END(2015-07-31)
      BEGIN(1)END(2) BEGIN(8)END(9) BEGIN(2015-07-30)END(2015-07-31)
      BEGIN(3)END(4) BEGIN(10)END(11) BEGIN(2015-08-01)END(2015-08-02)
      BEGIN(2)END(3) BEGIN(9)END(10) BEGIN(2015-07-31)END(2015-08-01)
      BEGIN(1)END(2) BEGIN(9)END(10) BEGIN(2015-07-31)END(2015-08-01)
      BEGIN(2)END(3) BEGIN(8)END(9) BEGIN(2015-07-30)END(2015-07-31)
      BEGIN(1)END(2) BEGIN(10)END(11) BEGIN(2015-07-30)END(2015-07-31)
      BEGIN(2)END(3) BEGIN(10)END(11) BEGIN(2015-08-01)END(2015-08-02)
      BEGIN(2)END(3) BEGIN(8)END(9) BEGIN(2015-08-01)END(2015-08-02)
      BEGIN(1)END(2) BEGIN(10)END(11) BEGIN(2015-08-01)END(2015-08-02)
      BEGIN(2)END(3) BEGIN(10)END(11) BEGIN(2015-07-30)END(2015-07-31)
      BEGIN(3)END(4) BEGIN(8)END(9) BEGIN(2015-08-01)END(2015-08-02)
      BEGIN(2)END(3) BEGIN(11)END(12) BEGIN(2015-07-31)END(2015-08-01)
      BEGIN(3)END(4) BEGIN(10)END(11) BEGIN(2015-07-30)END(2015-07-31)
    3. Restriction

      Restriction is only affected by the existence of interval types, in that the set of operators is extended that can be invoked in its boolean expression. If a relation heading has an interval-typed attribute, then it is only obvious that it should become possible to invoke, e.g., the OVERLAPS() operator using that attribute as one argument and using some other interval value as the second.

      Restriction cannot produce a non-packed relation if its input relation is itself packed. Therefore, RESTRICT will not attempt any packing of itself, and so if the input of RESTRICT is unpacked, then so will be the result :

      Restricting an unpacked relation with the degenerate condition "true" :
      ARG RESTRICT
      II
      BEGIN(3)END(4)
      BEGIN(1)END(2)
      BEGIN(2)END(3)
      II
      BEGIN(3)END(4)
      BEGIN(1)END(2)
      BEGIN(2)END(3)
    4. Projection

      The same obviously does not hold for projection. Assuming the world-records relation was the following value :

      NAME DISCIPLINE DURING
      Bob Beamon Long Jump 1968-07-24 - 1998-06-18
      Mike Powell Long Jump 1998-06-18 -

      Then a projection of this relation over attributes DISCIPLINE and DURING could yield :

      DISCIPLINE DURING
      Long Jump 1968-07-24 - 1998-06-18
      Long Jump 1998-06-18 -

      This relation is not in packed form. The projection operator implemented in SIRA_PRISE will therefore not produce this relation value as its result, but rather the following :

      DISCIPLINE DURING
      Long Jump 1968-07-24 -

      Note the subtle difference in meaning between the two results :

      • the former : A person exists such that throughout DURING, that person held the world record in DISCIPLINE
      • the latter : Throughout DURING, a person exists such that that person held the world record in DISCIPLINE [at least somewhere during that period]
      If the former is what you really need, there is no way to achieve this projection result while leaving the interval attributes intact. You need to TRANSFORM the relation, decomposing the concerned interval-typed attributes into its constituent FROM and TO components, and project that relation.

    5. Extension / Renaming

      These operators are not affected by the possible appearance of interval values in the attributes of the relations they operate on, except then (in the case of extend) in the set of operators that can be invoked by the extend expressions. So when fed unpacked relations, expect them to produce unpacked results :

      Extending an unpacked relation :
      ARG EXTENDSPEC EXTEND
      II
      BEGIN(3)END(4)
      BEGIN(1)END(2)
      BEGIN(2)END(3)
      boolean(true)
      EXTRA II
      True BEGIN(3)END(4)
      True BEGIN(1)END(2)
      True BEGIN(2)END(3)

      Note that EXTEND in particular can produce results that are packed even if the input is unpacked (namely if the extend expressions involve non-injective functions of the point intervals) :

      Extend producing a packed relation from an unpacked one (sort of "by accident") :
      ARG EXTENDSPEC EXTEND
      II
      BEGIN(3)END(4)
      BEGIN(1)END(2)
      BEGIN(2)END(3)
      extra(the_from(ii))
      EXTRA II
      1 BEGIN(1)END(2)
      3 BEGIN(3)END(4)
      2 BEGIN(2)END(3)
    6. Union

      The union operator can obviously cause an overlapping (or adjacency) of tuples in its output, if no special measures are taken. SIRA_PRISE's implementation of the operator does take these special measures :

      Query result :
      ARG2 ARG1 UNION
      II
      BEGIN(2)END(5)
      II
      BEGIN(1)END(4)
      II
      BEGIN(1)END(5)
    7. Unionusing

      If the default behaviour of UNION is not what you need, e.g. you explicitly want the "plain" union that keeps the "overlapping tuples", or you want a packing that is different from the default one (remember that the default packing is on all the interval-typed attributes), you need to use the UNIONUSING operator, which allows you more control over the packing.

      The UNIONUSING operator takes the same arguments as UNION, but has an additional "pack attributes list" argument. If you leave an interval-typed attribute of the relations out of the pack list, then this attribute will not be treated in "pointwise" mode by the UNION, and could possibly yield overlapping values in the result :

      UNION with not all interval-typed attributes in "pointwise" mode :
      ARG1 ARG2 USINGSPEC UNIONUSING
      II
      BEGIN(1)END(4)
      II
      BEGIN(2)END(5)
      ()
      II
      BEGIN(1)END(4)
      BEGIN(2)END(5)
    8. Intersection

      Supposing that the world-record history for each discipline is kept in distinct relations, we might have the following relations (for, say, long-jump and 100m respectively) :

      NAME DURING
      Bob Beamon 1968-07-24 - 1998-06-18
      NAME DURING
      Bob Beamon 1968-02-24 - 1969-05-05

      It is obvious that queries of the nature "Which athletes have been the world-record holder for both the long-jump and the 100m ?" should be answered using the intersection operator. But the intersection operator as defined before, would produce an empty relation, because there is no tuple that appears in both relations ! Indeed, the DURING attribute in both tuples is unequal. This problem is dealt with by saying that when the intersection operator is applied to relations holding interval-typed attributes, it is sufficient that the interval-typed attribute values overlap (instead of having to be equal), and that the value returned for such an attribute is the interval intersection of the attribute values in the "intersected tuples".

      In the example, this would yield the relation :

      NAME DURING
      Bob Beamon 1968-07-24 - 1969-05-05

      And that's indeed the period during which, according to the relations of the example, Bob Beamon held the world record in both disciplines.

      (Allthough it has nothing to do with the RA per se, this example also illustrates an issue that is crucial enough in temporal database design to mention it explicitly here : whether this result is indeed the correct answer to the stated problem, is somewhat doubtful. The stated problem was "Which athletes have been the world-record holder for both the long-jump and the 100m ?". Note carefully that there is no mention of a requirement to hold a world record in both disciplines _at the same moment in time_. Nor is there any mention of a relaxation that both world records must not have been held _at the same moment in time_. This issue has more to do with how we express our queries in natual language (and how apt or inapt natural language happens to be for that purpose), but especially when dealing with temporal information, it is an important potential source of misunderstandings between users and IT people.)

      To revert to our actual subject, we continue with a question that might have arisen. If the intersection operator is "re-defined" to treat interval values by checking, not whether they are equal, but instead only whether they overlap, then what do I do if I really want the check to be for equality ? In our example, how do I get the intersection operator to produce an empty relation value, precisely on account of the fact that the intervals are not equal ? It will not usually be the case that this behaviour is the needed or desired one, but it cannot in general be excluded either.

      So obviously, the conclusion seems to be that it must be possible for the user to specify which of the two conditions ("overlap" vs. "equal") must be used for some particular invocation of the operator. Furthermore, this must be possible for each individual interval-typed attribute that the relations have. Indeed, it might be the case that there is more than one interval-typed attribute in the relation, and that for some particular invocation of intersect, the "equality" behaviour is desired for one of those attributes, but the "overlaps" behaviour for the other. That problem is addressed by the INTERSECTUSING operator.

    9. INTERSECTUSING

      Analogous to UNIONUSING, the intersection operator also has an additional version that allows the user more control over the intersection and packing behaviour :

      Intersection with interval-typed attributes not treated in "pointwise" modus :
      ARG2 ARG1 USINGSPEC INTERSECTUSING
      II
      BEGIN(2)END(5)
      II
      BEGIN(1)END(4)
      ()
      II
    10. Difference

      It will now be intuitively obvious how the relational difference operator deals with interval types. Supposing the world-record relations are as in the intersection example, but the question is now "Which athletes have been (and during which period have they been) world-record holder for the 100m, but not for the long-jump ?".

      The answer to this question is given by invoking the relational difference operator, that is defined to deal with interval values such as to return :

      NAME DURING
      Bob Beamon 1968-02-24 - 1968-07-24

      So the relational difference operator deals with interval values by computing their interval difference, and including a tuple in the result only if that interval difference "still contains at least one point".

    11. MINUSUSING

      It will also be intuitively obvious how the relational difference operator also comes in a version that allows the user more control over the "difference" behaviour and over the packing :

      Relational difference with interval-typed attributes not treated in "pointwise" modus :
      MINUEND SUBTRAHEND USINGSPEC MINUSUSING
      II
      BEGIN(1)END(4)
      II
      BEGIN(2)END(5)
      ()
      II
      BEGIN(1)END(4)
    12. Join

      If in an invocation of the join operator, the set of join attributes contains an interval-typed attribute, then join deals with that attribute in exactly the same way as defined for intersection : it is not necessary for the interval values to be equal for a tuple to be included in the result of the join, instead it is sufficient that they overlap (i.e. have at least one value of their "underlying type" in common). The value returned for that attribute in the result of the join is the interval intersection of both interval values.

    13. JOINUSING

      It will also be intuitively obvious how the join operator also comes in a version that allows the user more control over the "difference" behaviour and over the packing :

      JOIN with some interval-typed attributes not treated in "pointwise" modus :
      ARG1 ARG2 USINGSPEC JOINUSING
      II
      BEGIN(1)END(5)
      II
      BEGIN(3)END(7)
      ()
      II
    14. Division

      Division is a problematic operator to define a "temporal" counterpart for. The most important reason for this state of affairs being, I believe, that there is no single, unique sensible way to incorporate the "temporal" aspect into the formulation of the kind of queries that relational division was aimed to solve.

      Recall from 4.4.9 that division was aimed to solve the kind of query like "get the list of customers who already have all possible types of insurance policy", or "employees who have followed all training programs they were eligible for", or some such.

      There is no single and universally applicable answer to the question "Must those customers have had all possible types of policy at the same point in time, or is it sufficient that they have had at least one policy of all possible types at just any point in time -not necessarily the same point in time- ?". Nor is it obvious whether "all possible types of policy" refers to "all types of policy that were possible at one particular moment in time" or to "all types of policy that have been possible throughout all times", or still some other different possible interpretation.

      For this reason (and possibly still others), a temporal counterpart to relational division is simply not defined. The relational division operator, if, when and where supported, therefore operates on relations holding interval-typed attributes in exactly the same way as it does on relations not holding such attributes. It is, however, very unlikely that the results produced by relational division when interval-typed attributes are in play, can make very much sense.

    15. Semijoin

      In section 4.4.10, the semijoin operator was defined to be equivalent to the projection of a join of the two arguments. The semijoin of relations holding interval-typed attributes is defined in the same way. But note that the result of the operator is influenced by how the "join" part of the operator deals with interval-typed values. Note that despite the fact that the "outer" operator of the equivalent expression is projection, which potentially gives rise to non-packed relations, this phenomenon cannot occur with semijoin.

    16. Using Semijoin

      Just like the "basic" join operator, semijoin comes with an additional "using" variant that gives the user more control over which interval-typed attributes are treated in "pointwise" modus, and which as "regular scalar attributes". The definition is analogous to that of "default" semijoin : It is the projection onto the attributes of the first argument, of the using-join of the two arguments for the specified pack attributes list.

    17. Semidifference

      Like semijoin, the definition of semidifference does not need to be altered for dealing with interval-typed attributes.

    18. Using Semidifference

      Just like the "basic" join operator, semiminus comes with an additional "using" variant that gives the user more control over which interval-typed attributes are treated in "pointwise" modus, and which as "regular scalar attributes". The definition is analogous to that of "default" semijoin : Its details should be obvious and are not specified here.

    19. Symmetric difference

      Earlier on, the symmetric difference operator was defined to be a shorthand for some specific combination of relational unions, differences and intersections. This means that symmetric difference "inherits" the way interval-typed attributes are treated, from the UNION, MINUS and INTERSECT operators in terms of which it is defined.

      If this is not what the user needs, the XMINUSUSING operator is offered as a solution, which is the obvious (i.e. analogous to XMINUS) shorthand for a similar combination of UNIONSUSINGs, MINUSUSINGs and INTERSECTUSINGs.

    20. Using Symmetric difference

      The XMINUSUSING operator is the obvious (i.e. analogous to XMINUS) shorthand for a similar combination of UNIONSUSINGs, MINUSUSINGs and INTERSECTUSINGs.

    21. left join

      Earlier on, the left join operator was defined to be a shorthand for some specific combination of relational join, union, extend and semiminus. This means that left join "inherits" the way interval-typed attributes are treated, from the UNION, JOIN, SEMIMINUS and EXTEND operators in terms of which it is defined. Note in particular that as a consequence of this definition, there are possibly two distinct sets of pack attributes in play :

      • The one that applies to the JOIN and SEMIMINUS parts, which are only the interval-typed attributes that are common to the two relations, and
      • The one that applies to the UNION part, which are all the interval-typed attributes of the left join's first argument

      There is a difference between these two if the left join's first argument has any interval-typed attribute that the second argument does not have. In intricate and/or exotic cases, this may cause results that may look rather weird at first sight.

    22. LEFTJOINUSING

      The LEFTJOINUSING operator is the obvious (i.e. analogous to LEFTJOIN) shorthand for a similar combination of UNIONSUSINGs, EXTENDs, SEMIMINUSUSINGs and JOINUSINGs.

      Note however that LEFTJOINUSING will take _only a single_ list of pack attributes and will apply this single list of pack attributes to both the UNIONSUSING part and the SEMIMINUSUSING/JOINUSING part. There is NO way to take control over the "USING" that applies to the UNION part, separately from taking control over the "USING" that applies to the SEMIMINUSUSING/JOINUSING parts.

    23. Transitive closure

      Defining a "temporal counterpart" for transitive closure is somewhat subject to the very same problem as defining a "temporal counterpart" for relational division.

      So despite the fact that "parts explosions" and similar problems regularly show up in the IT world, and despite the fact that "attaching a temporal connotation" to this kind of information is quite conceivable, a "temporal counterpart" of the operator that is aimed to address this category of problems is currently not defined.

    24. Group/Ungroup

      The group operator is affected in two distinct ways by the possible occurrence of interval-typed attributes, the first of which is the case when there are multiple group specifications. Consider the following hypothetical relation value :

      NAME DISCIPLINE DURING
      Bob Beamon Long Jump 1968-07-24 - 1998-06-18
      Bob Beamon 100m 1968-02-24 - 1969-05-05

      If this relation were grouped (without "special measures" to cater for the interval-typed attributes) per NAME, with the two grouping specificiation RVA_DISCIPLINE(DISCIPLINE) and RVA_DURING(DURING), then the relation-valued attribute RVA_DURING would contain a relation with two tuples, each holding a DURING value that overlaps.

      The second way in which GROUP is affected by the presence of interval-typed attributes, is best illustrated by considering the foregoing hypothetical relation, and how it must be processed in order to obtain the answer to the query "For each distinct set of disciplines that Bob Beamon has been world record holder in, show the period during which he held the world record in all of the disciplines in that set". The result would have to be something like this :

      NAME DISCIPLINES DURING
      Bob Beamon
      DISCIPLINE
      100m
      1968-02-24 - 1968-07-24
      Bob Beamon
      DISCIPLINE
      100m
      Long Jump
      1968-07-24 - 1969-05-05
      Bob Beamon
      DISCIPLINE
      Long Jump
      1969-05-05 - 1998-06-18

      Obtaining such results is the subject of TDATRM's USING-GROUP operator. Note that SIRA_PRISE currently does not support such an operator (it's on the todo list), and obtaining these resutls is possible only if :

      • The interval type is based on an ordinal type (meaning all of NEXT,FIRST,LAST and PRIOR) are available for the underlying point type, and
      • UNPACK is used explicitly to obtain a relation with single-point interval values that can be grouped over on a per-day basis, after which
      • PACK is used to re-group the tuples that have the same DISCIPLINES RVA value for adjacent days.

      Ungroup is also affected in the multi-element ungroup version. Consider following relation :

      NAME RVA_DISCIPLINE RVA_DURING
      Bob Beamon rva_dis1 rva_dur1
      Bob Beamon rva_dis2 rva_dur2

      where the respective relation values of the RVA_ attributes are as follows :

      rva_dis1

      DISCIPLINE
      Long Jump
      100m

      rva_dis2

      DISCIPLINE
      Long Jump

      rva_dur1

      DURING
      1968-07-24 - 1998-06-18

      rva_dur2

      DURING
      1968-02-24 - 1969-05-05

      Note that this relation cannot possibly be produced as the result of an invocation of the group operator. Nevertheless, under some interpretations, it is possible to define a result for a multi-element ungroup invocation on this relation.

      Under such an interpretation, overlapping tuples could potentially be produced for the longjump discipline :

      NAME DISCIPLINE DURING
      Bob Beamon Long Jump 1968-07-24 - 1998-06-18
      Bob Beamon Long Jump 1968-02-24 - 1969-05-05
      Bob Beamon 100m 1968-02-24 - 1969-05-05

      To repeat, such a multi-element version of ungroup is not commonly agreed upon.

    25. Aggregate / Summarizeby

      The complications that arise when interval types and data aggregations come together are so great that it is beyond the scope of this introductory text to treat the subject. (For one, note that SUMMARIZEBY has connotations similar to GROUP, so if interval-typed attributes are part of the "BY" key, it can be expected that "partitioning" according to the overlapping of the interval values in those attributes will be required, just as it is for USING-GROUP discussed in the previous section.)

  8. A remark on associativity

  9. The relational operators UNIONUSING, INTERSECTUSING, XMINUSUSING and JOINUSING have been discussed here in their most common form, taking two relational arguments plus a pack specification. However, these four operators also "inherit" the property of associativity from their counterparts UNION,JOIN,INTERSECT and XMINUS. It is therefore desirable to also support invocations of the "USING" versions of these operators that take 3,4,..., any number of relations as an argument. SIRA_PRISE supports this, but there is a convention to be followed regarding where in the argument list the pack attributes list is to be specified. That convention is as follows : the USING versions of these four operators will always try to interpret the _LAST_ argument as the pack attributes list.

    As is the case with the "standard" verions of these operators, the theoretical possibility of invocations of these operators with only one argument, or with no arguments at all, is syntactically not supported by SIRA_PRISE. Unlike the "standard" versions of these operators, it is also impossible to use these four associative "USING" operators as an aggregation operator within an AGGREGATE invocation, since no syntactic device is available to specify the using list, inside the context of an aggregation spec.