foundations of computational agents
Relations are common in AI and database systems. The relational algebra defines operations on relations and is the basis of relational databases.
A scope is a set of variables. A tuple on scope , has a value on each variable in its scope. A variable can be seen as a function on tuples; one that returns the value for that variable for that tuple. We write to be the value of tuple on variable . The value of must be in . This is like the mathematical notion of tuple, except the index is given by a variable, not by an integer.
A relation is a set of tuples, all with the same scope. A relation is often given a name. The scope of the tuples is often called the relation scheme. A relational database is a set of relations. A scheme of a relational database is the set of pairs of relation names and relation schemes.
A relation with scope can be seen as a Boolean factor on , where the true elements are represented as tuples.
Often a relation is written as a table.
The following is a tabular depiction of a relation, :
The heading gives the scheme, namely , and every other row is a tuple. The first tuple, call it is defined by , , , .
The order of the columns and the order of the rows is not significant.
If a relation with scheme , and is a condition on the variables in , the selection of in , written , is the set of tuples in for which holds. The selection has the same scheme as .
If is a relation with scheme , and , the projection of onto , written , is the set of tuples of where the scope is restricted to .
Suppose is the relation given in Example A.2.
The relation selects those tuples in where the grade is over 79. This is the relation:
The relation specifies what years students were enrolled:
Notice how the first and the fourth tuple of become the same tuple in the projection; they represent the same function on .
If two relations on the same scheme, the union, intersection and set difference of these are defined as the corresponding operations on the set of tuples.
If and are two relations, the natural join of and , written is a relation where
the scheme of the join is the union of the scheme of and the scheme of ,
a tuple is in the join, if the tuple restricted to the scope of is in the relation and the tuple restricted to the scope of is in the relation .
Consider the relation :
The join of and , written is the relation:
Note how in the join, the information about was lost, as there was no TA in that course.