subrelation

A subrelation is a relation that is contained within another relation. If R is a relation on a set (or between sets) A and B, then a relation S is called a subrelation of R when S is a subset of R, written S ⊆ R. In practical terms, a subrelation consists of some of the pairs that R relates, possibly restricting to a subset of the domain and codomain.

Formal definition and scope: For R ⊆ A×B, a relation S ⊆ A×B is a subrelation of R if every pair in S is also in R. If S ≠ R, it is a proper subrelation. Subrelations naturally arise when restricting attention to a portion of the elements involved in R, for example by limiting the domain, the codomain, or both.

Construction and examples: A common way to form a subrelation is to restrict R to a subset C of A and D of B, taking S = R ∩ (C×D). For a simple illustration, let R = {(a,a), (a,b), (b,c)} on A = {a,b,c}. Then S = {(a,b)} and T = {(a,b), (b,c)} are subrelations of R. Properties of R, such as reflexivity, symmetry, and transitivity, are not automatically preserved in a subrelation; a subrelation may lose these properties if some related pairs are omitted.

Relation to graphs: If R is viewed as the edge set of a directed graph on A, a subrelation corresponds to a subgraph formed by a subset of edges (and possibly a restricted vertex set).

Applications: Subrelations are used in relational algebra, database querying, model checking, and graph theory to focus analysis on specific connections or to construct smaller models from larger relations.

See also: relation, subset, adjacency relation.