relation: Relations
In relations: Data Structures and Algorithms for Relations

relation

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 `domain` is not a list or tuple, it is converted to a list.
`incidence`	A numeric array with values in the unit interval, or a logical array. Note that one-dimensional incidences are also accepted. The `names`/`dimnames` attribute of `incidence` is used as domain if this is not explicitly given using the `domain` argument.
`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 k arguments, with k equal to the arity of the relation.
`x`	an R object.
`...`	Further arguments passed to `as.relation()` methods (currently not used for those defined in the relations package).

Details

Given k sets of objects X_1, ..., X_k, a k-ary relation R on D(R) = (X_1, …, X_k) is a (possibly fuzzy) subset G(R) of the Cartesian product X_1 x ... x 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, …, 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, …, 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 ≤ S iff G(R) is a subset of G(S), or equivalently, iff f_R(t) ≤ 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.

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))

relations documentation built on March 7, 2023, 8:01 p.m.