3 Sep 2004 12:34:36 -0400

Related articles |
---|

Implementing set theory operations similar to SQL's select and update barry_j_kelly@hotmail.com (2004-08-23) |

Re: Implementing set theory operations similar to SQL's select and upd gneuner2@comcast.net (George Neuner) (2004-08-25) |

Re: Implementing set theory operations similar to SQL's select and upd dmclean@stsci.edu (Donald F. McLean) (2004-08-25) |

Re: Implementing set theory operations similar to SQL's select and upd kwheinri@bsr2.uwaterloo.ca (Kenn Heinrich) (2004-09-03) |

From: | Kenn Heinrich <kwheinri@bsr2.uwaterloo.ca> |

Newsgroups: | comp.compilers |

Date: | 3 Sep 2004 12:34:36 -0400 |

Organization: | University of Waterloo |

References: | 04-08-117 |

Keywords: | analysis |

Posted-Date: | 03 Sep 2004 12:34:36 EDT |

barry_j_kelly@hotmail.com (Barry Kelly) writes:

*>*

*> Does anybody know of concrete papers, books, articles dealing with*

*> concrete implementation details and algorithms that I should be*

*> tracking down rather than the (thus far unsuccessful) general searches*

*> for "set theory"?*

*>*

Barry,

For manipulating sets in terms of their characteristic functions, you

might want to take a look at BDD's (Binary decision diagrams). They

can let you do a lot of operations like determining inclusion,

symmetric differences, etc, very efficiently. Unfortunately, there's

no one single data structure or algorithm that can do everything you

might want -- you just can't get away from the exponential blowup in

the general case. SAT solvers can also be very useful to determine

answers to these problems when you think of sets through their

characteristic functions. Popular BDD packages are Buddy and (in ML)

Muddy, CUDD, while some popular SAT packages that come to mind are

grasp and zchaff. There used to be an excellent introduction to BDD's

posted somewhere on the web written by Henrik Reif Andersen.

Encoding your types of sets ( Cartesian products ) using boolean

functions can work out nicely, since the "any" set has a

characteristic function of True (or 1), so it does not contribute to

the complexity of the required boolean formula. Check out how BDD's

are used to perform relational product operations (in model checking,

not databases) in some of the earlier papers by Ken McMillan.

Hope this helps a little,

- Kenn

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.