Given \(k\) sets of objects \(X_1\), ..., \(X_k\), a
\(k\)-ary relation \(R\) on \(D(R) = (X_1, \ldots, X_k)\) is a
(possibly fuzzy) subset \(G(R)\) of the Cartesian product \(X_1
\times \cdots \times X_k\). We refer to \(D(R)\)
and \(G(R)\) as the domain and the graph of the
relation, respectively (alternative notions are that of ground
and figure, respectively). We also refer to \(s = (s_1,
\ldots, s_k)\), where each \(s_i\) gives the cardinality of
\(X_i\), as the size of the relation.
Strictly speaking, the relation is the pair \((D(R), G(R))\);
often, relations are identified with their graph. If \(G(R)\) is a
crisp subset of \(D(R)\), \(R\) is a crisp relation. In
this case, we say that a \(k\)-tuple \(t\) is contained in
the relation \(R\) iff it is an element of \(G(R)\).
The characteristic function \(f_R\) of a relation \(R\) is
the membership function of \(G(R)\), giving for each \(k\)-tuple
\(t\) in \(D(R)\) the membership (amount of belongingness) of
\(t\) to \(G(R)\). In the crisp case, \(f_R\) is also referred
to as the indicator function of the relation, and is a binary (0/1)
function such that \(f_R(t)\) is one iff \(t\) is in \(G(R)\).
Relations with arity 2, 3, and 4 are typically referred to as
binary, ternary, and quaternary relations,
respectively. A homorelation on \(X\) is a relation with
homogeneous domain, i.e. \((X, X, \dots, X)\).
An endorelation on \(X\) (or binary relation
over \(X\)) is a binary homorelation.
See predicates for the most important
types of endorelations.
Relations with the same domain can naturally be ordered according to
their graphs. I.e., \(R \le S\) iff \(G(R)\) is a subset of
\(G(S)\), or equivalently, iff \(f_R(t) \le f_S(t)\) for every
\(k\)-tuple \(t\) (in the crisp case, iff every tuple contained in
\(R\) is also contained in \(S\)). This induces a lattice
structure, with meet (greatest lower bound) and join (least upper
bound) the intersection and union of the graphs, respectively, also
known as the intersection and union of the relations.
The least element moves metric on this lattice is the
symmetric difference metric, i.e., the Manhattan distance
between the collections of membership values (incidences). In the
crisp case, this gives the cardinality of the symmetric difference of
the graphs (the number of tuples in exactly one of the relation
graphs).
The complement (or negation) \(R^c\) of a relation
\(R\) is the relation with domain \(D(R)\) whose graph is the
complement of \(G(R)\) (in the crisp case, containing exactly the
tuples not contained in \(R\)).
For binary crisp relations \(R\), it is customary to write
\(x R y\) iff \((x, y)\) is contained in \(R\). For binary
crisp relations \(R_1\) and \(R_2\) with domains \((X, Y)\) and
\((Y, Z)\), the composition \(T = R_1 * R_2\) of \(R_1\)
and \(R_2\) is defined by taking \(x S z\) iff there is an \(y\)
such that \(x R_1 y\) and \(y R_2 z\). The transpose (or
inverse) \(R^{t}\) of the relation \(R\) with domain
\((X, Y)\) is the relation with domain \((Y, X)\) such that
\(y R^{t} x\) iff \(x R y\). The
codual (Clark (1990), also known as the ‘dual’ in the
fuzzy preference literature, e.g., Ovchinnikov (1991)) is the
complement of the transpose (equivalently, the transpose of the
complement).
For binary fuzzy relations \(R\), one often writes \(R(x, y)\) for
the membership of the pair \((x, y)\) in the relation. The above
notions need to take the fuzzy logic employed (as described by the
fuzzy t-norm (intersection) \(T\), t-conorm (disjunction) \(S\),
and negation \(N\)) into account. Let \(R\), \(R_1\) and
\(R_2\) be binary relations with appropriate domains. Then the
memberships for \((x, y)\) of the complement, transpose and codual of
\(R\) are \(N(R(x, y))\), \(R(y, x)\) and \(N(R(y, x))\),
respectively. The membership of \((x, y)\) for the composition of
\(R_1\) and \(R_2\) is \(\max_z T(R_1(x, z), R_2(z, y))\).
Package relations implements finite relations as an S3 class
which allows for a variety of representations (even though currently,
typically dense array representations of the incidences are employed).
Other than by the generator,
relations can be obtained by coercion via the generic function
as.relation(), which has methods for at least logical and numeric
vectors, unordered and ordered factors, arrays including matrices, and
data frames. Unordered factors are coerced to equivalence relations;
ordered factors and numeric vectors are coerced to order relations.
Logical vectors give unary relations (predicates). A (feasible)
\(k\)-dimensional array is taken as the incidence of a \(k\)-ary
relation. Finally, a data frame is taken as a relation table. Note
that missing values will be propagated in the coercion.
endorelation() is a wrapper for relation(), trying to
guess a suitable domain from its arguments to create an
endorelation. If a domain is given, all labels are combined and the
result (as a list) recycled as needed.
Basic relation operations are available as group methods: min()
and max() give the meet and join, and range() a
relation ensemble with these two.
Comparison operators implement the natural ordering in the relation
lattice. Where applicable, ! gives the complement (negation),
& and | intersection and union, and *
composition, respectively. Finally, t() gives the transpose
and codual() the codual.
There is a plot() method for certain
crisp endorelations provided that package Rgraphviz is
available.
For crisp endorelations \(R\), sym() and asy() give
the symmetric and asymmetric parts of \(R\), defined as the
intersection of \(R\) with its transpose, or, respectively, with its
codual (the complement of its transpose).
The summary() method applies all predicates available
and returns a logical vector with the corresponding results.