RAL package reference: relation

NAME

relation -
Operators for Relation Values

SYNOPSIS

package require ral 0.7
::ral::relation cardinality relationValue
::ral::relation degree relationValue
::ral::relation divide dividend divisor mediator
::ral::relation eliminate relationValue  ? attribute ... ? 
::ral::relation emptyof relationValue
::ral::relation extend relationValue tupleVariable  ? attr1 type1 expr1 attr2 type2 expr2 ... ? 
::ral::relation foreach tupleVariable relationValue  ? ascending | descending ?   ? attr-list ?  script
::ral::relation group relationValue newattribute  ? attr1 attr2 ... ? 
::ral::relation heading relationValue
::ral::relation identifiers relationValue
::ral::relation intersect relationValue1 relationValue2  ? relationValue3 ... ? 
::ral::relation is relationValue1 compareop relationValue2
::ral::relation isempty relationValue
::ral::relation isnotempty relationValue
::ral::relation join relationValue1 relationValue2  ? joinAttrs1 joinAttrs2 ... ? 
::ral::relation list relationValue
::ral::relation minus relationValue1 relationValue2
::ral::relation project relationValue  ? attr1 attr2 ... ? 
::ral::relation rename relationValue  ? oldname newname ... ? 
::ral::relation restrict relationValue tupleVariable expression
::ral::relation restrictone relationValue name-value-list
::ral::relation semijoin relationValue1 relationValue2  ? attr1 attr2 ... ? 
::ral::relation semiminus relationValue1 relationValue2  ? attr1 attr2 ... ? 
::ral::relation summarize relationValue perRelation attr type summary initialValue
::ral::relation times relationValue1 relationValue2  ? relationValue3 ... ? 
::ral::relation tuple relationValue
::ral::relation ungroup relationValue attribute
::ral::relation union relationValue1 relationValue2  ? relationValue3 ... ?

This manpage describes the relation command. The relation command is part of the Tcl Relational Algebra Library (ral) package. The relation command defines a set of operators on relations that constitute the formal algebra of relations that is supported by TclRAL. The algebra is patterned after that described by Date (Date, C.J., An Introduction to Database Systems, 8th ed, Pearson Education, 2004, ISBN 0-321-19784-4, chap. 7)

Formally a relation has a heading and a body. The heading, like a tuple heading, defines the attribute names and data types of the components of the relation. The body consists of tuples, all of which match the heading. A relation also has one or more identifiers (also known as candidate keys). Each identifier consists of one or more attributes of the relation and every tuple in the body of the relation will be unique in all their values with respect to all the identifiers. Because relations are fundamentally sets, several things should be noted:

There is no left to right ordering of the attributes. Like tuples, relations have no real left to right ordering. The implementation may choose to store attributes in any order and users should not depend upon certain string representations nor operate on relations with any operators other than those given here.
There is no top to bottom ordering of tuples. Again the implementation is free to store tuples in any order it chooses. There are no indexing operations that depend upon a tuple at some fixed location.
There are no duplicate tuples and there is no concept of a NULL value. Relations are sets and sets do not have duplicates. All attributes of all tuples of a relation must contain a valid value of the data type defined for that attribute.

Note that all the operators are read only in the sense that they operate on relation values without modifying them. All of these operators return either a new relation or scalar value and do not modify the relation arguments. Only the relvar command can modify a relation variable in place.

STRING REPRESENTATION

Like any Tcl value, relations have a string representation. The string representation of a relations is a specially formatted list consisting of four elements:

The keyword Relation.
The relation heading.
The identifiers of the relation.
The relation body.

The relation heading is a even numbered list consisting of alternating attribute names and attribute data types. It is the same form as a tuple heading.

The identifiers (candidate keys) of a relation are specified as a list. Each identifer list element is in turn a list containing the attribute names that constitute the identifier. Every relation must have at least one identifier.

