| relation {relations} | R Documentation |
Relations
Description
Creation and manipulation of relations.
Usage
relation(domain = NULL, incidence = NULL, graph = NULL,
charfun = NULL)
endorelation(domain = NULL, incidence = NULL, graph = NULL,
charfun = NULL)
homorelation(domain = NULL, incidence = NULL, graph = NULL,
charfun = NULL)
as.relation(x, ...)
is.relation(x)
Arguments
domain |
List (or tuple) of (possibly named) sets (or vectors)
used as the domain, recycled as needed to fit the arity of the relation.
If |
incidence |
A numeric array with values in the unit interval, or
a logical array. Note that one-dimensional incidences are also
accepted. The |
graph |
Either a set of equally sized tuples, or a list of (possibly, generic) vectors of same length where each component specifies one relation element, or a data frame where each row specifies one relation element. For the latter, the columns correspond to the domain sets, and the colnames are used as their labels if specified. |
charfun |
A characteristic function of the relation, i.e., a
predicate function taking |
x |
an R object. |
... |
Further arguments passed to |
Details
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.
References
S. A. Clark (1990), A folk meta-theorem in the foundations of utility theory. Mathematical Social Sciences, 19/3, 253–267. doi:10.1016/0165-4896(90)90065-F.
S. Ovchinnikov (1991), Similarity relations, fuzzy partitions, and fuzzy orderings. Fuzzy Sets and Systems, 40/1, 107–126. doi:10.1016/0165-0114(91)90048-U.
See Also
relation_incidence() for obtaining incidences;
relation_domain() for determining domain, arity, and
size;
relation_graph() for determining the graph of a relation;
relation_charfun() for determining the characteristic
function;
predicates for available predicate functions; and
algebra for further operations defined on relations.
Examples
require("sets") # set(), tuple() etc.
## A relation created by specifying the graph:
R <- relation(graph = data.frame(A = c(1, 1:3), B = c(2:4, 4)))
relation_incidence(R)
## extract domain
relation_domain(R)
## extract graph
relation_graph(R)
## both ("a pair of domain and graph" ...)
as.tuple(R)
## (Almost) the same using the set specification
## (the domain labels are missing).
R <- relation(graph = set(tuple(1,2), tuple(1,3),
tuple(2,4), tuple(3,4)))
## equivalent to:
## relation(graph = list(c(1,2), c(1,3), c(2,4), c(3,4)))
relation_incidence(R)
## Explicitly specifying the domain:
R <- relation(domain = list(A = letters[1:3], B = LETTERS[1:4]),
graph = set(tuple("a","B"), tuple("a","C"),
tuple("b","D"), tuple("c","D")))
relation_incidence(R)
## Domains can be composed of arbitrary R objects:
R <- relation(domain = set(c, "test"),
graph = set(tuple(c, c), tuple(c, "test")))
relation_incidence(R)
## Characteristic function ("a divides b"):
R <- relation(domain = list(1 : 10, 1 : 10),
charfun = function(a, b) b %% a == 0)
relation_incidence(R)
## R is a partial order: plot the Hasse diagram provided that
## Rgraphviz is available:
if(require("Rgraphviz")) plot(R)
## conversions and operators
x <- matrix(0, 3, 3)
R1 <- as.relation(row(x) >= col(x))
R2 <- as.relation(row(x) <= col(x))
R3 <- as.relation(row(x) < col(x))
relation_incidence(max(R1, R2))
relation_incidence(min(R1, R2))
R3 < R2
relation_incidence(R1 * R2)
relation_incidence(! R1)
relation_incidence(t(R2))
### endorelation
s <- set(pair("a","b"), pair("c","d"))
relation_incidence(relation(graph = s))
relation_incidence(endorelation(graph = s))