Methods and apparatus for efficiently splitting query execution across client and server in an object-relational mapping

[0002] This is a continuation of application Ser. No. 09/105,955, filed Jun. 29, 1998, abandoned, which claims the benefit of U.S. provisional application No. 60/068,415, filed Dec. 22, 1997, all of which are incorporated herein by reference.

[0003] The following identified U.S. patent applications are relied upon and are incorporated by reference in this application.

[0004] Provisional U.S. patent application Ser. No. 60/068415, entitled System and Method for Mapping Between Objects and Databases,” filed on Dec. 22, 1997.

[0005] U.S. patent application Ser. No. 09/106,186, entitled “OBJECT-RELATIONAL MAPPING TOOL THAT PROCESSES VIEWS,” U.S. Pat. No. 6,175,837, and filed on Jun. 29, 1998.

[0006] U.S. patent application Ser. No. 09/106,189, entitled “EVOLUTION OF OBJECT-RELATIONAL MAPPING THROUGH SOURCE CODE MERGING,” pending, and filed on Jun. 29, 1998.

[0007] U.S. patent application Ser. No. 09/105,957, “INTEGRATING BOTH MODIFICATIONS TO AN OBJECT MODEL AND MODIFICATIONS TO A DATABASE INTO SOURCE CODE BY AN OBJECT-RELATIONAL MAPPING TOOL,” pending, and filed on Jun. 29, 1998.

[0008] U.S. patent application Ser. No. 09/106,210, entitled “RULE-BASED APPROACH TO OBJECT-RELATIONAL MAPPING STRATEGIES,” pending, and filed on Jun. 29, 1998.

[0009] U.S. patent application Ser. No. 09/106,212, entitled “USER INTERFACE FOR THE SPECIFICATION OF LOCK GROUPS,” and filed on Jun. 29, 1998.

[0010] U.S. patent application Ser. No. 09/106,119, entitled “A FINE-GRAINED CONSISTENCY MECHANISM FOR OPTIMISTIC CONCURRENCY CONTROL USING LOCK GROUPS,” pending, and filed on Jun. 29, 1998.

[0011] U.S. patent application Ser. No. 09/106,211, entitled “USER INTERFACE FOR THE SPECIFICATION OF INDEX GROUPS OVER CLASSES,” pending, and filed on Jun. 29, 1998.

[0012] U.S. patent application Ser. No. 09/106,188, entitled “METHOD AND APPARATUS FOR CREATING INDEXES IN A RELATIONAL DATABASE CORRESPONDING TO CLASSES IN AN OBJECT-ORIENTED APPLICATION,” pending, and filed on Jun. 29, 1998.

[0013] U.S. patent application Ser. No. 09/106,190, entitled “METHOD AND APPARATUS FOR LOADING STORED PROCEDURES IN A DATABASE CORRESPONDING TO OBJECT-ORIENTED DATA DEPENDENCIES,” pending and filed on Jun. 29, 1998.

[0014] U.S. patent application Ser. No. 09/106,046, entitled “AN INTEGRATED GRAPHICAL USER INTERFACE METHOD AND APPARATUS FOR MAPPING BETWEEN OBJECTS AND DATABASES,” pending, and filed on Jun. 29, 1998.

[0015] A. Field of the Invention

[0016] This invention relates generally to computer databases and, more particularly, to methods and apparatus for providing object-based querying of a non-object-based database.

[0017] B. Description of the Related Art

[0018] Conventional, non-object-based database management systems (CDBMS) are widely used to store data. One popular type of a CDBMS, a relational database management system (RDBMS), stores data in the form of related tables. An RDBMS, however, is limited to relational (or tabular) data and does not have the sophistication required to manipulate more complex items such as objects associated with object-oriented programming languages. Some companies now provide an object-to-database mapping (ODM) system that converts objects to data and then stores the data in a CDBMS. With these systems, a software developer may to some extent integrate an object-oriented program with a CDBMS.

