Managing expressions in a database system

• US 20030212670A1
• Filed: 09/24/2002
• Published: 11/13/2003
• Est. Priority Date: 05/10/2002
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Yalamanchi, Aravind, Gawlick, Dieter, Srinivasan, Jagannathan
• Granted Patent: US 7,127,467 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: G06F 40/137 Hierarchical processing, e.g. outlines
• CPC Class Codes: Y10S 707/961 Associative
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method for managing expressions includes receiving a first query that includes a first conditional expression. The first expression is then represented as data in a column of a table. A second query is received that specifies a first set of criteria, and the second query is executed to select data based at least on whether expressions in the column satisfy the first set of criteria. In an embodiment, the second query further specifies a second set of criteria, wherein executing the second query includes selecting data based on whether data in columns other than the expression column satisfy the second criteria. A special index is defined, which can be created on the column that stores the expressions as data, to filter large sets of expressions efficiently. A method of evaluating an expression set stored as data in a table classifies each predicate from each expression, and filters the expression set based on the predicate classification.

Claims

1. A method for managing expressions in a database, the method comprising the steps of:

receiving a first query that includes a first conditional expression;

representing the first conditional expression as data in a column of a table;

receiving a second query that specifies a first set of one or more criteria; and

executing the second query to select data based at least on whether conditional expressions in the column satisfy the first set of criteria.

2. The method of claim 1, wherein the second query further specifies a second set of one or more criteria, and wherein the step of executing the second query includes selecting data based on whether data in one or more columns other than the column satisfies the second set of criteria.

3. The method of claim 1, wherein the step of receiving a first query includes receiving the first query from a first user of a database application, and wherein the first conditional expression specifies one or more criteria that must be satisfied by data for the data to be of interest to the user.

4. The method of claim 3, wherein the step of receiving the second query includes receiving the second query from a second user of a database application, and wherein the second query specifies a second set of one or more criteria that must be satisfied by data for the data to be made available to the first user, thus enabling mutual filtering among the first user and the second user.

5. The method of claim 1, wherein the step of receiving a first query includes receiving the first query from a subscriber to an information subscription system, and wherein the first conditional expression specifies one or more criteria that must be satisfied by data for the data to be of interest to the subscriber.

6. The method of claim 5, wherein the step of receiving the second query includes receiving the second query from a publisher in the subscription system, and wherein the second query specifies a second set of one or more criteria that must be satisfied by data for the data to be published to the subscriber.

7. The method of claim 1, wherein the step of receiving the second query includes receiving the second query from a publisher in an information subscription system, and wherein the second query specifies a second set of one or more criteria that must be satisfied by data for the data to be published to a subscriber to the subscription system.

8. The method of claim 1, wherein the step of representing a first conditional expression as data in a column includes representing a set of first conditional expressions from a plurality of first queries as data in the column, the method further comprising the steps of:

creating an index on the column of the table by

grouping predicates from the set of first conditional expressions based on predicate identifiers that are associated with respective criteria of the first set of criteria;

storing in a predicate table sets of predicate operators and constants in association with respective predicate identifiers;

creating a concatenated bitmap index based on a set of predicate operators and constants associated with a particular predicate identifier.

9. A method for evaluating an expression set that is stored as data in a column of a table, the method comprising the steps of:

classifying each predicate from each expression of the expression set as one of,

an indexed attribute predicate, wherein a bitmap index is created based on a set of operator and constant attributes that are stored in respective columns of a predicate table in association with a respective predicate identifier;

a stored attribute predicate, wherein a set of operator and constant attributes are stored in respective columns of the predicate table in association with a respective predicate identifier, and wherein no index is created on the set of operator and constant attributes;

a sparse predicate, in which a predicate identifier associated with a sparse predicate is uncommon in the expression set, and wherein a sparse predicate is stored as data in the predicate table; and

filtering the expression set based on the classification of predicates from the expression set.

10. The method of claim 9, wherein the step of filtering the expression set includes the steps of:

first, filtering the indexed attribute predicates to obtain a first set of expressions that includes one or more expressions for which all of its indexed attribute predicates are true for a given data item;

second, filtering the stored attribute predicates of the first set of expressions to obtain a second set of expressions that includes one or more expressions for which all of its stored attributes are true for the given data item; and

third, filtering the sparse predicates, if any, of the second set of expressions to obtain a third set of expressions that includes one or more expressions for which all of its predicates are true for the given data item.

11. The method of claim 10, further comprising the step of:

publishing the given data item to a subscriber to an information subscription system that has expressed interest in data that meets criteria represented by an expression from the third set of expressions.

12. A computer-readable medium storing an index that is built on a table that has a plurality of rows, the index comprising:

concatenated bit vectors, wherein each bit vector is associated with one of an operator and a constant that are each stored in respective columns of the table;

