Re: Implementing set theory operations similar to SQL's select and update

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

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