[0019] With both a CDBMS and an ODM system, however, data must be retrieved by using a standardized query language, such as SQL. Until now, therefore, software developers have not been able to take advantage of object-oriented programming languages to perform queries on data stored in a CDBMS. Instead, software developers have been required to formulate queries by using a standardized query language such as SQL. This approach limits software developers to the functions supported by SQL and does not allow them to take full advantages of the capabilities of object-oriented programming. Furthermore, in order to formulate SQL queries, software developers must learn how to map objects to the data stored in the DBMS.

[0020] There exists, therefore, a need for a system that allows software developers to formulate and perform object-based queries on data stored in a conventional, non-object-based DBMS.

[0021] Methods and apparatus consistent with the present invention, as embodied and broadly described herein, allow users to perform object-based querying in a distributed system having a non-object-based database management system.

[0022] In accordance with the invention, a method for performing object-based querying in a system having a non-object-based database management system comprises receiving an object-based query from a user program. The object-based query is separated into a server portion and a client portion, and the server portion is transmitted to the database management system.

[0023] The accompanying drawings, which are incorporated in, and constitute a part of, this specification illustrate an embodiment of the invention and, together with the description, serve to explain the advantages and principles of the invention. In the drawings,

[0024] FIG. 1 is a block diagram of a data processing system in which systems consistent with the invention may be implemented;

[0025] FIG. 2 is a flow diagram for performing an object-based query consistent with the invention;

[0026] FIG. 3 is a block diagram of a logical query tree consistent with the invention that may be used to separate an object query language query into a server portion and a client portion;

[0027] FIG. 4 is a flow diagram for a pessimistic concurrency control model consistent with the invention;

[0028] FIG. 5 is a block diagram depicting the logical flow of data in a pessimistic concurrency control model consistent with the invention;

[0029] FIG. 6 is a flow diagram of a repeatable-read optimistic concurrency control model consistent with the invention;

[0030] FIG. 7 is a block diagram depicting the logical flow of data in a repeatable-read optimistic concurrency control model consistent with the invention;

[0031] FIG. 8 is a block diagram depicting the logical flow of data in a read-committed optimistic concurrency control model consistent with the invention; and

[0032] FIG. 9 is a block diagram depicting the logical flow of data in a read-committed optimistic concurrency control model consistent with the invention.

[0033] Reference will now be made in detail to an implementation of the present invention as illustrated in the accompanying drawings. The same reference numbers may be used throughout the drawings and the following description to refer to the same or like parts.

[0034] A. Overview

[0035] Methods and apparatus consistent with the invention allow users to perform object-based querying in a distributed system having a conventional, non-object-based DBMS, such as an RDBMS. After beginning a user program initiated (UPI) transaction, a user initiates an object-based query that may be written using an object query language (OQL). A query is a predicate that determines the collection of objects or values in terms of their properties, including their relationships, and that does not explicitly specify the steps by which this collection is obtained. A query may include method invocations and may be defined in terms of other predicates, including subqueries. A standardized OQL is described, for example, in “Object Database Standard: ODMG 2.0,” by R. G. G. Cattell et al., Morgan Kaufmann Publishers, Inc., 1997.

[0036] An ODM/OQL process receives this query and creates a logical tree that contains nodes representing operations that are required for the query to be completed. Operations that can be performed by the RDBMS are transmitted to the RDBMS, preferably as an SQL query. The RDBMS executes the SQL query and returns data to the ODM/OQL process.

[0037] The ODM/OQL process receives data from the RDBMS, places it into appropriate fields of one or more objects, and stores the resulting objects in a memory, such as an object cache. The ODM/OQL process executes the remaining node operations (that could not be performed by the RDBMS) in conjunction with the objects stored in the object cache. The ODM/OQL process then forwards the results to the user program. When the user program has completed the UPI transaction, it commits the data to the RDBMS.

