System and method for performing database queries using a stack machine

• US 6,253,194 B1
• Filed: 06/16/1998
• Issued: 06/26/2001
• Est. Priority Date: 06/16/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Johnson, David L., Parlin, David R., Stevens, Warren G., Wigton, R. Scott
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/097,925
• Time in Patent Office: 1,106 Days
• Field of Search: 707/1-2, 707/3, 707/4, 707/5, 707/104, 379/219, 717/1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2438 Embedded query languages
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A stack-language interface between a client application and its underlying database. To query the database, the client application passes a search expression to a database API. The search expression includes simple operands, which define values for individual search criteria, and one or more operators, which define the logical relationship between two or more operands. Upon receiving the search expression, the database API searches the database to retrieve records satisfying the search criteria. For each record, the database API executes the search expression on the stack machine to determine if the record matches the search criteria as defined by the operands and operators in the search expression. Once the relevant records are retrieved, the database API may present a list of objects representing those records to the client application.

Claims

1. A computer-implemented method for querying a database using a stack machine, wherein the database comprises a plurality of records, to retrieve information satisfying a search, comprising the steps of:

building a first operand defining a first value for a first search criterion of the search;

building a second operand and defining a second value for a second search criterion of the search;

building an operator defining a logical relationship between the first operand and the second operand, the logical relationship being dependent on the search;

creating a search expression comprising the first operand, the second operand, and the operator, the search expression being created in accordance with a stack-language structure;

passing the search expression to an Application Programming Interface, wherein the Application Programming Interface performs a sequence comprising the steps of;

identifying those records that satisfy the search expression using a stack machine; and

receiving the records from the database, which satisfy the search expression.

2. The computer-implemented method of claim 1, wherein the first operand defines a value for a parameter of an object in the database.

3. The computer-implemented method of claim 2, wherein the parameter of the object is a field of a record in the database.

4. The computer-implemented method of claim 1, wherein the second operand defines a value for a parameter of an object in the database, the parameter being an identifier of a table within the database.

5. The computer-implemented method of claim 4, wherein the table within the database contains a plurality of rows and a plurality of columns, each row in the plurality of rows representing a record in the database, and each column in the plurality of columns representing a field for the plurality of rows.

6. The computer-implemented method of claim 1, wherein the step of passing the search expression includes passing a command to initiate the query.

7. The computer-implemented method of claim 1, wherein the object received represents the results of performing a search on the database for records in the database which satisfy the search.

8. The computer-implemented method of claim 7, wherein the object represents a list of records in the database, each of the records comprising a value in a first field which satisfies the first search criterion of the first operand and a value in a second field which satisfies the second search criterion of the second operand.

9. The computer-implemented method of claim 8, wherein a logical relationship between the value in the first field and the value in the second field satisfies the logical relationship defined by the operator.

10. The computer-implemented method of claim 1, further comprising, validating the search expression to insure that the search expression is in the proper stack-language structure.

11. A computer-implemented method for querying a database using a stack machine, wherein the database comprises a plurality of records, to retrieve information satisfying a search, comprising the steps of:

passing a search expression created in accordance with a stack-language structure from a client application to a database API, the client application operative to accept an input defining a search comprising at least one search criteria, the search expression comprising a command representative of the search criteria for the search, the database API comprising the stack machine operative to execute the search expression on a stack machine for evaluation;

executing the search expression on the stack machine to identify a record in the database which satisfies the search criteria; and

passing the identified record from the database to the client application as a unit of data capable of being manipulated as a single object.

12. The computer-implemented method of claim 11, wherein the command comprises an operand defining a value for a field of the record in the database.

13. The computer-implemented method of claim 12, wherein the search expression further comprises a second command, the second command comprising a second operand defining a second value for a second field of the record in the database.

14. The computer-implemented method of claim 13, wherein the search expression further comprises a third command, the third command comprising an operator defining a logical relationship between the first operand and the second operand, the logical relationship being dependent on the search.