wherein the operator and the constant are associated with a predicate of one or more predicates from a conditional expression that specifies one or more criteria that must be satisfied by data for the data to be of interest to a subscriber to a subscription system.

13. A computer-readable medium carrying one or more sequences of instructions for managing expressions in a database, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving a first query that includes a first conditional expression;

representing the first conditional expression as data in a column of a table;

receiving a second query that specifies a first set of one or more criteria; and

executing the second query to select data based at least on whether conditional expressions in the column satisfy the first set of criteria.

14. The computer-readable medium of claim 13, wherein the second query further specifies a second set of one or more criteria, and wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of executing the second query by selecting data based on whether data in one or more columns other than the column satisfies the second set of criteria.

15. The computer-readable medium of claim 13, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of receiving a first query by receiving the first query from a first user of a database application, and wherein the first conditional expression specifies one or more criteria that must be satisfied by data for the data to be of interest to the user.

16. The computer-readable medium of claim 15, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of receiving the second query by receiving the second query from a second user of a database application, and wherein the second query specifies a second set of one or more criteria that must be satisfied by data for the data to be made available to the first user, thus enabling mutual filtering among the first user and the second user.

17. The computer-readable medium of claim 13, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of receiving a first query by receiving the first query from a subscriber to an information subscription system, and wherein the first conditional expression specifies one or more criteria that must be satisfied by data for the data to be of interest to the subscriber.

18. The computer-readable medium of claim 17, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of receiving a second query by receiving the second query from a publisher in the subscription system, and wherein the second query specifies a second set of one or more criteria that must be satisfied by data for the data to be published to the subscriber.

19. The computer-readable medium of claim 13, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of receiving the second query by receiving the second query from a publisher in an information subscription system, and wherein the second query specifies a second set of one or more criteria that must be satisfied by data for the data to be published to a subscriber to the subscription system.

20. The computer-readable medium of claim 13, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of representing a first conditional expression as data in a column by representing a set of first conditional expressions from a plurality of first queries as data in the column, and wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

creating an index on the column of the table by

grouping predicates from the set of first conditional expressions based on predicate identifiers that are associated with respective criteria of the first set of criteria;

storing in a predicate table sets of predicate operators and constants in association with respective predicate identifiers;

creating a concatenated bitmap index based on a set of predicate operators and constants associated with a particular predicate identifier.

21. A computer-readable medium carrying one or more sequences of instructions for evaluating an expression set that is stored as data in a column of a table, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

classifying each predicate from each expression of the expression set as one of,

an indexed attribute predicate, wherein a bitmap index is created based on a set of operator and constant attributes that are stored in respective columns of a predicate table in association with a respective predicate identifier;

a stored attribute predicate, wherein a set of operator and constant attributes are stored in respective columns of the predicate table in association with a respective predicate identifier, and wherein no index is created on the set of operator and constant attributes;

a sparse predicate, in which a predicate identifier associated with a sparse predicate is uncommon in the expression set, and wherein a sparse predicate is stored as data in the predicate table; and

filtering the expression set based on the classification of predicates from the expression set.

22. The computer-readable medium of claim 21, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the step of filtering the expression set by performing the steps of:

first, filtering the indexed attribute predicates to obtain a first set of expressions that includes one or more expressions for which all of its indexed attribute predicates are true for a given data item;

second, filtering the stored attribute predicates of the first set of expressions to obtain a second set of expressions that includes one or more expressions for which all of its stored attributes are true for the given data item; and

third, filtering the sparse predicates, if any, of the second set of expressions to obtain a third set of expressions that includes one or more expressions for which all of its predicates are true for the given data item.

23. The computer-readable medium of claim 22, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to further perform the step of:

publishing the given data item to a subscriber to an information subscription system that has expressed interest in data that meets criteria represented by an expression from the third set of expressions.

24. An apparatus for managing expressions in a database, comprising:

means for receiving a first query that includes a first conditional expression;

means for representing the first conditional expression as data in a column of a table;

means for receiving a second query that specifies a first set of one or more criteria; and

means for executing the second query to select data based at least on whether conditional expressions in the column satisfy the first set of criteria.

25. An apparatus for evaluating an expression set that is stored as data in a column of a table, comprising:

means for classifying each predicate from each expression of the expression set as one of,

an indexed attribute predicate, wherein a bitmap index is created based on a set of operator and constant attributes that are stored in respective columns of a predicate table in association with a respective predicate identifier;

a stored attribute predicate, wherein a set of operator and constant attributes are stored in respective columns of the predicate table in association with a respective predicate identifier, and wherein no index is created on the set of operator and constant attributes;

a sparse predicate, in which a predicate identifier associated with a sparse predicate is uncommon in the expression set, and wherein a sparse predicate is stored as data in the predicate table; and

means for filtering the expression set based on the classification of predicates from the expression set.