US5608904A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for processing and optimizing queries having joins between structured data and text data
Assignee: Hewlett Packard Development Co LP
•
Filing: 1995-02-13
•
Granted: 1997-03-04
•
Expires: 2015-02-13
Abstract
Abstract Probe-based query processing for a database system that loosely integrates a structured database and a text retrieval system is described. The query processing constructs a query plan that efficiently evaluates a conjunctive query having joins of structured and textual data by sending to the text retrieval system one or more text search/retrieve operations.
Inventors
- 👤 Surajit Chaudhuri
- 👤 Umeshwar Dayal
- 👤 Tak W. Yan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 11:02
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24547; G06F16/2458; G06F16/2471; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
75 words
A method for executing a conjunctive query that includes joins of structured data from a structured database system and external textual data from a text retrieval system, the joins having multiple join predicates, comprising: (a) selecting at least one probing column from the multiple join predicates; and (b) reducing execution time of the conjunctive query by probing the external textual database to eliminate redundant queries to the external textual database which produce no matching documents.
Claim 2
Independent Claim
75 words
A method for executing a conjunctive query that includes joins of structured data from a structured database system and external textual data from a text retrieval system, the joins having multiple join predicates, comprising: (a) selecting at least one probing column from the multiple join predicates; and (b) reducing execution time of the conjunctive query by probing the external textual database to eliminate redundant queries to the external textual database which produce no matching documents.
Claim 3
Independent Claim
100 words
A method for processing a conjunctive query that includes joins of structured data from a structured database and external textual data from a text retrieval system, comprising: (a) selecting at least one probing column from the multiple join predicates if one or more of the joins has multiple join predicates; (b) determining an estimated cost of at least one probe-based optimization plan; (c) determining an estimated cost of at least one conventional optimization plan; (d) selecting one of the optimization plans based on the lowest estimated cost; and (e) evaluating the conjunctive query in accordance with the selected optimization plan.
Claim 4
Independent Claim
100 words
A method for processing a conjunctive query that includes joins of structured data from a structured database and external textual data from a text retrieval system, comprising: (a) selecting at least one probing column from the multiple join predicates if one or more of the joins has multiple join predicates; (b) determining an estimated cost of at least one probe-based optimization plan; (c) determining an estimated cost of at least one conventional optimization plan; (d) selecting one of the optimization plans based on the lowest estimated cost; and (e) evaluating the conjunctive query in accordance with the selected optimization plan.
Claim 5
Dependent Claim
84 words
A method as recited in claim 2, wherein when the selected optimization plan is a probe-based optimization plan, said evaluating (e) comprises: (e1) sending text search/retrieve operations to the text retrieval system to obtain a result set of matching text documents; (e2) probing the external textual database to determine presence of matching text documents; and (e3) avoiding said sending (e1) of certain of the text search/retrieve operations if said probing (e2) indicates that the certain of the text search/retrieve operations find no matching documents.
Claim 6
Dependent Claim
29 words
A method as recited in claim 3, wherein said evaluating (e) further comprises (e4) joining the result set with relations of the conjunctive query associated with the structured data.
Claim 7
Dependent Claim
46 words
A method as recited in claim 3, wherein when the selected optimization plan is a conventional optimization plan, said evaluating (e) comprises: sending text search/retrieve operations to the text retrieval system to obtain a result set of matching text documents without probing the external textual database.
Claim 8
Dependent Claim
24 words
An apparatus as recited in claim 5, wherein said structured database system further includes a probe cache for storing results of previously performed probes.
Claim 9
Dependent Claim
44 words
An apparatus as recited in claim 6, wherein said query executor further reduces execution time by performing said probing only when the optimal execution plan is a probe-based execution plan and when said probe cache does not already store the results of said probing.
Claim 10
Dependent Claim
44 words
An apparatus as recited in claim 7, wherein said structured database system further includes a document cache for storing the matching documents retrieved from the external textual database, the matching documents stored in said document cache being associated with entries in said probe cache.
Claim 11
Dependent Claim
123 words
A loosely integrated database system capable of evaluating a conjunctive query that includes joins of structured data and external textual data, the joins having multiple join predicates, comprising: a text retrieval system having textual data; and a structured database system having structured data, said structured database system comprising: a query optimizer for selecting an optimal execution plan from a plurality of available execution plans based on cost; and a query executor for executing the optimal execution plan to evaluate the conjunctive query, wherein when the optimal execution plan is a probe-based execution plan, said query executor reduces execution time of the conjunctive query by probing the external textual database to eliminate redundant queries to the external textual database which produce no matching documents.
Claim 12
Dependent Claim
123 words
A loosely integrated database system capable of evaluating a conjunctive query that includes joins of structured data and external textual data, the joins having multiple join predicates, comprising: a text retrieval system having textual data; and a structured database system having structured data, said structured database system comprising: a query optimizer for selecting an optimal execution plan from a plurality of available execution plans based on cost; and a query executor for executing the optimal execution plan to evaluate the conjunctive query, wherein when the optimal execution plan is a probe-based execution plan, said query executor reduces execution time of the conjunctive query by probing the external textual database to eliminate redundant queries to the external textual database which produce no matching documents.
References Cited (Backward Citations)
US5315504A
Cited
US5367677A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-03-03 | 2000-09-02 | 2001-03-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-03-03 | 2004-09-02 | 2005-03-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-03-03 | 2008-09-02 | 2009-03-04 | $7700.00 | Window Closed / Lapsed |