Component intersection data base filter

Details Component intersection data base filter Component intersection data base filter

1991-05-03

1993-09-28

MacDonald, Allen R.

395 54, 395600, G06F 1500

Patent

active

052492621

ABSTRACT:
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.

REFERENCES:
patent: 3964029 (1976-06-01), Babb
patent: 4593403 (1986-06-01), Kishi et al.
Ceri et al., "What You Always Wanted to Know About Datalog (And Never Dared to Ask)", IEEE Transactions on Knowledge and Data Engineering, vol. 1, No. 1 Mar. 1989, pp. 146-165.
Turbo Prolog 2.0 User's Guide, IBM Version, Borland, 1988, pp. 46-51, 58-60, 62-64, 99-109, 146-147, 167, 214-215, 219, 248-252, 266, 271, 274-275, 320-326, 358-361.
Yokota et al., "Term Indexing for Retrieval by Unification," Proceedings Fifth International Conference on Data Engineering, 1989, pp. 313-320.
E. Babb, "CAFS File-Correlation Unit," ICL Technical Journal, Nov. 1985, pp. 489-503.
E. Babb, "Implementing a Relational Database by Means of Specialized Hardware," ACM Transactions on Database Systems, vol. 4, No. 1, Mar. 1979, pp. 1-29.
Donald E. Knuth, "The Art of Computer Programming, vol. 3, Sorting and Searching," Addison-Wesley Publishing Company, Inc., 1973, pp. 558-563.
P. Bruce Bera, Soon Myoung Chung, and Nabil I. Hachem, "Computer Architecture for a Surrogate File to a Very large Data/Knowledge Base," Computer, vol. 20, No. 3, mar. 1987, pp. 25-32.
David H. D. Warren, "An Abstract Prolog Instruction Set," SRI International, Oct. 1983.
John Gabriel, Tim Lindholm, E. L. Lusk, R. A. Overbeek, "A Tutorial on the Warren Abstract Machine for Computational Logic," Argonne National Laboratory, Jun. 1985.

Affiliated with

Also associated with

Rating

Component intersection data base filter does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Component intersection data base filter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Component intersection data base filter will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2196698