[0038] Methods and apparatus consistent with the invention also provide different types of concurrency control. One approach employs a pessimistic concurrency control model. In this model, the RDBMS locks any necessary data items and relinquishes those locks only when the UPI transaction, including all required queries, is complete. Another approach employs a repeatable-read optimistic concurrency control model. In this model, the ODM/OQL process confirms that data received from the RDBMS matches the data previously stored in the object cache. Another approach employs a read-committed optimistic concurrency control model. In this approach, if the object cache is updated by the user program, the ODM/OQL process ensures that subsequent queries that are part of the same UPI transaction receive the same updated data as contained in the object cache.

[0039] B. Architecture

[0040] FIG. 1 is a block diagram of a system in which the present invention may be implemented. System 100 comprises a client 110 connected to a server 170 via a network 165. Examples of network 165 include a local area network, a wide area network, or an internetwork such as the Internet.

[0041] Server 170 comprises an I/O interface 172, a network interface 174, a processor 176, and an RDBMS 188, each of which is connected to a bus 186. RDBMS 188 contains a plurality of tables of data. RDBMS 188 also receives SQL queries, executes the queries based on data stored in tables, and returns the resulting data.

[0042] Client 110 comprises a display device 115, a processor 120, an input/output (I/O) interface 125, a network interface 130, and a memory 140, each of which is connected to a bus 135. Memory 140 comprises an object cache 150, a user program 145, an ODM/OQL process 155, and a virtual machine 160. Object cache 150 is used to store objects for user program 145 or for ODM/OQL process 155.

[0043] User program 145 begins a UPI transaction, issues one or more OQL queries, and then completes the UPI transaction. In one implementation, user program 145 is created using the Java™ programming language. The Java programming language is described in a text entitled “The Java™ Tutorial” by Mary Campione and Kathy Walrath, Addison-Wesley, 1996.¹

[0044] 1 Sun, Sun Microsystems, Sun Microsystems Corporation, JavaSoft, the Sun Logo, and Java are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries.

[0045] ODM/OQL process 155 provides an interface between the object-based OQL queries issued by user program 145 and the data stored in tables in RDBMS 188. In one implementation, ODM/OQL process 155 is created using the Java™ programming language. Although this application shows the ODM and the OQL combined into one process, those skilled in the art will recognize that the two may be separate.

[0046] VM 160 is a virtual machine that provides an interface between a platform-independent process (such as a user program created using the Java programming language) and a specific platform. In one implementation, VM 160 is the Java™ Runtime Environment, which includes the Java™ Virtual Machine (JVM) and Java™ class libraries. The JVM is described in a text entitled “The Java Virtual Machine Specification,” by Tim Lindholm and Frank Yellin, Addison Wesley, 1996.

[0047] C. Architectural Operation

[0048] FIG. 2 is a flow diagram for performing object-based querying consistent with the present invention. After user program 145 begins a UPI transaction, it issues an OQL query. This OQL query is received by ODM/OQL process 155 (step 205). As described in further detail below in reference to FIG. 3, ODM/OQL process 155 separates the OQL query into one or more server portions and one or more client portions (step 210). ODM/OQL process 155 then transmits the server portions to one or more CDBMSs, such as RDBMS 188 (step 215). RDBMS 188 executes the server portion and provides the resulting data set to ODM/OQL process 155.

[0049] ODM/OQL process 155 receives the resulting data set, converts it into one or more objects, and stores the objects in object cache 150 (step 220). ODM/OQL process 155 executes the client portion of the OQL query in conjunction with the objects stored in object cache 150 (step 225), thereby creating one or more resulting objects and completing the OQL query. Finally, ODM/OQL process 155 forwards the results of the OQL query to user program 145 (step 230). This may be done, for example, either by providing user program 145 with a reference to the resulting objects or by providing user program 145 with copies of the actual resulting objects.

[0050] FIG. 3 is a diagram of a logical query tree consistent with the invention that may be used to separate an OQL query into a server portion and a client portion. The process for creating a logical tree from a query is well understood in the art, and is described, for example, in “The Theory of Relational Databases” by David Maier, Computer Science Press, 1983. Accordingly, the description in reference to FIG. 3 assumes that an OQL query has been converted into a logical tree.