15. The computer-implemented method of claim 11, further comprising, identifying candidate records from the plurality of records in the database using at least one index associated with the plurality of records to identify those candidate records that satisfy the search expression using the stack machine.

16. The computer-implemented method of claim 11, further comprising, identifying candidate records from the plurality of records in the database using at least one index associated with the plurality of records.

17. A computer-readable medium having computer-executable instructions for querying a database comprising a plurality of objects to retrieve information satisfying a search, which when executed perform the steps of:

building a first operand defining a first value for a first search criterion of the search;

building a second operand defining a second value for a second search criterion of the search;

building an operator defining a logical relationship between the first operand and the second operand, the logical relationship being dependent on the search;

creating a search expression comprising the first operand, the second operand, and the operator, the search expression being created in accordance with a stack-language structure;

passing the search expression to an Application Programming Interface and placing the search expression in a stack language structure;

using a stack machine to evaluate the search expression in the stack language structure and compare the search expression to the plurality of objects in the database; and

receiving an object, which satisfies the search criteria.

18. The computer-implemented method of claim 17, further comprising, identifying candidate records from the plurality of records in the database using at least one index associated with the plurality of records.

19. A computer readable medium having computer executable instructions for forming a database query, to search the database comprising a plurality of records, which instructions when executed, perform the steps, comprising:

generating a logical expression comprising the steps of;

receiving a first operand from a client application, the first operand defining a first search criterion for a search of a database;

pushing the first operand on a stack machine, the stack machine comprising a location in the memory for storing, data in a “

last-in-first-out”

scheme;

receiving a second operand from the client application, the second operand defining a second search criterion for the search of the database;

pushing the second operand on the stack machine;

receiving an operator from the client application, the operator defining a logical relationship between the first operand and the second operand; and

pushing the operator on the stack machine;

identifying candidate records from the plurality of records in the database using at least one index associated with each record;

evaluating the candidate records using the stack machine to identify a record in the database which satisfies the logical relationship between the first operand and the second operand; and

returning the record to the client application as an object.

20. The computer readable medium of claim 19, wherein the first search criterion comprises a value for a parameter of an object in the database.

21. The computer readable medium of claim 20, wherein the parameter of the object represents a field of a record in the database.

22. The computer readable medium of claim 19, wherein the step of identifying the record in the database comprises evaluating the stack machine to construct a search filter, the search filter representing a test embodying the fist search criterion, the second search criterion, and the logical relationship between the first operand and the second operand.

23. The computer readable medium of claim 22, further comprising computer executable instructions for performing the step of accessing the database to apply the search filter to the information therein and retrieving the information that satisfies the search filter.

24. The computer readable medium of claim 19, wherein the step of returning the record to the client application comprises formatting the record such that the record is capable of being manipulated as a unit of information.

25. The computer-implemented method of claim 19, further comprising, identifying candidate records from the plurality of records in the database using at least one index associated with the plurality of records.

26. A computer-readable medium having computer-executable components, comprising:

a database containing information, the information comprising at least one table, the table comprising at least one record, and the record comprising at least one field;

a client application associated with the database and operative to receive input defining a search of the database, the client application further operative to build a first operand and a second operand, the first operand defining a first value for a first search criterion of the search, the second operand defining a second value for a second search criterion of the search, the client application further operative to build an operator, the operator defining a logical relationship between the first operand and the second operand;

a database API operative to receive from the client application the first operand, the second operand, and the operator within a search expression, the search expression having the first operand, the second operand, and the operator assembled in accordance with a stack-language structure, the database API further operative to store the first operand, the second operand, and the operator in a stack-language structure in memory, the database API comprising a stack machine operative to evaluate the information in the database for conformity with the first operand, the second operand, and the operator stored in the stack-language structure.

27. The computer-readable medium of claim 26, wherein the first value is related to the field of the record within the database.

28. The computer-readable medium of claim 27, wherein the second value is related to a second field of the record within the database.

29. The computer-implemented method of claim 26, wherein the API is further operative to identify candidate records from the plurality of records in the database using at least one index associated with the plurality of records.