Abstract
A relation can be represented by a bit matrix such that relational intersections,
union, natural join, product and equiselection operations can be implemented by
parallel bitwise AND and OR of bit matrices. Depending on the dimensions of the
bit matrices, this representation is more or less approximate in so far as spurious
tuples may be recovered from a bit matrix along with genuine tuples. The process
of outputting a result relation is serial and has desirable properties that output
tuples can be sorted at no extra cost, and elimination of duplicates from projections
actually speeds up the process instead of requiring extra work. Results of small-scale
simulation are reported.