[0051] In the example shown in FIG. 3, the OQL query tree contains nodes 1-15, each of which represent operations to be performed. Furthermore, the nodes of the OQL query tree form “subtrees.” For example, node 2 (and its subnodes 4-5, 8-9, and 12-13) and node 3 (and its subnodes 6-7, 10-11, and 14-15) each represents a “subtree” of the OQL tree represented by node 1. Similarly, node 5 (and its subnodes 8-9, and 12-13) represents a subtree of the tree represented by node 2. In order to complete the OQL query, the operation associated with each node must be performed.

[0052] In one implementation, it is desirable to have as many operations performed by RDBMS 188 as possible; in other words, the server portion should contain all operations that are supported by SQL. This may be achieved by including in the server portion all subtrees that require only operations that are supported by SQL.

[0053] In the example shown in FIG. 3, node 6 requires an operation that is supported by OQL and that cannot be parsed into any SQL portion. Similarly, node 9 requires an operation (a method call) that is not supported by SQL. The remaining nodes (2-5, 7-8, 10-15) require operations that are supported by SQL. Thus, the subtrees represented by nodes 4, 7, and 8 may be included in the server portion because these subtrees require only operations that are supported by SQL. In other words, these subtrees do not contain any nodes that represent non-SQL supported operations.

[0054] In contrast, the operation represented by nodes 6 and 9 are not supported by SQL, and therefore must be included in the client portion. The operation represented by node 3 depends on the operation represented by node 6, and therefore must also be included in the client portion. Similarly, the operation represented by node 5 depends on the operation represented by node 9, and therefore must also be included in the client portion. The operation represented by node 2 depends on the operation represented by node 5 (which, in turn depends on the non-SQL supported operation represented by node 9), and therefore must also be included in the client portion.

[0055] The description in reference to FIG. 3 is illustrative only. Those skilled in the art will recognize that operations required for an OQL query may be separated in other manners that are consistent with the invention. For example, it may be desirable to perform certain SQL portions on client 110 rather than on server 170.

[0056] An RDBMS is frequently used in a multi-user environment, with each user having concurrent access to data. Moreover, any given UPI transaction may require multiple queries before the transaction is completed and modifications committed to the RDBMS. In such an environment, it is possible that another user may alter RDBMS data during the time between multiple queries within a single UPI transaction. Concurrency controls are used to help ensure that a user program obtains consistent data from the RDBMS during the course of a UPI traction. Depending on the type of concurrency control employed, a multi-user environment may appear to be a single-user environment from the perspective of the single user.

[0057] FIG. 4 is a flow diagram of a pessimistic concurrency control model consistent with the invention. For purposes of explanation, FIG. 4 is described in connection with the logical flow of information shown in FIG. 5, which shows user program 145, ODM/OQL process 155 and object cache 150, and RDBMS 188. Under a pessimistic concurrency control model, user program 145 will perceive no changes to data (other than changes made by user program 145) because RDBMS 188 locks any required data items for the duration of the UPI transaction.

[0058] Specifically, user program 145 begins a UPI transaction, which is received by ODM/OQL process 155 (step 405). In response, ODM/OQL process 155 begins a database transaction with RDBMS 188 (step 410). ODM/OQL process 155 then receives and processes queries from user program 145 (step 420).

[0059] In particular, user program 145 initiates query 1, which is received and processed by ODM/OQL process 155. Query 1 is separated into a server portion and client portion, as explained above in reference to FIG. 3, and the server portion is transmitted to RDBMS 188. RDBMS 188 executes the server portion, locks any required data items, and returns data to ODM/OQL process 155. ODM/OQL process 155 converts the data into one or more objects, and stores the objects in object cache 150. After executing the client portion of query 1 in conjunction with object cache 150, ODM/OQL process 155 stores the resulting objects in object cache 150. ODM/OQL process 155 then returns result 1 to user program 145, as described above in reference to FIG. 2.

[0060] At some later point in the UPI transaction, user program 145 issues query 2. As described above in reference to query 1, the server portion of query 2 is passed to RDBMS 188, data is received from RDBMS 188 by ODM/OQL process 155, and result 2 is forwarded to user program 145.

