module Relation

rascal-0.40.16

Library functions for relations.

Usage

import Relation;

Description

The following library functions are defined for relations:

• carrier
• carrierR
• carrierX
• complement
• domain
• domainR
• domainX
• groupDomainByRange
• groupRangeByDomain
• ident
• index
• invert
• range
• rangeR
• rangeX

function carrier

Return the set of all elements in any tuple in a relation.

set[&T]  carrier (rel[&T,&T] R)

set[&T]  carrier (rel[&T, &T, &T] R)

set[&T]  carrier (rel[&T,&T,&T,&T] R)

set[&T]  carrier (rel[&T,&T,&T,&T,&T] R)

Examples

rascal>import Relation;
ok
rascal>carrier({<1,10>, <2,20>});
set[int]: {10,1,20,2}
rascal>carrier({<1,10,100,1000>, <2,20,200,2000>});
set[int]: {10,200,20,2,100,1000,1,2000}

function carrierR

A relation restricted to certain element values in tuples.

rel[&T,&T] carrierR (rel[&T,&T] R, set[&T] S)

rel[&T,&T,&T] carrierR (rel[&T,&T,&T] R, set[&T] S)

rel[&T,&T,&T,&T] carrierR (rel[&T,&T,&T,&T] R, set[&T] S)

rel[&T,&T,&T,&T,&T] carrierR (rel[&T,&T,&T,&T,&T] R, set[&T] S)

Returns relation R restricted to tuples with elements in set S.

Examples

rascal>import Relation;
ok
rascal>carrierR({<1,10>, <2,20>, <3,30>}, {10, 1, 20});
rel[int,int]: {<1,10>}

function carrierX

A relation excluded tuples containing certain values.

rel[&T,&T] carrierX (rel[&T,&T] R, set[&T] S)

rel[&T,&T,&T] carrierX (rel[&T,&T,&T] R, set[&T] S)

rel[&T,&T,&T,&T] carrierX (rel[&T,&T,&T,&T] R, set[&T] S)

rel[&T,&T,&T,&T,&T] carrierX (rel[&T,&T,&T,&T,&T] R, set[&T] S)

Returns relation R excluding tuples with some element in S.

Examples

rascal>import Relation;
ok
rascal>carrierX({<1,10>, <2,20>, <3,30>}, {10, 1, 20});
rel[int,int]: {<3,30>}

Examples

rascal>import Relation;
ok
rascal>carrierX({<1,10>, <2,20>, <3,30>}, {10, 1, 20});
rel[int,int]: {<3,30>}

function complement

Complement of a relation.

rel[&T0, &T1] complement(rel[&T0, &T1] R)

rel[&T0, &T1, &T2] complement(rel[&T0, &T1, &T2] R)

rel[&T0, &T1, &T2, &T3] complement(rel[&T0, &T1, &T2, &T3] R)

rel[&T0, &T1, &T2, &T3, &T4] complement(rel[&T0, &T1, &T2, &T3, &T4] R)

Given a relation R a new relation U can be constructed that contains all possible tuples with element values that occur at corresponding tuple positions in R. The function complement returns the complement of R relative to U, in other words: U - R.

Examples

rascal>import Relation;
ok

Declare R and compute corresponding U:

rascal>R = {<1,10>, <2, 20>, <3, 30>};
rel[int,int]: {
  <1,10>,
  <3,30>,
  <2,20>
}
rascal>U = domain(R) * range(R);
rel[int,int]: {
  <1,10>,
  <1,20>,
  <1,30>,
  <3,10>,
  <3,20>,
  <3,30>,
  <2,10>,
  <2,20>,
  <2,30>
}

Here is the complement of R computed in two ways:

rascal>U - R;
rel[int,int]: {
  <1,20>,
  <1,30>,
  <3,10>,
  <3,20>,
  <2,10>,
  <2,30>
}
rascal>complement({<1,10>, <2, 20>, <3, 30>});
rel[int,int]: {
  <1,20>,
  <1,30>,
  <3,10>,
  <3,20>,
  <2,10>,
  <2,30>
}

function domain

Domain of a relation: a set consisting of the first element of each tuple.

set[&T0] domain (rel[&T0,&T1] R)

set[&T0] domain (rel[&T0,&T1,&T2] R)

set[&T0] domain (rel[&T0,&T1,&T2,&T3] R)

set[&T0] domain (rel[&T0,&T1,&T2,&T3,&T4] R)

Examples

rascal>import Relation;
ok
rascal>domain({<1,10>, <2,20>});
set[int]: {1,2}
rascal>domain({<"mon", 1>, <"tue", 2>});
set[str]: {"tue","mon"}

function domainR

Relation restricted to certain domain elements.

rel[&T0,&T1] domainR (rel[&T0,&T1] R, set[&T0] S)

rel[&T, &U] domainR(rel[&T, &U] R, bool(&T) accept)

rel[&T0,&T1,&T2] domainR (rel[&T0,&T1,&T2] R, set[&T0] S)

rel[&T0,&T1,&T2,&T3] domainR (rel[&T0,&T1,&T2,&T3] R, set[&T0] S)

rel[&T0,&T1,&T2,&T3,&T4] domainR (rel[&T0,&T1,&T2,&T3,&T4] R, set[&T0] S)

Restriction of a relation R to tuples with first element in S.

