Relations

Relations

Relations

Ipoh

Kota Bharu

Alor Star

Seremban

Pasir Mas

Perak

Kelantan

Kedah

Neg. Sembilan

cities states

isin

Relations

• Defining isin relation

isin == {(Ipoh,Perak), (Kota Bharu, Kelantan), (Alor Star, Kedah),

(Seremban, Neg Sembilan), (Pasir Mas, Kelantan)}

• From the above we that (Ipoh,Perak) isin• but (Ipoh, Kelantan) isin• we can deduce that, the type of isin is ℙ(cities states)

Notation for Relation

Examples

Examples

Declaring Relations

• Examples

isin : cities states• Another example

let [Author] and [Title] are given sets, then

we will have

wrote : ℙ(Author Title)

wrote : Author Title

• Representing pairs that make up a relation (x,y), we can use maplet notation x ↦y

• Using maplet notation for isin relation

{Ipoh ↦ Perak, Kota Bharu ↦Kelantan, …}

Ipoh ↦ Perak isin

{Ipoh ↦ Perak, Kota Bharu ↦Kelantan} isin

Domains and Ranges

• Domain of a relation is the set of first elements of the pairs (source) in the relation

suppose R : X Y then

dom R = { x : X | y : Y • x ↦y R}

• Range of a relation is the set of second elements of the pairs (target) in the relation

ran R = {y : Y | x : X • x ↦y R}

Example

Exercise

Assume that the definition of two relations involving the sets People, and Instruments as follows:

plays == {Ash ↦piano, William ↦ guitar, David ↦ violin,

Huw ↦ trumpet, Alice ↦ flute, Alice ↦piano, Kate ↦piano}

what are the domain and range of plays?

Restriction

• Domain restriction

getting attention to those pairs in relation whose first members are members of some other set of interest

• Example: to confine the relation wrote to those pair whose first members are in the set female --- female ⊳ wrote

• An abbreviation of either of the following

{ a: female; t : Title | a wrote t • a ↦ t }(female Title) wrote

Restriction

• Range restriction

getting attention to those pairs in relation whose second members are members of some other set of interest

• Example: restrict on second members as set of novel which is a set of titles --- wrote ▷ novel

• An abbreviation of either of the following

{ a: Author; t : Novel | a wrote t • a ↦ t }(Author Novel) wrote

Subtraction

• Domain subtraction

Getting attention to those pair in a relation whose first members are not members of some other set of interest

• Example: denote set of ordered pairs in wrote whose first members are not in female

female wrote

Subtraction

• Range subtraction

Getting attention to those pair in a relation whose second members are not members of some other set of interest

• Example: denote set of ordered pairs in wrote whose second members are not in novel

wrote novel

Inverse

Inverse

Relational Image

• Given any set of domain-type elements of a relation, we can get the subset of range elements to which they are related

Relational Composition

• Given two relations such that the range type of the first is the same as the domain type of the second

• Able to put ‘end-to-end’ to form a single relation containing all pairs joined by some common elements

• Example:

wrote : Author Title

issued-by : Title Publisher

composition published-by : wrote ; issued-by