[0061] Later in the UPI transaction, user program 145 issues a command to update the data. ODM/OQL process 155 receives this command, and passes it through as an update command to RDBMS 188, which updates the data (step 425). Query 3 is then completed in a manner similar to that described above in reference to queries 1 and 2. In the example shown in FIG. 5, user program 145 then commits the UPI transaction. Upon receiving this command (step 430), ODM/OQL process 155 commits the changes to RDBMS 188, which releases the locks previously obtained on the data sets (step 435).

[0062] FIG. 6 is a flow diagram of a repeatable-read optimistic concurrency control model consistent with the invention. For purposes of explanation, FIG. 6 is described in connection with the logical flow of information shown in FIG. 7.

[0063] After the UPI transaction begins (step 605), ODM/OQL process 155 receives query 1 from user program 145 (step 610). The server portion of query 1 is passed to RDBMS 188, a data set is received from RDBMS 188 by ODM/OQL process 155, and result 1 is forwarded to user program 145. (step 615). During execution of any given server portion, such as the server portion associated with query 1, RDBMS 188 may lock the data sets associated with a query. These locks are not maintained throughout the remainder of the UPI transaction, however, as is the case with the pessimistic model of concurrency control.

[0064] At some later point, user program 145 issues query 2 to ODM/OQL process 155 (step 620), which separates query 2 into a server portion and a client portion (step 625). ODM/OQL process 155 then transmits the server portion to RDBMS 188, which executes the server portion and returns data to ODM/OQL process 155 (step 630). ODM/OQL process 155 receives the data and converts it into one or more objects (step 635). For purposes of explanation, these objects are referred to as “query 2 RDBMS objects.”

[0065] ODM/OQL process 155 next reconciles the data contained in the query 2 RDBMS objects with data previously stored in object cache 150 (e.g., as a result of query 1) (step 640). Specifically, ODM/OQL process 155 determines whether any portion of the data contained in the query 2 RDBMS objects has previously been stored in object cache 150. Such a portion of data is hereinafter called the “overlapping data.” If there exists any overlapping data, ODM/OQL process 155 uses the overlapping data contained in object cache 150 rather than the overlapping data in the query 2 RDBMS objects.

[0066] In one example, RDBMS 188 contains a table that includes a list of employee names, and data associated with each employee, such as salary, and gender. Query 1 may request all information for each male employee. The result of query 1 may be a plurality of “employee objects” stored in object cache 150, each of which contains a name, salary, and gender corresponding to a male employee.

[0067] Query 2 may request those employees who have a salary in excess of $100,000. The result of query 2 may be a plurality of “employee objects”, each of which contains a name, salary, and gender of an employee that has a salary in excess of $100,000.

[0068] Suppose, however, that between query 1 and query 2, another user modified the salary for a particular male employee named John from $150,000 to $125,000. ODM/OQL process 155 compares the query 2 RDBMS employee objects with the employee objects previously stored in object cache 150. In doing so, ODM/OQL process 155 determines that the salary indicated for John in his query 2 RDBMS employee object differs from that indicated for John in his corresponding employee object already in object cache 150. In order to ensure that data does not change from the perspective of user program 145, ODM/OQL process 155 does not insert the query 2 RDBMS employee object for John into object cache 150.

[0069] After reconciling the data contained in the query 2 RDBMS objects with data previously stored in object cache 150, ODM/OQL process 155 executes the client portion of the OQL query in conjunction with object cache 150. ODM/OQL process 155 then forwards result 2 to user program 145, as described above in reference to FIG. 2 (step 645).

[0070] At some point later in the UPI transaction, user program 145 issues a command to update the data. ODM/OQL process 155 updates object cache 150 in response to this command, but does not issue any command to update RDBMS 188. As a result, RDBMS 188 is unaffected by the update command from user program 145. Query 3 is later processed in a manner similar to that described above for query 2. User program 145 then commits the UPI transaction (step 650); in response, ODM/OQL process 155 updates RDBMS 188 with data from object cache 150 and commits the change (step 655). Before updating RDBMS 188, ODM/OQL process 155 determines whether the data contained in RDBMS 188 is consistent with data read from RDBMS 188 during earlier portions the UPI transaction. If it is not, the UPI transaction is aborted.