The body of a relation consists of a list of tuples. Each tuple in the body is in a list containing an even number of elements consisting alternately of an attribute name and an attribute value.

The following is a literal string representation of a relation with one tuple in its body.

{Relation {DogName string Breed string} DogName {{DogName Fido Breed Poodle}}}

EXAMPLE

In the command descriptions that follow, we will often refer to the example data given below. We presume the relations were created with the relvar command and for brevity we assume that the necessary commands have been imported into the namespace of the example.

DOG
DogName      Breed
 string     string
==================
   Fido     Poodle
    Sam     Collie
   Spot    Terrier
  Rover  Retriever
   Fred    Spaniel
 Jumper       Mutt

OWNER
OwnerName  Age           City
   string  int         string
=============================
      Sue   24      Cupertino
   George   35      Sunnyvale
    Alice   30       San Jose
     Mike   50       San Jose
      Jim   42  San Francisco

OWNERSHIP
OwnerName  DogName  Acquired
   string   string    string
============================
      Sue     Fido      2001
      Sue      Sam      2000
   George     Fido      2001
   George      Sam      2000
    Alice     Spot      2001
     Mike    Rover      2002
      Jim     Fred      2003

COMMANDS

::ral::relation cardinality relationValue

The cardinality subcommand returns the number tuples contained in the body of relationValue.

% relation cardinality [relvar set DOG]
6
% relation cardinality [relvar set OWNERSHIP]
7

::ral::relation degree relationValue

The degree subcommand returns the number of attributes in the tuples of relationValue

% relation degree [relvar set DOG]
2

::ral::relation divide dividend divisor mediator

The divide subcommand implements the relational divide operation. The headings of dividend and divisor must be disjoint and the heading of mediator must be the union of the dividend and divisor headings. The returned result is a new relation that has the same heading as dividend and contains all the tuples from dividend whose corresponding tuples in mediator include all the tuples in divisor. Using the data from our ongoing example, then the following example shows how division can be used to find all the Dogs owned by both Sue and George.

set dividend [relation project [relvar set DOG] DogName]
puts [relformat $dividend Dividend:]
Dividend:
---------
DogName
 string
=======
   Fido
    Sam
   Spot
  Rover
   Fred
 Jumper

set divisor [relation project [relation restrict [relvar set OWNER] t\ 
    {[tuple extract $t OwnerName] eq "Sue" ||\ 
    [tuple extract $t OwnerName] eq "George"}] OwnerName]
puts [relformat $divisor Divisor:]
Divisor:
--------
OwnerName
   string
=========
      Sue
   George

set mediator [relation eliminate [relvar set OWNERSHIP] Acquired]
puts [relformat $mediator Mediator:]
Mediator:
---------
OwnerName  DogName
   string   string
==================
      Sue     Fido
      Sue      Sam
   George     Fido
   George      Sam
    Alice     Spot
     Mike    Rover
      Jim     Fred

set quotient [relation divide $dividend $divisor $mediator]
puts [relformat $quotient "All dogs owned by both Sue and George"]
All dogs owned by both Sue and George
-------------------------------------
DogName
 string
=======
   Fido
    Sam

::ral::relation eliminate relationValue ? attribute ... ?

The eliminate subcommand returns a new relation that has a heading equal to that of the relationValue less any attributes whose names are given in the attribute arguments. The body of the new relation is the same as the body of relationValue removing any tuples that might be duplicated as a result of removing the attributes. The eliminate subcommand complements the project command in the sense that eliminate specifies which attributes to discard and project specifies which attribute to keep.

% relformat [relation eliminate [relvar set DOG] Breed]
DogName
 string
=======
   Fido
    Sam
   Spot
  Rover
   Fred
 Jumper

::ral::relation emptyof relationValue

The emptyof subcommand returns a new relation that has the same heading as relationValue but whose cardinality is zero.

::ral::relation extend relationValue tupleVariable ? attr1 type1 expr1 attr2 type2 expr2 ... ?

