org.zedlib
Interface Relation

All Superinterfaces:

Collection, Set, Set

All Known Subinterfaces:

Bag, Function, Sequence

All Known Implementing Classes:

HashBag, HashFun, HashRel, HashSeq

public interface Relation

extends Set

A relation is a set of relationships between two objects. Each (x,y) is termed a binary relation (or maplet) relating some x of set X to some y of set Y, contained within the relation X ↔ Y.

Note that this is not equivalent to a java.util.Map which enforces a unique set of keys (properly called a function). In other words, a relation allows x of X to appear multiple times so long as each x relates to a different y of Y.

If X and Y are sets, then X ↔ Y is the set of binary relations between X and Y. Each such relation is a subset of X x Y. A 'maplet' from x to y is another way of expressing the ordered pair (x, y).

For example, the following are valid binary relations (maplets, ordered pairs) within a Relation R:

(tom, mary)
(fred, jane)
(tom, jane)

Author:

Brad Long

Method Summary

boolean	add(Maplet m) Adds a maplet to this relation.
boolean	add(Object x, Object y) Adds a pair of objects to this relation as a maplet.
boolean	addAll(Map m) Adds all entries in a java.util.Map to this relation.
Relation	composition(Relation r) Returns the relational composition of this relation and another given relation, thus if (x,y) exists in this relation Q and (y,z) exists in R then (x,z) appears in the composed relation.
Set	domain() Returns a set containing the unique objects in X of the relation X ↔ Y.
Relation	domainAntiRestriction(Set s) Returns a relation being those maplets in this relation whose x in (x,y) do not appear in the given set.
Relation	domainRestriction(Set s) Returns a relation being only those maplets in this relation whose x in (x,y) appear in the given set.
Set	image(Set s) Returns a set containing the range of a domain restriction on this relation, that is, returns a set of all y of Y for which x of X is related in X ↔ Y.
Relation	inverse() Returns the relational inverse of this relation, thus each maplet (x,y) is inverted to (y,x).
boolean	isFunction()
boolean	isInjection()
boolean	isReflexive()
Relation	override(Relation r) Returns a relation being this relation overridden with a given relation.
Set	range() Returns a set containing the unique objects in Y of the relation X ↔ Y.
Relation	rangeAntiRestriction(Set t) Returns a relation containing those maplets in this relation whose y in (x,y) do not appear in the given set.
Relation	rangeRestriction(Set t) Returns a relation containing only those maplets of this relation whose y in (x,y) appear in the given set.
Relation	transitiveClosure() Returns the transitive closure of this relation.

Methods inherited from interface org.zedlib.Set

cartesianProduct, difference, identity, intersection, isSubsetOf, isSupersetOf, union

Methods inherited from interface java.util.Set

add, addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, size, toArray, toArray

Method Detail

domain

public Set domain()

Returns a set containing the unique objects in X of the relation X ↔ Y.

If R is a binary relation between X and Y, then the domain of R is the set of all members of X which are related to at least one member of Y by R.

Returns:

the set of unique objects contained within X

range

public Set range()

Returns a set containing the unique objects in Y of the relation X ↔ Y.

If R is a binary relation between X and Y, then the range of R is the set of all members of Y to which at least one member of X is related by R.

add

public boolean add(Object x,
                   Object y)

Adds a pair of objects to this relation as a maplet.

Parameters:

x - any object

y - any object

Returns:

true if the objects were added to this relation

add

public boolean add(Maplet m)

Adds a maplet to this relation.

Parameters:

m - any maplet

Returns:

true if the given maplet was added to this relation

See Also:

Set.add(Object o)

addAll

public boolean addAll(Map m)

Adds all entries in a java.util.Map to this relation.

Parameters:

m - any java.util.Map

Returns:

true if any objects of the map were added to this relation

See Also:

Set.addAll(Collection c)

domainRestriction

public Relation domainRestriction(Set s)

Returns a relation being only those maplets in this relation whose x in (x,y) appear in the given set.

The domain restriction R.domainRestriction(S) of this relation R to a set S, relates x to y if and only if R relates x to y and x is a member of S.

Example:

if r = { (a,b), (a,c), (b,d) } and s = {b}
then r.domainRestriction(s) = { (b,d) }

Parameters:

s - the set of objects with which to restrict the domain of this relation

Returns:

a relation being this relation restricted to elemnets in the domain contained in s

domainAntiRestriction

public Relation domainAntiRestriction(Set s)

Returns a relation being those maplets in this relation whose x in (x,y) do not appear in the given set.

