Re: Representing unions of Cartesian products

(Mark-Jan Nederhof) writes:
>I am looking for an efficient way to store and manipulate unions of
>Cartesian products.
...
>At this moment I am using a representation where a union of Cartesian
>products is transformed into another such that the Cartesian products do
>no longer overlap (i.e. they have no tuples in common). If possible I
>merge two Cartesian products into one. These transformations are however
>rather expensive. Does anyone have a better suggestion? references to
>papers?


I may be off the mark here but one way to do this is to represent your
cartesian products as predicates. Then the union of two cartesian products
C1 and C2 is the logical or of their respective predicates, the
intersection is the logical and of their respective predicates, etc.


This scheme allows for fast membership testing of a tuple in a cartesian
product, and allows maintains enumerability. If C1 and C2 are enumerable
then so is C1 union C2, C1 intersect C2, etc.


Efficiency is a bit of an issue here, but given that you don't want to
represent cartesian products explicitly, you don't appear to have much
choice but to sacrifice efficiency.


graham
--
Graham Matthews
Pure Math, Uni.Sydney, Oz
graham@maths.su.oz.au
--

Return to the comp.compilers page.
Search the comp.compilers archives again.