The extend subcommand returns a new relation which has the same heading as relationValue with zero or more additional attributes. The first additional attribute is given by attr1 which has type type1 and its value is set to the result returned by passing expr1 to the expr command. Subsequent attributes are treated similarly. As each tuple in the body of relationValue is considered, its value is set into the variable whose name is given by the tupleVariable argument. This variable is accessible to the extending expressions so that the current tuple values of relationValue are available for computing the values of the new attributes.

% relformat [relation extend [relvar set OWNER] owner\ 
    AgeInMonths int {[tuple extract $owner Age] * 12}]
OwnerName  Age           City  AgeInMonths
   string  int         string          int
==========================================
      Sue   24      Cupertino          288
   George   35      Sunnyvale          420
    Alice   30       San Jose          360
     Mike   50       San Jose          600
      Jim   42  San Francisco          504

::ral::relation foreach tupleVariable relationValue ? ascending | descending ? ? attr-list ? script

The foreach subcommand provides a means to iterate through the body of a relation. For each tuple in the body of relationValue, the tupleVariable variable is assigned a value of a tuple and script is executed. The order in which the tuples are considered is unspecified unless the list of sorting attributes is specified. In this case the tuples are visited in the ascending order of the values of the sorting attibutes if the direction keyword of ascending is supplied or if no direction keyword is given. Tuples can be visited in descending order of the sorting attributes if the descending keyword is given.

% relation foreach d [relvar set DOG] descending DogName {
    puts [tuple extract $d DogName]
}
Spot
Sam
Rover
Jumper
Fred
Fido

::ral::relation group relationValue newattribute ? attr1 attr2 ... ?

The group subcommand creates a new relation from relationValue that contains an attribute which is of type Relation. The newattribute argument gives the name of the relation valued attribute and the attrN arguments give the names of attributes in relationValue that are to be assembled into a relation value. The returned relation has a heading that is the same as relationValue minus the attributes given in the attrN arguments plus the new relation attribute given by newattribute. The resulting body has tuples for each unique set of values for the remaining ungrouped attributes in the original relation with the corresponding part of the tuple placed in the new relation valued attribute. See also the ungroup subcommand for the complementary operation.

relation group [relvar set OWNERSHIP] DogAcquisition Dogname Acquired
OwnerName     DogAcquisition
   string           Relation
           DogName  Acquired
            string    string
============================
      Sue     Fido      2001
               Sam      2000
   George     Fido      2001
               Sam      2000
    Alice     Spot      2001
     Mike    Rover      2002
      Jim     Fred      2003

::ral::relation heading relationValue

The heading subcommand returns tuple heading of the relation. This is an even numbered list consisting of alternating attribute names and attribute data types.

% relation heading [relvar set DOG]
DogName string Breed string

::ral::relation identifiers relationValue

The identifiers subcommand returns the set of identifiers for the relation. The identifiers are returned as a list each element of which is in turn a list of attribute names that constitute the identifer.

::ral::relation intersect relationValue1 relationValue2 ? relationValue3 ... ?

The intersect subcommand returns the set intersection of two or more relations. All relations must be of the same type. The result relation has a heading that is the same as any of the arguments and has a body consisting of all tuples present in all of the relationValue arguments. Since the intersection operation is both associative and commutative, the order of the relationValue arguments has no effect the result.

::ral::relation is relationValue1 compareop relationValue2

The is subcommand returns a boolean value based on performing a comparison operation between two relation values. Allowed values of compareop are:

equal: Returns 1 if relationValue1 is equal to relationValue2.
notequal: Returns 1 if relationValue1 is not equal to relationValue2.
propersubsetof: Returns 1 if relationValue1 is a proper subset of relationValue2.
subsetof: Returns 1 if relationValue1 is a subset of relationValue2.
propersupersetof: Returns 1 if relationValue1 is a proper superset of relationValue2.
supersetof: Returns 1 if relationValue1 is a superset of relationValue2.

