0.6 Discrete structures relation

Relation

Introduction to relation

The relation we are going to study here is an abstraction of relations we see in our everyday life such as those between parent and child, between car and owner, among name, social security number, address and telephone number etc. We are going to focus our attention on one key property which all the everyday relations have in common, define everything that has that property as a relation, and study properties of those relations. One of the places where relation in that sense is used is data base management systems. Along with hierarchical and network models of data, the relational model is widely used to represent data in a database. In this model the data in a database are represented as a collection of relations. Informally, each relation is like a table or a simple file. For example, consider the following table.

Definitions

Binary relation

Here we are going to define relation formally, first binary relation, then general n-ary relation. A relation in everyday life shows an association of objects of a set with objects of other sets (or the same set) such as John owns a red Mustang, Jim has a green Miata etc. The essence of relation is these associations. A collection of these individual associations is a relation, such as the ownership relation between peoples and automobiles. To represent these individual associations, a set of "related" objects, such as John and a red Mustang, can be used. However, simple sets such as {John, a red Mustang} are not sufficient here. The order of the objects must also be taken into account, because John owns a red Mustang but the red Mustang does not own John, and simple sets do not deal with orders. Thus sets with an order on its members are needed to describe a relation. Here the concept of ordered pair and, more generally, that of ordered n-tuple are going to be defined first. A relation is then defined as a set of ordered pairs or ordered n-tuples.

Definition (ordered pair):

An ordered pair is a set of a pair of objects with an order associated with them. If objects are represented by x and y, then we write an ordered pair as<x, y>or<y, x>. In general<x, y>is different from<y, x>.