[0071] FIG. 8 is a flow diagram of a read-committed optimistic concurrency control model consistent with the present invention. For purposes of explanation, FIG. 8 is described in connection with the logical flow of information shown in FIG. 9.

[0072] After the UPI transaction begins (step 805), ODM/OQL process 155 receives query 1 from user program 145 (step 810). The server portion of query 1 is passed to RDBMS 188, data is received from RDBMS 188 by ODM/OQL process 155, and result 1 is forwarded to user program 145 (step 815). As explained above in reference to FIG. 6; RDBMS 188 may lock the data items associated with a query.

[0073] Until an update command is received from user program 145 (step 815), all subsequent queries are processed in the same manner described above in reference to query 1 in FIG. 8. As a result, pre-update queries receive data that has been committed to RDBMS 188. When an update command is received from user program 145, ODM/OQL process 155 updates object cache 150 but does not update RDBMS 188.

[0074] If a query is received after an update command, the procedure may differ from that for pre-update queries. Because the update command was not passed through to RDBMS 188, the data contained in object cache 150 may differ from that received from RDBMS 188. To account for this, when ODM/OQL process 155 receives a post-update query (such as query 2 shown in FIG. 9), it begins a database transaction with RDBMS 188 (step 825) and updates RDBMS 188 by flushing the data contained in object cache 150 (step 830). ODM/OQL process 155 then transmits the server portion of query 2 to RDBMS 188 and receives the resulting data (step 835). Once it has received the resulting data, ODM/OQL process 155 aborts the database transaction (step 840), thereby rolling back RDBMS 188 to the state that existed before RDBMS 188 was updated by flushing object cache 150.

[0075] ODM/OQL process 155 converts the data received from RDBMS 188 into one or more objects and stores them in object cache 150 (step 845). ODM/OQL process 155 then executes the client portion of query 2 in conjunction with object cache 150 and forwards result 2 to user program 145 (step 850). At some later point, ODM/OQL process 155 receives a commit command from user program 145 (step 855). In response, ODM/OQL process 155 begins a database transaction with RDBMS 188, updates RDBMS 188 by flushing the data contained in object cache 150, and commits the change to RDBMS 188 (step 860).

[0076] FIG. 8 is presented for purposes of illustration, and those skilled in the art will recognize that variations are possible consistent with the invention. Other methods and apparatus for handling post-update queries may also be used consistent with the invention. For example, rather than aborting the database transaction after receiving data from RDBMS 188 for the server portion of query 2, ODM/OQL process 155 may maintain open the database transaction until a commit command is received from user program 145. There may also exist alternate approaches that do not flush cache updates to the database.

[0077] D. Conclusion

[0078] As described in detail above, methods and apparatus consistent with the present invention allow users to perform object-based querying in a distributed system having an RDBMS. The foregoing description of an implementation of the invention has been presented for purposes of illustration and description. Modifications and variations are possible in light of the above teachings or may be acquired from practicing the invention.

[0079] For example, the detailed description describes an ODM that executes on the same machine as a user program, but that need not be the case. Furthermore, the foregoing description is based on the Java™ programming environment, OQL, SQL, and an RDBMS; but those of skill in the art will recognize that another programming environment, object-based query language, standardized query language, and non-object-based DBMS, respectively, may be used consistent with the invention. Furthermore, although the description is based on the server portion including SQL operations, the server portion could also include OQL operations. Moreover, although the described implementation includes software, the invention may be implemented as a combination of hardware and software or in hardware alone. Additionally, although aspects of the present invention are described as being stored in memory, one skilled in the art will appreciate that these aspects can also be stored on other types of computer-readable media, such as secondary storage devices, like hard disks, floppy disks, or CD-ROM; a carrier wave from the Internet; or other forms of RAM or ROM. The scope of the invention is therefore defined by the claims and their equivalents.