Both relationValue1 and relationValue2 must be of the same type to be compared.

::ral::relation isempty relationValue

The isempty subcommand returns the boolean value "1" if the body of relationValue does not contain any tuples and "0" otherwise. The isempty subcommand is a convenient short hand for the the command expr {[::ral::relation cardinality relationValue] == 0}.

::ral::relation isnotempty relationValue

The isnotempty subcommand returns the boolean value "1" if the body of relationValue contains any tuples and "0" otherwise. The isnotempty subcommand is a convenient short hand for the the command expr {[::ral::relation cardinality relationValue] != 0}.

::ral::relation join relationValue1 relationValue2 ? joinAttrs1 joinAttrs2 ... ?

The join subcommand performs the natural join of relationValue1 with relationValue2. The join is performed across the given joinAttrsN. If no joinAttrsN are given, then the join is performed across attributes with the same name in both relations (because of the rename subcommand it is always possible to arrange for the relations to have common names for the join attributes). If present, the joinAttrsN are lists consisting of one or two elements. If a joinAttrsN list contains a single element then that element gives the name of a join attribute in both relationValue1 and relationValue2. If the joinAttrsN list contains two elements then the first element gives the name of a join attribute in relationValue1 and the second element gives the name of a join attribute in relationValue2. The heading of the resulting relation consists of all the attibutes of relationValue1 plus all the attributes of relationValue2 minus any of the join attributes from relationValue2. The body of the resulting relation consists all tuples composed from the tuples in both relationValue1 and relationValue2 where the values of the join attributes in relationValue1 equal those of relationValue2.

% relformat [relation join [relvar set OWNERSHIP] [relvar set DOG]]
OwnerName  DogName  Acquired      Breed
   string   string    string     string
=======================================
      Sue     Fido      2001     Poodle
      Sue      Sam      2000     Collie
   George     Fido      2001     Poodle
   George      Sam      2000     Collie
    Alice     Spot      2001    Terrier
     Mike    Rover      2002  Retriever
      Jim     Fred      2003    Spaniel

::ral::relation list relationValue

The list subcommand returns the body of relationValue as a proper Tcl list. RelationValue must be of degree one or an error is returned. The list subcommand is complementary to the tuple subcommand in the sense that it provides proper Tcl list for a relation of degree one where the tuple subcommand provides a single tuple for a relation of cardinality one. Note also that the list returned by the list subcommand is a proper set since there are not duplicates in a relation.

% relation list [relation project [relvar set OWNERSHIP] Acquired]]
2001 2000 2002 2003

::ral::relation minus relationValue1 relationValue2

The minus subcommand returns the set difference between two relations. The relationValue arguments must be of the same type and that is the type of the result relation. The body of the result consists of those tuples present in relationValue1 but not present in relationValue2. Note that the order of the relationValue1 and relationValue2 arguments is significant to the result.

::ral::relation project relationValue ? attr1 attr2 ... ?

The project subcommand returns a relation whose heading consists of only those attributes listed in the attrN arguments. The body of the result consists of tuples the corresponding tuples from relationValue, removing any duplicates created by considering only a subset of the attributes.

% relformat [relation project [relvar set OWNER] City]
         City
       string
=============
    Cupertino
    Sunnyvale
     San Jose
San Francisco

::ral::relation rename relationValue ? oldname newname ... ?

The rename subcommand returns a relation whose heading has each oldname attribute changed to newname and whose body is the same as relationValue. An arbitrary number of oldname / newname pairs may be given. Renaming is processed from left to right in the command arguments and it is not an error to change the name of any given attribute multiple times. However, oldname must always be the name of an attribute at the time the rename takes place. The rename subcommand is useful for manipulating the attribute names of a relation to suit the needs of particular operators (e.g. times and join).

::ral::relation restrict relationValue tupleVariable expression

