# Relations

A relation is a structure that is used to represent the relationships between elements

## Category of relations

- Binary relations
- N-ary relations

## Binary Relations

A binary relation

## Functions and Relations

- Are all the functions relations? Yes
- Are all relations functions? No

## Relation on the Set

- A relation on the set is a relation from
to .

## Properties of Relations

### Reflexive

A relation

### Symmetric

A relation

### Anti-symmetric

A relation

### Transitive

A relation

## Combining Relations

The composite of

E.g.,

▪, ,

▪(a relation from to )

▪(a relation from to )

▪

## Powers of a Relation

Let

Theorem: The relation

-ary Relations

- Let
be sets. - An
-ary relation on these sets is a subset of - Domain:
- Degree:

## Relations and Database

- Currently, the most commonly used databases are relational databases.
- Each database consists of multiple relations.
- Each relation is presented as a table.

## Operations on -ary Relations

### Selection operator :

-ary relation - condition
- Selection operator
: maps to an -ary relations , where all the tuples in satisfy the condition .

i.e.

### Projection operator :

- the input relation is on
tuples , - the output relation is on
tuples , . - Projection operator
: removes the tuples not in the -tuple list i.e.

## Equivalence Relations

- A relation on a set
is called an equivalence relation if it is reflexive, symmetric, and transitive. Let be an equivalence relation on .

### Equivalent class

Equivalent class -> Equivalent relations

### Partition

- All the equivalent classes obtained from
through an equivalent class are either same or disjoint. - These disjoint classes are subsets of
. - The union of these subsets is
. - These subsets are called a partition of
In general, is a partition of if:

for all for all

### Theorem: Let be an equivalence relation on a nonempty set .

The following statements are equivalent: