cz.cuni.versatile.api.relops
Interface TransitiveClosure

All Superinterfaces:
RelationalOperator

public interface TransitiveClosure
extends RelationalOperator

TransitiveClosure operator builds a transitive closure of a source RelationalProperty so that the resulting RelationalProperty represents a transitive binary relation. In case the source property is already transitive, the operator should return the source property.

Note: A generic implementation of this interface is practically impossible given the way the Versatile API is designed: RelationalProperty only has contains(x, y) method, so that one would first need to scan the entire domain and build a list of all ordered pairs {x, y} where contains(x, y) = true and then proceed with building the transitive closure. This represents computational complexity O(N2). It would help if we add an additional method to the RelationalProperty, which for a given x would return a set of all y such that contains(x, y) = true. The problem is that having such a method requires all relational properties to become enumerable, which is exactly what we want to avoid: the Versatile API is designed in the way which allows and encourages computational approach to implementing properties (as opposed to pure algebraic data manipulation which can be quite limiting for some applications). Given the above, we assume property-specific implementations of this interface are most likely to be used.

Author:
Jaroslav Gergic
See Also:
RelationalProperty.isTransitive()

Method Summary
 RelationalProperty transitiveClosure(RelationalProperty source)
          Returns a RelationalProperty which corresponds to a transitive closure of the source binary relation.
 

Method Detail

transitiveClosure

public RelationalProperty transitiveClosure(RelationalProperty source)
Returns a RelationalProperty which corresponds to a transitive closure of the source binary relation.

Parameters:
source - a source relational property