The restrict subcommand returns a new relation that is a subset (possibly improper) of relationValue. Each tuple in the body of relationValue is successively assigned to tupleVariable and expression is evaluated. The resulting relation has a heading that is the same as relationValue and a body consisting of all tuples where expression evaluated to true.

% relformat [relation restrict [relvar set DOG] d {[tuple extract $d DogName] eq "Fred"}]
DogName    Breed
 string   string
================
   Fred  Spaniel

::ral::relation restrictone relationValue name-value-list

The restrictone subcommand returns a new relation that has the same heading as relationValue and a body consisting of the set of tuples in relationValue whose identifying attribute values match those contained in name-value-list The cardinality of the returned relation will necessarily then be either 0 or 1. The name-value-list must be list containing an even number of elements which are attribute names alternating with attribute values. The set of attribute names in name-value-list must form one of the identifiers of relationValue. If relationValue contains a tuple whose attribute values match those in name-value-list then the returned relation will contain that single tuple. Otherwise the returned relation has cardinality 0. This subcommand is useful in those contexts where the attribute values of an identifier are known and evaluating an expression over all the tuples in relationValue is superfluous.

% relformat [relation restrictone [relvar set DOG] {DogName Fred}]
DogName    Breed
 string   string
================
   Fred  Spaniel

% relformat [relation restrictone [relvar set DOG] {DogName Jane}]
DogName    Breed
 string   string
================

::ral::relation semijoin relationValue1 relationValue2 ? attr1 attr2 ... ?

The semijoin subcommand computes the join of relationValue1 and relationValue2 but eliminates all of the attributes of relationValue2 (or alternatively speaking, projecting all attributes of relationValue1). The returned relation has a heading the same a relationValue1 and a body consisting of those tuples in relationValue1 that would have been included in the natural join with relationValue2. As with join, if the attrN arguments are missing, the join is computed across the attributes in relationValue1 and relationValue2 that are named the same. Otherwise the attrN arguments are treated the same as for the join subcommand. For example, to find all the dogs that have some owner:

relformat [relation semijoin [relvar set DOG] [relvar set OWNERSHIP]]
DogName      Breed
 string     string
==================
   Fido     Poodle
    Sam     Collie
   Spot    Terrier
  Rover  Retriever
   Fred    Spaniel

::ral::relation semiminus relationValue1 relationValue2 ? attr1 attr2 ... ?

The semiminus subcommand computes the difference between relationValue1 and the semijoin of relationValue1 and relationValue2. The returned relation has a heading equal to that of relationValue1 and a body consisting of those tuples from relationValue1 which would not have been included in the natural join of relationValue1 and relationValue2. The optional attrN arguments are treated in the same way as for the join subcommand. For example, to find all dogs that have no owner:

relformat [relation semiminus [relvar set DOG] [relvar set OWNERSHIP]]
DogName   Breed
 string  string
===============
 Jumper    Mutt

::ral::relation summarize relationValue perRelation attr type summary initialValue

The summarize subcommand allows for computations across sets of attributes. The perRelation must be of the same type as a projection of relationValue. The returned relation has the same heading as perRelation extended by attr. The attr gives the name of the new attribute. The name of the new attribute may not match any existing attributes in perRelation. The type argument is data type of the new attribute. The body of the returned relation consists of all the tuples of perRelation with a value for the new attribute. That value is computed by treating summmary as a command prefix and invoking it for all the tuples in relationValue that match the corresponding attributes in perRelation. When summary is invoked, it is given two additional arguments. The first argument is the value returned from the previous invocation of summary for the given tuple in the result. Upon the first invocation of summary for a tuple in the result initialValue is given as the first argument. The second argument is the tuple in relationValue that matches the current tuple under consideration in perRelation. The summary command is expected to return a result of the same type as the new attribute and that result is passed to subsequent invocations of summary. In this example we determine the years when dogs were acquired and the number of dogs acquired in each year.