This operation is the complemented counterpart of the domain restriction operation. An object x is related to an object y by the relation R.domainAntiRestrict(S) if and only if x is related to y by R and x is not a member of S.

Example:

if r = { (a,b), (a,c), (b,d) } and s = {b}
then r.domainAntiRestriction(s) = { (a,b), (a,c) }

Parameters:

s - the set of objects with which to anti-restrict this relation. By definition, these objects will not appear in the domain of the restricted relation.

Returns:

a relation containing all maplets in this relation that are not in s

rangeRestriction

public Relation rangeRestriction(Set t)

Returns a relation containing only those maplets of this relation whose y in (x,y) appear in the given set.

The range restriction R.rangeRestrict(T) of R to a set T relates x to y if and only if R relates x to y and y is a member of T.

Example:

if r = { (a,b), (a,c), (b,d) } and t = {d}
then r.rangeRestriction(t) = { (b,d) }

Parameters:

t - the set of objects with which to restrict the range of this relation

Returns:

a relation consisting of this relation restricted to maplets with y in (x,y) in t

rangeAntiRestriction

public Relation rangeAntiRestriction(Set t)

Returns a relation containing those maplets in this relation whose y in (x,y) do not appear in the given set.

This operation is the complemented counterpart of the domain restriction operation. An object x is related to an object y by the relation R.rangeAntiRestrict(T) if and only if x is related to y by R and y is not a member of T.

Example:

if r = { (a,b), (a,c), (b,d) } and t = {d}
then r.rangeAntiRestriction(t) = { (a,b), (a,c) }

Parameters:

t - the set of objects with which to anti-restrict this relation. By definition, these objects will not appear in the range of the restricted relation.

Returns:

a relation containing maplets in this relation whose y in (x,y) do not appear in t

inverse

public Relation inverse()

Returns the relational inverse of this relation, thus each maplet (x,y) is inverted to (y,x).

An object y is related to an object x by the relational inverse R∼ of R if and only if x is related to y by R.

Example:

if r = { (a,b), (a,c), (b,d) }
then r.inverse() = { (b,a), (c,a), (d,b) }

Returns:

a relation being the inverse of this relation

composition

public Relation composition(Relation r)

Returns the relational composition of this relation and another given relation, thus if (x,y) exists in this relation Q and (y,z) exists in R then (x,z) appears in the composed relation.

The composition Q.compose(R) of two relations Q: X ↔ Y and R: Y ↔ Z relates a member x of X to a member z of Z if and only if there is at least one element y of Y to which x is related by Q and which is itself related to z by R.

Example:

if q = { (a,b), (a,c), (b,d) } and r = { (b,e), (b,f), (d,g) }
then q.composition(r) = { (a,e), (a,f), (b,g) }

Parameters:

r - the relation R with which to perform the composition

Returns:

a relation composed of this relation with r

override

public Relation override(Relation r)

Returns a relation being this relation overridden with a given relation. The relation Q.override(R) relates everything in the domain of R to the same objects as R does, and everything else in the domain of Q to the same objects as Q does.

Example:

if q = { (a,b), (a,c), (b,d) } and r = { (a,d), (c,e) }
then q.override(r) = { (a,d), (b,d), (c,e) }

Parameters:

r - the relation to override this relation

Returns:

a relation being the composition of this relation with r

transitiveClosure

public Relation transitiveClosure()

Returns the transitive closure of this relation.

If R is a relation from a set X to itself, R.transitiveClosure(), or R+, is the strongest or smallest relation containing R which is transitive.

Example:

if r = { (a,b), (a,c), (b,d), (d,e) }
then r.transitiveClosure() = { (a,b), (a,d), (a,e), (a,c), (b,d), (b,e), (d,e) }

If a relation Relation.transitiveClosure(r).intersect(Relation.identity(r)) is not empty, then the transitive closure contains one or more cycles.

Returns:

a relation being the transitive closure of this relation

image

public Set image(Set s)

Returns a set containing the range of a domain restriction on this relation, that is, returns a set of all y of Y for which x of X is related in X ↔ Y. The relational image R.image(S) of a set S through a relation R is the set of all objects y to which R relates some member x of S.

Example:

if r = { (a,b), (a,c), (b,d) } and s = {a}
then r.image(s) = {b,c}

Returns:

the range of a relation formed by restricting the domain of this relation to the given set

isFunction

public boolean isFunction()

Returns:

true if elements in the domain of this relation are unique

isInjection

public boolean isInjection()

Returns:

true if elements in the domain of this relation are unique and none of them map to the same object.

isReflexive

public boolean isReflexive()

Returns:

true if all elements in the domain of this relation are at least related to themselves in the range of this relation.