Examples

rascal>import Relation;
ok
rascal>domainR({<1,10>, <2,20>, <3,30>}, {3, 1});
rel[int,int]: {
  <1,10>,
  <3,30>
}

function domainX

Relation excluding certain domain values.

rel[&T0,&T1] domainX (rel[&T0,&T1] R, set[&T0] S)

rel[&T0,&T1,&T2] domainX (rel[&T0,&T1,&T2] R, set[&T0] S)

rel[&T0,&T1,&T2,&T3] domainX (rel[&T0,&T1,&T2,&T3] R, set[&T0] S)

rel[&T0,&T1,&T2,&T3,&T4] domainX (rel[&T0,&T1,&T2,&T3,&T4] R, set[&T0] S)

Relation R excluded tuples with first element in S.

Examples

rascal>import Relation;
ok
rascal>domainX({<1,10>, <2,20>, <3,30>}, {3, 1});
rel[int,int]: {<2,20>}

function groupDomainByRange

Make sets of elements in the domain that relate to the same element in the range.

set[set[&U]] groupDomainByRange(rel[&U dom, &T ran] input)

Examples

rascal>import Relation;
ok
rascal>legs = {<"bird", 2>, <"dog", 4>, <"human", 2>, <"spider", 8>, <"millepede", 1000>, <"crab", 8>, <"cat", 4>};
rel[str,int]: {
  <"spider",8>,
  <"human",2>,
  <"crab",8>,
  <"cat",4>,
  <"bird",2>,
  <"dog",4>,
  <"millepede",1000>
}
rascal>groupDomainByRange(legs);
set[set[str]]: {
  {"human","bird"},
  {"cat","dog"},
  {"spider","crab"},
  {"millepede"}
}

function groupRangeByDomain

Make sets of elements in the range that relate to the same element in the domain.

set[set[&T]] groupRangeByDomain(rel[&U dom, &T ran] input)

rascal>import Relation;
ok
rascal>skins = {<"bird", "feather">, <"dog", "fur">, <"tortoise", "shell">, <"human", "skin">, <"fish", "scale">, <"lizard", "scale">, <"crab", "shell">, <"cat", "fur">};
rel[str,str]: {
  <"tortoise","shell">,
  <"human","skin">,
  <"crab","shell">,
  <"fish","scale">,
  <"bird","feather">,
  <"dog","fur">,
  <"lizard","scale">,
  <"cat","fur">
}
rascal>groupRangeByDomain(skins);
set[set[str]]: {
  {"scale"},
  {"shell"},
  {"skin"},
  {"feather"},
  {"fur"}
}

function ident

The identity relation.

rel[&T, &T] ident (set[&T] S)

The identity relation for set S.

Examples

rascal>import Relation;
ok
rascal>ident({"mon", "tue", "wed"});
rel[str,str]: {
  <"tue","tue">,
  <"mon","mon">,
  <"wed","wed">
}

function invert

Invert the tuples in a relation.

rel[&T1, &T0] invert (rel[&T0, &T1] R)

rel[&T2, &T1, &T0] invert (rel[&T0, &T1, &T2] R)

rel[&T3, &T2, &T1, &T0] invert (rel[&T0, &T1, &T2, &T3] R)

rel[&T4, &T3, &T2, &T1, &T0] invert (rel[&T0, &T1, &T2, &T3, &T4] R)

Examples

rascal>import Relation;
ok
rascal>invert({<1,10>, <2,20>});
rel[int,int]: {
  <10,1>,
  <20,2>
}

function range

The range (i.e., all but the first element of each tuple) of a relation.

set[&T1] range (rel[&T0,&T1] R)

rel[&T1,&T2] range (rel[&T0,&T1, &T2] R)

rel[&T1,&T2,&T3] range (rel[&T0,&T1,&T2,&T3] R)

rel[&T1,&T2,&T3,&T4] range (rel[&T0,&T1,&T2,&T3,&T4] R)

Examples

rascal>import Relation;
ok
rascal>range({<1,10>, <2,20>});
set[int]: {10,20}
rascal>range({<"mon", 1>, <"tue", 2>});
set[int]: {1,2}

function rangeR

Relation restricted to certain range values.

rel[&T0,&T1] rangeR (rel[&T0,&T1] R, set[&T1] S)

Restriction of binary relation R to tuples with second element in set S.

Examples

rascal>import Relation;
ok
rascal>rangeR({<1,10>, <2,20>, <3,30>}, {30, 10});
rel[int,int]: {
  <1,10>,
  <3,30>
}

function rangeX

Relation excluding certain range values.

rel[&T0,&T1] rangeX (rel[&T0,&T1] R, set[&T1] S)

Restriction of binary relation R to tuples with second element not in set S.

Examples

rascal>import Relation;
ok
rascal>rangeX({<1,10>, <2,20>, <3,30>}, {30, 10});
rel[int,int]: {<2,20>}

function index

Indexes a binary relation as a map.

map[&K, set[&V]] index(rel[&K, &V] R)

Converts a binary relation to a map of the domain to a set of the range.

Examples

rascal>import Relation;
ok
rascal>index({<1,10>, <2,20>, <3,30>, <30,10>});
map[int, set[int]]: (
  1:{10},
  3:{30},
  2:{20},
  30:{10}
)