Skip to main content

module Relation

rascal-0.34.0

Library functions for relations.

Usage

import Relation;

The following library functions are defined for relations:

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.

A relation excluding tuples that contain certain element 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[&T2] 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[&T2] 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}
)