proc count_tuples {value t} {
    # tuple "t" is ignored for counting
    return [expr {$value + 1}]
}
relformat [relation summarize [relvar set OWNERSHIP]\ 
    [relation project [relvar set OWNERSHIP] Acquired]\ 
    NumAcquired int count_tuples 0]
Acquired  NumAcquired
  string          int
=====================
    2001            3
    2000            2
    2002            1
    2003            1

::ral::relation times relationValue1 relationValue2 ? relationValue3 ... ?

The times subcommand returns the extended Cartesian product of two or more relations. The heading of the result is the union of the headings of all the relationValue arguments. The body of the result consists of a tuple for all combinations of the tuples in all the relationValue arguments. Since the relational multiplication operation is both associative and commutative, the order of the relationValue arguments has no effect on the result.

% relformat [relation times [relvar set DOG] [relvar set OWNER]]
DogName      Breed  OwnerName  Age           City
 string     string     string  int         string
=================================================
   Fido     Poodle        Sue   24      Cupertino
   Fido     Poodle     George   35      Sunnyvale
   Fido     Poodle      Alice   30       San Jose
   Fido     Poodle       Mike   50       San Jose
   Fido     Poodle        Jim   42  San Francisco
    Sam     Collie        Sue   24      Cupertino
    Sam     Collie     George   35      Sunnyvale
    Sam     Collie      Alice   30       San Jose
    Sam     Collie       Mike   50       San Jose
    Sam     Collie        Jim   42  San Francisco
   Spot    Terrier        Sue   24      Cupertino
   Spot    Terrier     George   35      Sunnyvale
   Spot    Terrier      Alice   30       San Jose
   Spot    Terrier       Mike   50       San Jose
   Spot    Terrier        Jim   42  San Francisco
  Rover  Retriever        Sue   24      Cupertino
  Rover  Retriever     George   35      Sunnyvale
  Rover  Retriever      Alice   30       San Jose
  Rover  Retriever       Mike   50       San Jose
  Rover  Retriever        Jim   42  San Francisco
   Fred    Spaniel        Sue   24      Cupertino
   Fred    Spaniel     George   35      Sunnyvale
   Fred    Spaniel      Alice   30       San Jose
   Fred    Spaniel       Mike   50       San Jose
   Fred    Spaniel        Jim   42  San Francisco
 Jumper       Mutt        Sue   24      Cupertino
 Jumper       Mutt     George   35      Sunnyvale
 Jumper       Mutt      Alice   30       San Jose
 Jumper       Mutt       Mike   50       San Jose
 Jumper       Mutt        Jim   42  San Francisco

::ral::relation tuple relationValue

The tuple subcommand returns the body of relationValue as a tuple. The cardinality of relationValue must be one or an error is returned.

::ral::relation ungroup relationValue attribute

The ungroup subcommand maps relations that have relation valued attributes to relations that have scalar valued attributes. It is the complementary operation to the group command. The attribute argument must be the name of a relation valued attribute of relationValue. The returned relation has a heading consisting of all the attributes of relationValue minus attribute plus all the attributes of the attribute relation. The body of the returned relation consists of tuples composed of pairing each tuple from the attribute attribute with its corresponding components from relationValue.

set da [relation group [relvar set OWNERSHIP] DogAcquisition Dogname Acquired]
relformat [relation ungroup $da DogAcquisition]
OwnerName  DogName  Acquired
   string   string    string
============================
      Sue     Fido      2001
      Sue      Sam      2000
   George     Fido      2001
   George      Sam      2000
    Alice     Spot      2001
     Mike    Rover      2002
      Jim     Fred      2003

::ral::relation union relationValue1 relationValue2 ? relationValue3 ... ?

The union subcommand returns the set union of two or more relations. All relations must be of the same type. The result relation has a heading that is the same as any of the arguments and has a body consisting of all tuples present in any of the relationValue arguments. Since the union operation is both associative and commutative, the order of the relationValue arguments has no effect the result.

KEYWORDS

relation, tuple, body