US5249262A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Component intersection data base filter
Assignee: Intelligent Query Engines Inc
•
Filing: 1991-05-03
•
Granted: 1993-09-28
•
Expires: 2011-05-03
Abstract
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.
Inventors
- 👤 Gerhard M. Baule
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 16:51
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/30; G06F8/31; G06F8/313; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
130 words
A factbase filter engine comprising: means for storing a factbase organized as a plurality of predications, each containing one or more facts each with one or more terms; a control unit responsive to query parameters connected to said means for storing; a plurality of component term intersection filters, each containing at least a random access memory connected to said means for storing and said control unit wherein addressable locations of said memory correspond to terms of said facts, means for evaluating contents of an addressable location of said memory connected to said memory and said control unit, and means for writing into said memory connected to said control unit, said means for evaluating and said memory; and a buffer store connected to said means for storing and said control unit.
Claim 2
Dependent Claim
130 words
A factbase filter engine comprising: means for storing a factbase organized as a plurality of predications, each containing one or more facts each with one or more terms; a control unit responsive to query parameters connected to said means for storing; a plurality of component term intersection filters, each containing at least a random access memory connected to said means for storing and said control unit wherein addressable locations of said memory correspond to terms of said facts, means for evaluating contents of an addressable location of said memory connected to said memory and said control unit, and means for writing into said memory connected to said control unit, said means for evaluating and said memory; and a buffer store connected to said means for storing and said control unit.
Claim 3
Dependent Claim
28 words
A factbase filter engine according to claim 1, wherein said means for writing is responsive to said means for evaluating of all of said component term intersection filters.
Claim 4
Dependent Claim
33 words
A factbase filter engine according to claim 2, further comprising a selection filter connected to said means for storing, said control unit and said means for writing of each component term intersection filter.
Claim 5
Dependent Claim
23 words
A factbase filter engine according to claim 3, wherein said means for evaluating comprises means for comparing said contents to a threshold level.
Claim 6
Dependent Claim
23 words
A factbase filter engine according to claim 4, wherein said means for writing comprises means for writing an incremented threshold into said memory.
Claim 7
Dependent Claim
30 words
A factbase filter engine according to claim 3, further comprising a term latch associated with each component term intersection filter connected to said means for storing and said control unit.
Claim 8
Dependent Claim
100 words
A factbase filter engine comprising: means for storing a factbase organized as a plurality of predications, each containing one or more facts each with one or more terms; control means responsive to a conjunction of constraints for delivering facts from said means for storing; a component intersection filter means connected to said means for storing and said control means for eliminating from further consideration facts which contain terms which are not within a component intersection set defined by an intersection of instantiations of corresponding terms of said predications wherein said corresponding terms are defined by a predetermined conjunction of constraints.
Claim 9
Dependent Claim
100 words
A factbase filter engine comprising: means for storing a factbase organized as a plurality of predications, each containing one or more facts each with one or more terms; control means responsive to a conjunction of constraints for delivering facts from said means for storing; a component intersection filter means connected to said means for storing and said control means for eliminating from further consideration facts which contain terms which are not within a component intersection set defined by an intersection of instantiations of corresponding terms of said predications wherein said corresponding terms are defined by a predetermined conjunction of constraints.
Claim 10
Dependent Claim
33 words
A filter engine according to claim 7, wherein said component intersection filter means further comprises a plurality of term filters, each corresponding to an unknown contained in two or more of said constraints.
Claim 11
Dependent Claim
94 words
A filter engine according to claim 8, wherein each term filter comprises a memory with index storage locations corresponding to a term of said facts delivered from said means for storing; means for writing into said index storage locations an indication when a term is within said component intersection set, wherein said indication is an incremented index and said component intersection set is further defined by a term level index; means for indicating facts which contain only terms which are members of said intersection connected to said index storage location and said control means.
Claim 12
Dependent Claim
103 words
A filter engine according to claim 8, wherein each term filter comprises a memory with index storage locations corresponding to a term of said facts delivered from said means for storing; means for writing into said index storage location when a term is a member of a fact which contains only terms which are within associated component intersection sets, wherein said indication is an incremented index and said intersection sets are further defined by a term index level; and means for indicating facts which contain only terms which are members of said intersection connected to said index storage location and said control means.
Claim 13
Dependent Claim
17 words
A filter engine according to claim 10, wherein said means for indicating is a secondary storage unit.
Claim 14
Dependent Claim
17 words
A filter engine according to claim 9, wherein said means for indicating is a secondary storage unit.
Claim 15
Dependent Claim
54 words
A factbase filter engine comprising: a control unit connected to a factbase storage unit; a plurality of component intersection filters each corresponding to a constraint conjunction unknown, responsive to said control unit and connected to said factbase storage unit; and a secondary storage unit responsive to said component intersection filters and said control unit.
Claim 16
Dependent Claim
54 words
A factbase filter engine comprising: a control unit connected to a factbase storage unit; a plurality of component intersection filters each corresponding to a constraint conjunction unknown, responsive to said control unit and connected to said factbase storage unit; and a secondary storage unit responsive to said component intersection filters and said control unit.
Claim 17
Dependent Claim
24 words
A filter engine according to claim 13, wherein said factbase storage unit and said secondary storage unit are portions of a single storage device.
Claim 18
Dependent Claim
24 words
A filter engine according to claim 13, wherein each component intersection filter further comprises a random access memory addressed by term of said factbase.
Claim 19
Dependent Claim
24 words
A filter engine according to claim 13, further comprising a selection filter responsive to said control unit and connected to said factbase storage unit.
Claim 20
Dependent Claim
27 words
A filter engine according to claim 16, wherein each of said component intersection filters and said selection filter include an indication output connected to said control unit.
Claim 21
Dependent Claim
23 words
A filter engine according to claim 13, wherein each of said component intersection filters includes an indication output connected to said control unit.
Claim 22
Independent Claim
70 words
A method for filtering a factbase in response to a query made up of a conjunction of two or more constraints comprising the steps of: constructing a filter containing component intersection sets by intersecting instantiations of corresponding terms of predicates of said constraints; filtering facts of said predicates by eliminating from consideration all facts which include any term which is not within a corresponding component intersection set of said filter.
Claim 23
Independent Claim
70 words
A method for filtering a factbase in response to a query made up of a conjunction of two or more constraints comprising the steps of: constructing a filter containing component intersection sets by intersecting instantiations of corresponding terms of predicates of said constraints; filtering facts of said predicates by eliminating from consideration all facts which include any term which is not within a corresponding component intersection set of said filter.
Claim 24
Dependent Claim
59 words
A method according to claim 19, wherein said step of constructing further comprises: forming a sequence of unknowns of said constraints; generating a potential satisfaction sequence for each term of said facts corresponding to said unknowns for each predication; intersecting corresponding fact terms of said potential satisfaction sequences wherein said intersection defines a component intersection set for each unknown.
Claim 25
Dependent Claim
37 words
A method according to claim 20, further comprising the step of: reducing said potential satisfaction sequences to component sets wherein each component set contains only unique elements, and wherein said step of intersecting intersects corresponding component sets.
Claim 26
Dependent Claim
31 words
A method according to claim 20, further comprising the steps of: repeating said steps of constructing and filtering using only facts of said predicates not eliminated during a previous filtering step.
Claim 27
Dependent Claim
19 words
A method according to claim 22, wherein said step of repeating is continued until no additional facts are eliminated.
Claim 28
Dependent Claim
15 words
A method according to claim 19, further comprising the step of selection filtering said factbase.
Claim 29
Dependent Claim
58 words
A factbase filter engine comprising: means for storing a factbase organized as a plurality of predications, each containing one or more facts each with one or more terms; control means responsive to a conjunction of constraints for delivering facts from said means for storing; a component intersection filter connected to said means for storing and said control means.
Claim 30
Dependent Claim
58 words
A factbase filter engine comprising: means for storing a factbase organized as a plurality of predications, each containing one or more facts each with one or more terms; control means responsive to a conjunction of constraints for delivering facts from said means for storing; a component intersection filter connected to said means for storing and said control means.
Claim 31
Dependent Claim
55 words
A filter engine according to claim 25, wherein said component intersection filter is configured to eliminate from further consideration facts which contain terms which are not within a component intersection set defined by an intersection of instantiations of corresponding terms of said predications wherein said corresponding terms are defined by a predetermined conjunction of constraints.
References Cited (Backward Citations)
US3964029A
Cited
US4593403A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-09-27 | 1997-03-29 | 1997-09-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-09-27 | 2001-03-29 | 2001-09-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-09-27 | 2005-03-29 | 2005-09-28 | $7700.00 | Window Closed / Lapsed |