Relation (mathematics)

In mathematics, an n-ary relation on n sets, is any subset of Cartesian product of the n sets (i.e., a collection of n-tuples), with the most common one being a binary relation, a collection of order pairs from two sets containing an object from each set. The relation is homogeneous when it is formed with one set.

A (binary)relation R among sets A and B is a subset of the Cartesian product of the set of b $R\subseteq A\times B$. The above picture shows an example of two sets A={a,b,c} and B={x,y,z}, their Cartesian product is a complete relation among A and B, and any other subset of AxB is a relation too. The Venn diagram shows a function. A function is a relation that "maps" elements of one set to another set. That means that each element in the first set can appear at most in one pair in the first entry. The example shows two elements of the first set can be mapped to the same element of the second set. Both elements b and c of the first set map to element z of the second set.

For example, any curve in the Cartesian plane is a subset of the Cartesian product of real numbers, RxR. The homogeneous binary relations are studied for properties like reflexiveness, symmetry, and transitivity, which determine different kinds of orderings on the set. Heterogeneous n-ary relations are used in the semantics of predicate calculus, and in relational databases.

In relational databases jargon, the relations are called tables. There is a relational algebra consisting in the operations on sets, because relations are sets, extended with operators like projection, which forms a new relation selecting a subset of the columns (tuple entries) in a table, the selection operator, which selects just the rows (tuples),according to some condition, and join which works like a composition operator.

The use of the term "relation" is often used as shorthand to refer to binary relations, where the set of all the starting points is called the domain and the set of the ending points is the codomain.

Different types of relationship

An example for such a relation might be a function. Functions associate each key with one value. The set of all functions is a subset of the set of all relations - a function is a relation where the first value of every tuple is unique through the set.

Other well-known relations are the equivalence relation and the order relation. That way, sets of things can be ordered: Take the first element of a set, it is either equal to the element looked for, or there is an order relation that can be used to classify it. That way, the whole set can be classified (i.e., compared to some arbitrarily chosen element).

Relations can be transitive.One example of a transitive relation is the "smaller-than" relation. If X "is smaller than" Y,and Y is "smaller than" Z,then X "is smaller than" Z. In general, a transitive relation is a relation such that if relations (a,b) and (b,c) both belong to R, then (a,c) must also belongs to R.

Relations can be symmetric. One example of a symmetric relation is the relation "is equal to". If X "is equal to" Y, then Y "is equal to" X. In general, a symmetric relation is a relation such that if (a,b) belongs to R, then (b,a) must belong to R as well.

Relations can be asymmetric, such as the relation " is smaller than". In general, a relation is asymmetric if whether (a,b) belongs to R, (b,a) does not belong to R.

Relations can be reflexive. One example of a reflexive relation is the relation "is equal to" (e.g., for all X, X "is equal to" X). In general, a reflexive relation is a relation such that for all a in A, (a,a) belongs to R.

By definition, every subset of AxB is a relation from A to B.

In category theory, relations play an important role in the Cartesian closed categories, which transform morphisms from tuples to morphisms of single elements. That corresponds to Currying in the Lambda calculus.

Databases and Relations

In relational database theory, a database is a set of relations. To model a real world, the relations should be in a canonical form called normalized form. That transformation ensure no loss of information, nor the insertion of spurious tuples with no corresponding meaning in the world represented in the database. The normalization process takes into account properties of relations like functional dependencies among their entries, keys and foreign keys, transitive and join dependencies.