COMPONENT INTERSECTION DATA BASE FILTER

A Component Intersection Database Filter is a mechanism to process conjunction-of-constraints queries which does not require indexes, allows arbitrary query complexity without exponential explosion in query processing time, and is inexpensive to implement. For a wide variety of queries, this Component Intersection Database Filter Engine drastically reduces the amount of processing required to determine the final answers. For certain queries it can eliminate all incorrect answers, thus requiring no further processing. It is of linear complexity. High speed filtering can be done with simple hardware or software. Further, the processing can be combined with conventional selection filtering and both performed in a pipelined fashion as data streams off disc. The processing is accomplished by building a filter by intersecting predicate instantiations of corresponding unknown components and then filtering potential solution facts by eliminating those with terms corresponding to unknowns not within the intersection.