Source: http://www.google.com/patents/US5765159?dq=patent:7945653
Timestamp: 2016-02-06 21:38:41
Document Index: 199647181

Matched Legal Cases: ['art 502', 'art 502', 'art 502', 'art 502', 'art 502', 'art 602', 'art 602', 'art 702', 'art 702', 'art 702', 'art 702', 'art 1402', 'art 1402', 'art 1402', 'art 1502', 'art 1502', 'art 1502', 'art 1602', 'art 1602', 'art 1602', 'art 1702', 'art 1702', 'art 1702', 'art 1702', 'art 1702', 'art 1802', 'art 1802', 'art 1802', 'art 1402']

Patent US5765159 - System and method for generating an optimized set of relational queries for ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsThe processing of object-oriented queries so as to retrieve data from a relational database management system (RDBMS) is described. An object-oriented query and at least one prefetch path are received from an object-oriented source (such as an application or user) . The prefetch path identifies one or...http://www.google.com/patents/US5765159?utm_source=gb-gplus-sharePatent US5765159 - System and method for generating an optimized set of relational queries for fetching data from a relational database management system in response to object queries received from an object oriented environmentAdvanced Patent SearchPublication numberUS5765159 APublication typeGrantApplication numberUS 08/870,581Publication dateJun 9, 1998Filing dateMay 21, 1997Priority dateDec 29, 1994Fee statusLapsedAlso published asUS5799309Publication number08870581, 870581, US 5765159 A, US 5765159A, US-A-5765159, US5765159 A, US5765159AInventorsVenkatachary SrinivasanOriginal AssigneeInternational Business Machines CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (16), Non-Patent Citations (10), Referenced by (161), Classifications (13), Legal Events (3) External Links: USPTO, USPTO Assignment, EspacenetSystem and method for generating an optimized set of relational queries for fetching data from a relational database management system in response to object queries received from an object oriented environment
US 5765159 AAbstract
The processing of object-oriented queries so as to retrieve data from a relational database management system (RDBMS) is described. An object-oriented query and at least one prefetch path are received from an object-oriented source (such as an application or user) . The prefetch path identifies one or more objects which are desired to be constructed. The object-oriented query is translated to a translated object query, where the translated object query is a relational database query capable of retrieving from the RDBMS data to initialize base attributes of top-level objects identified by the object-oriented query. A set of relational queries is generated from the translated object query and the prefetch path. These relational queries, which are capable of retrieving from the RDBMS data needed to construct the objects identified by the prefetch path, are processed by the RDBMS.
1. A method of processing object-oriented queries so as to retrieve data from a relational database management system (RDBMS), comprising the steps of:(1) receiving an object-oriented query and at least one prefetch path from an object-oriented source, said at least one prefetch path identifying one or more objects which are desired to be constructed; (2) translating said object-oriented query to a translated object query, said translated object query being a relational database query capable of retrieving from said RDBMS data to initialize base attributes of top-level objects identified by said object-oriented query; (3) generating from said translated object query and said at least one prefetch path a set of relational queries capable of retrieving from said RDBMS data to construct said objects identified by said at least one prefetch path; and (4) causing said RDBMS to process said set of relational queries. 2. The method of claim 1 in which said object-oriented query includes a condition list, and in which said at least one prefetch path includes at least one prefetch path component, wherein step (3) comprises the steps of:(a) determining whether said prefetch path component defines a (0,1)-to-(0,1) relationship; (b) if said prefetch path component defines a (0,1)-to-(0,1) relationship, then:(i) generating a first relational query which, when processed by the RDBMS, operates to retrieve from the RDBMS data needed to construct objects of a top-level class not pointing to objects along said prefetch path component, and which satisfy said condition list; and (ii) generating a second relational query which, when processed by the RDBMS, operates to retrieve from the RDBMS data needed to construct objects of said top-level class which point to objects along said prefetch path component, and which satisfy said condition list, said second relational query also operating to retrieve from the RDBMS data needed to construct said objects along said prefetch path component. 3. The method of claim 1 in which said object-oriented query includes a condition list, and in which said at least one prefetch path includes at least one prefetch path component, wherein step (3) comprises the steps of:(a) determining whether said prefetch path component defines a (1,1)-to-(1,1) relationship; and (b) if said prefetch path component defines a (1,1)-to-(1,1) relationship, then generating a relational query which, when processed by the RDBMS, operates to retrieve from the RDBMS data needed to construct objects of a top-level class which point to objects along said prefetch path component, and which satisfy said condition list, said relational query also operating to retrieve from the RDBMS data needed to construct said objects along said prefetch path component. 4. The method of claim 1 in which said object-oriented query includes a condition list, and in which said at least one prefetch path includes at least one prefetch path component, wherein step (3) comprises the steps of:(a) determining whether said prefetch path component defines a one-to-many relationship; (b) if said prefetch path component defines a one-to-many relationship, then:(i) generating a first relational query which, when processed by the RDBMS, operates to retrieve from the RDBMS data needed to construct objects of a top-level class that satisfy said condition list; and (ii) generating a second relational query which, when processed by the RDBMS, operates to retrieve from the RDBMS data needed to construct objects along said prefetch path component that are pointed to by said objects of said top-level class. 5. The method of claim 4 in which said top-level class maps to a top-level table, and said prefetch path component identifies a prefetch class that maps to a prefetch table, wherein step (b) further comprises the steps of:(iii) generating a first relational database command which, when processed by the RDBMS, causes the RDBMS to sort tuples retrieved by operation of said first relational query according to a foreign key in said top-level table that identifies tuples in said prefetch table; and (iv) generating a second relational database command which, when processed by the RDBMS, causes the RDBMS to sort tuples retrieved by operation of said second relational query according to a primary key of said prefetch table. 6. The method of claim 5, further comprising the step of:(5) merging said sorted tuples retrieved by operation of said first and second relational queries. 7. The method of claim 1 in which said object-oriented query includes a condition list, said at least one prefetch path includes at least one prefetch path component, said object-oriented query identifies a top-level class that maps to a top-level table, said prefetch path component identifies a prefetch class that maps to a prefetch table, and in which an intermediate table is maintained by the RDBMS that stores a top-level foreign key from said top-level table that references said prefetch table, and a prefetch foreign key from said prefetch table that references said top-level table, wherein step (3) comprises the steps of:(a) determining whether said prefetch path component defines a many-to-many relationship; (b) if said prefetch path component defines a manyto-many relationship, then:(i) generating a first relational query which, when processed by the RDBMS, operates to retrieve from the RDBMS data needed to construct objects of said top-level class that satisfy said condition list; (ii) generating a second relational query which, when processed by the RDBMS, operates to retrieve from said RDBMS said top-level foreign key and said prefetch foreign key from tuples of said intermediate table that satisfy said condition list; and (iii) generating a third relational query which, when processed by the RDBMS, operates to retrieve from the RDBMS data needed to construct objects of said prefetch class that satisfy said condition list and that are pointed to by said top-level class objects as indicated by said retrieved top-level and prefetch foreign keys. 8. The method of claim 7, wherein step (b) further comprises the steps of:(iv) generating a first relational database command which, when processed by the RDBMS, causes the RDBMS to sort tuples retrieved by operation of said first relational query according to a primary key of said top-level table; (v) generating a second relational database command which, when processed by the RDBMS, causes the RDBMS to sort tuples retrieved by operation of said second relational query according to said top-level foreign key; and (vi) generating a third relational database command which, when processed by the RDBMS, causes the RDBMS to sort tuples retrieved by operation of said third relational query according to a primary key of said prefetch table. 9. The method of claim 8, further comprising the step of:(5) merging said sorted tuples retrieved by operation of said first, second, and third relational queries. 10. The method of claim 1, wherein step (3) comprises the steps of:(a) generating a nested path representation of said at least one prefetch path; and (b) traversing said nested path representation to generate said set of relational queries. 11. The method of claim 1, wherein said at least one prefetch path specifies a class pointed to by a relationship attribute, whereby said one or more objects identified by the prefetch path correspond to said class pointed to by said relationship attribute.
12. A method of processing object-oriented queries so as to retrieve data from a non-object oriented database management system (DBMS), comprising the steps of:(1) receiving a translated object query generated from an object-oriented query having at least one prefetch path, said at least one prefetch path identifying one or more objects which are desired to be constructed, said translated object query being a relational database query capable of retrieving from said DBMS data to initialize base attributes of top-level objects identified by said object-oriented query; (2) generating from said translated object query and said at least one prefetch path a set of relational queries capable of retrieving from said DBMS data to construct said objects identified by said at least one prefetch path; and (3) causing said DBMS to process said set of relational queries. 13. A database system, comprising:a relational database management system (RDBMS); an object-relational database gateway for receiving an object-oriented query and at least one prefetch path from an object-oriented source, said at least one prefetch path identifying one or more objects which are desired to be constructed; said gateway comprising:a first query generator for translating said object-oriented query to a translated object query, said translated object query being a relational database query capable of retrieving from said RDBMS data to initialize base attributes of top-level objects identified by said object-oriented query; a second query generator for generating from said translated object query and said at least one prefetch path a set of relational queries capable of retrieving from said RDBMS data to construct said objects identified by said at least one prefetch path; and means for causing said RDBMS to process said set of relational queries. 14. The system of claim 13 in which said object-oriented query includes a condition list, and in which said at least one prefetch path includes at least one prefetch path component, wherein said second query generator comprises:means for determining whether said prefetch path component defines a (0,1)-to-(0,1) relationship; means for generating first and second relational queries when said prefetch path component defines a (0,1)-to-(0,1) relationship, wherein:(i) said first relational query, when processed by the RDBMS, operates to retrieve from the RDBMS data needed to construct objects of a top-level class not pointing to objects along said prefetch path component, and which satisfy said condition list; and (ii) said second relational query, when processed by the RDBMS, operates to retrieve from the RDBMS data needed to construct objects of said top-level class which point to objects along said prefetch path component, and which satisfy said condition list, said second relational query also operating to retrieve from the RDBMS data needed to construct said objects along said prefetch path component. 15. The system of claim 13 in which said object-oriented query includes a condition list, and in which said at least one prefetch path includes at least one prefetch path component, wherein said second query generator comprises:means for determining whether said prefetch path component defines a (1,1)-to-(1,1) relationship; and means for generating, if said prefetch path component defines a (1,1)-to-(1,1) relationship, a relational query which, when processed by the RDBMS, operates to retrieve from the RDBMS data needed to construct objects of a top-level class which point to objects along said prefetch path component, and which satisfy said condition list, said relational query also operating to retrieve from the RDBMS data needed to construct said objects along said prefetch path component. 16. The system of claim 13 in which said object-oriented query includes a condition list, and in which said at least one prefetch path includes at least one prefetch path component, wherein said second query generator comprises:means for determining whether said prefetch path component defines a one-to-many relationship; means for generating first and second relational queries when said prefetch path component defines a one-to-many relationship, wherein:(i) said first relational query, when processed by the RDBMS, operates to retrieve from the RDBMS data needed to construct objects of a top-level class that satisfy said condition list; and (ii) said second relational query, when processed by the RDBMS, operates to retrieve from the RDBMS data needed to construct objects along said prefetch path component that are pointed to by said objects of said top-level class. 17. The system of claim 16 in which said top-level class maps to a top-level table, and said prefetch path component identifies a prefetch class that maps to a prefetch table, wherein said second query generator further comprises:means for generating a first relational database command which, when processed by the RDBMS, causes the RDBMS to sort tuples retrieved by operation of said first relational query according to a foreign key in said top-level table that identifies tuples in said prefetch table; and means for generating a second relational database command which, when processed by the RDBMS, causes the RDBMS to sort tuples retrieved by operation of said second relational query according to a primary key of said prefetch table. 18. The system of claim 17, further comprising:means for merging said sorted tuples retrieved by operation of said first and second relational queries. 19. The system of claim 13 in which said object-oriented query includes a condition list, said at least one prefetch path includes at least one prefetch path component, said object-oriented query identifies a top-level class that maps to a top-level table, said prefetch path component identifies a prefetch class that maps to a prefetch table, wherein said RDBMS maintains an intermediate table that stores a top-level foreign key from said top-level table that references said prefetch table, and a prefetch foreign key from said prefetch table that references said top-level table, and wherein said second query generator comprises:means for determining whether said prefetch path component defines a many-to-many relationship; means for generating first, second, and third relational queries when said prefetch path component defines a many-to-many relationship, wherein:(i) said first relational query, when processed by the RDBMS, operates to retrieve from the RDBMS data needed to construct objects of said top-level class that satisfy said condition list; (ii) said second relational query, when processed by the RDBMS, operates to retrieve from said RDBMS said top-level foreign key and said prefetch foreign key from tuples of said intermediate table that satisfy said condition list; and (iii) said third relational query, when processed by the RDBMS, operates to retrieve from the RDBMS data needed to construct objects of said prefetch class that satisfy said condition list and that are pointed to by said top-level class objects as indicated by said retrieved top-level and prefetch foreign keys. 20. The system of claim 19, wherein said second query generator further comprises:means for generating a first relational database command which, when processed by the RDBMS, causes the RDBMS to sort tuples retrieved by operation of said first relational query according to a primary key of said top-level table; means for generating a second relational database command which, when processed by the RDBMS, causes the RDBMS to sort tuples retrieved by operation of said second relational query according to said top-level foreign key; and means for generating a third relational database command which, when processed by the RDBMS, causes the RDBMS to sort tuples retrieved by operation of said third relational query according to a primary key of said prefetch table. 21. The system of claim 20, further comprising:means for merging said sorted tuples retrieved by operation of said first, second, and third relational queries. 22. The database system of claim 13, wherein said at least one prefetch path specifies a class pointed to by a relationship, whereby said one or more objects identified by the prefetch path correspond to said class pointed to by said relationship attribute.
23. A computer system, comprising:a processor; a relational database management system (RDBMS); a controller for enabling said processor to process object-oriented queries so as to retrieve data from said RDBMS, comprising:means for enabling said processor to receive an object-oriented query and at least one prefetch path from an object-oriented source, said at least one prefetch path identifying one or more objects which are desired to be constructed; a first query generator for enabling said processor to translate said object-oriented query to a translated object query, said translated object query being a relational database query capable of retrieving from said RDBMS data to initialize base attributes of top-level objects identified by said object-oriented query; a second query generator for enabling said processor to generate from said translated object query and said at least one prefetch path a set of relational queries capable of retrieving from said RDBMS data to construct said objects identified by said at least one prefetch path; and means for enabling said processor to cause said RDBMS to process said set of relational queries. 24. The computer system of claim 23, wherein said at least one prefetch path specifies a class pointed to by a relationship, whereby said one or more objects identified by the prefetch path correspond to said class pointed to by said relationship attribute.
25. A controller, for use in a computer system comprising a processor and a relational database management system (RDBMS), for enabling the processor to process object-oriented queries so as to retrieve data from said RDBMS, comprising:means for enabling the processor to receive an object-oriented query and at least one prefetch path from an object-oriented source, said at least one prefetch path identifying one or more objects which are desired to be constructed; a first query generator for enabling the processor to translate said object-oriented query to a translated object query, said translated object query being a relational database query capable of retrieving from said RDBMS data to initialize base attributes of top-level objects identified by said object-oriented query; a second query generator for enabling the processor to generate from said translated object query and said at least one prefetch path a set of relational queries capable of retrieving from said RDBMS data to construct said objects identified by said at least one prefetch path; and means for enabling the processor to cause said RDBMS to process said set of relational queries. 26. A method of processing object-oriented queries so as to retrieve data from a relational database management system (RDBMS), comprising the steps of:(1) receiving an object-oriented query and at least one prefetch path from an object-oriented source, said at least one prefetch path identifying one or more objects which are desired to be constructed; (2) translating said object-oriented query to a translated object query, said translated object query being a relational database query capable of retrieving data from said RDBMS; and (3) generating from said translated object query and said at least one prefetch path a set of relational queries capable of retrieving from said RDBMS data to construct said objects identified by said at least one prefetch path. 27. The method of claim 26 further comprising the step of:(4) causing said RDBMS to process said set of relational queries. 28. The method of claim 26, wherein said translated object query retrieves data from said RDBMS data to initialize base attributes of top-level objects identified by said object-oriented query.
This application is a continuation of application Ser. No. 08/366,238, filed Dec. 29, 1994, now abandoned.
U.S. patent application entitled "System and Method for Efficiently Translating Relational Tuples to Object-Oriented Objects", Ser. No. 08/366,541, incorporated herein by reference in its entirety.
The present invention relates generally to databases, and more particularly to generating relational database queries to retrieve data from a relational database in accordance with an object-oriented database query and an associated set of prefetch paths.
A great amount of data is currently stored in existing relational database management systems (RDBMS), such as DB2 produced by International Business Machines (IBM) Corporation, Oracle produced by Oracle Corp., and Sybase produced by Sybase Inc. It would be desirable if applications operating in object-oriented computing environments could access in an object-oriented manner data in relational database management systems.
There are many problems that must be overcome before such object-oriented access to relational database management systems can be allowed. These problems stem from the fact that data is stored in a relational database according to a relational database schema, whereas (as described above) data is stored in an object-oriented database according to an object-oriented database schema. (The relational database schema specifies the tables in the relational database, the number of columns in each table, the nature of such columns, etc.)
Thus, what is required is a system and method for enabling an object-oriented application to access data in a relational database management system in an object-oriented manner.
Briefly stated, the present invention is directed to a system and method for processing object-oriented queries so as to retrieve data from a relational database management system (RDBMS). According to the present invention, an object-oriented query and zero or more prefetch paths are received from an object-oriented source (such as an application or user). The prefetch paths identify one or more objects to be prefetched in addition to the objects that are fetched as a result of executing the object-oriented query. The object-oriented query is translated to a translated object query, where the translated object query is a relational database query capable of retrieving from the RDBMS data to initialize base attributes of top-level objects identified by the object-oriented query. A set of relational queries is generated from the translated object query and the prefetch path. These relational queries, which are capable of retrieving from the RDBMS data needed to construct the objects identified by the prefetch path, are processed by the RDBMS.
FIGS. 5-7, 14-17, 18A, and 18B are flowcharts depicting the operation of the present invention;
FIGS. 8-10 and 19 depict ways in which relational queries can be generated from prefetch path components; and
FIGS. 11-13 illustrate preferred rules for generating relational queries from prefetch path components.
More particularly, the application 104 generates and transfers object-oriented database queries (also called object queries herein) and an (optional) set of prefetch paths associated with the object queries to the gateway 106. The gateway 106 analyzes the object queries and their prefetch paths (if any) and generates, for each object query and its set of prefetch paths, a set of relational database queries (also called relational queries herein). These relational queries are capable of retrieving from the RDBMS 112 the information indicated by the object query (and also indicated by prefetch paths, as discussed below).
The application 104, gateway 106, schema mapping module 108 (described below), object-oriented DBMS 110, and RDBMS 112 preferably represent computer programs which reside (during run-time) in the main memory 208, and which are executed by the processors in the computer system 202, such as processor 204. (The data maintained by the object-oriented DBMS 110 and the RDBMS 112 may be stored in the main memory 208 and/or the secondary memory 210. Also, the computer programs associated with the application 104, gateway 106, schema mapping module 108, object-oriented DBMS 110, and RDBMS 112 may be stored in a floppy disk 218 or some other removable storage medium, which is read by the floppy drive 214). The computer system 202 may also be connected to a network. In this case, data may be retrieved from relational tables stored in storage devices in communication with the computer system 202 via the network.
The gateway 106 and the schema mapping module 118, when executed, enable the computer system 202 to perform the features of the present invention as discussed herein. Thus, the gateway 106 and the schema mapping module 118 represent controllers of the computer system 202.
According to the present invention, the application 104 is enabled to access the RDBMS 112 in an object-oriented manner. In other words, the application 104 works using only an object-oriented view of the relational database schema. All operations initiated by the application 104 which involve the RDBMS 112 are in the object-oriented database schema. However, since the RDBMS 112 stores data according to a relational database schema, there needs to be a mechanism by which the relational data (from the RDBMS 112) is mapped into an equivalent object-oriented schema. In the present invention, this mechanism is represented by the schema mapping module 108.
The schema mapping module 108 maps the relational database schema of the RDBMS 112 into the object-oriented schema associated with the object-oriented DBMS 110. The schema mapping module 108 preferably represents a schema mapping object that is stored persistently and that can be used to access relational data using the object-oriented schema.
Schema mapping is a well known process. Accordingly, the discussion below focuses on particular characteristics of the schema mapping module 108 which are required to enable operation of the gateway 106. Implementation of the schema mapping module 108 as described herein will be apparent to persons skilled in the relevant art.
According to the present invention, the schema mapping module 108 can be accessed and queried (by the gateway 106, for example) . The schema mapping module 108 can be queried for the following information:
(b) The foreign key or list of foreign keys (in intermediate tables) in this corresponding relational table that defines the relationship provided to the schema mapping module 108. A foreign key is a value in the corresponding relational table that maps to a non-base attribute in the class. Thus, in table employee of FIG. 3, mgrid and did are foreign keys. If Emp.department is passed to the schema mapping module 108, then the schema mapping module 108 returns "did," which is the foreign key that maps to "department" in the class Emp.
This represents a one-to-one relationship, since each person (presumably) has a single spouse. Thus, if Emp.spouse is passed to the schema mapping module 108, the schema mapping module 108 would return an arity of "one-to-one". Now assume that Emp.department is passed to the schema mapping module 108. Each employee has a single department, but each department may contain many employees. This relationship is represented in the class Dept by the set "emp-- set" of pointers to Emp objects ("did" is also the foreign key for emp-- set). Thus, this represents a "many-to-one " relationship (or, equivalently, a "one-to-many" relationship). Accordingly, the schema mapping module 108 would return an arity of "many-to-one".
Object-Relational Database Gateway
FIG. 4 is a block diagram of the gateway 106 according to one embodiment of the present invention. According to this embodiment, the gateway 106 includes a first query generator 402 and a second query generator 404. The first and second query generators 402 and 404 collectively operate to generate a set of relational queries from an object query provided by the application 104 (and from prefetch paths, as discussed below) . These relational queries are capable of retrieving from the RDBMS 112 the information indicated by the object query (and also indicated by the prefetch paths).
The first query generator 402 analyzes the object query (issued by the application 104) and generates a relational query that is capable of retrieving from the RDBMS 112 all of the base attributes for the top-level object(s). The top-level objects are defined as the objects which can be constructed using the data that is retrieved from the relational database as a result of executing the object query. In other words, the top-level objects are explicitly identified by the object query. If prefetch paths are specified, additional "prefetch" objects will be retrieved that are related to the top-level objects. The prefetch paths identify these additional prefetch objects. If no prefetch paths are specified, only top-level objects will be retrieved. For example, consider the following example object query (all object queries shown herein are based on the well known ObjectStore Query Language, described in Orenstein et al., "Query Processing in the ObjectStore Database System", Proceedings of the ACM SIGMOD Conference, San Diego, Calif., 403-412, Jun. 1992, incorporated herein by reference).
Employees : salary>20000:!
This query, which is based on the example classes and tables shown in FIG. 3, operates to retrieve all objects (these are the top-level objects) of class Emp where the salary base attribute is greater than 20,000. The first query generator 402 generates the following relational query from the above object query:
Note that this relational query operates to retrieve from the RDBMS 112 only the base attributes (i.e., name, eid, birthdate, and salary) for only the top level object. This relational query does not retrieve any information needed to initialize the non-base attributes (such as manager or department) . Also, this relational query does not retrieve any attributes (base or otherwise) from any objects other than the top level object. Non-top level objects include, for example, the objects pointed to by the manager and department pointers.
The first query generator 402 generates the above relational query by querying the schema mapping module 108 to determine which table or view is mapped to the class Emp, and to determine which columns of this table map to the base attributes of the class Emp. The relational query is generated directly from this information.
As is well known, in an object database, it is possible to access other objects from a given object using pointers to the other objects stored as part of the given object. Dereferencing such pointers (that is, setting the values of such non-based "pointer" attributes in the given object when data for the object is read from a database and the given object is initialized) enables access to both base and relationship attributes of the pointed-to objects. The translated object query (generated by the first query generator 402) is capable of retrieving the information needed to construct the base attributes of the given object (the top-level object). More work is needed, however, to initialize other objects pointed to by the relationship attributes in the top-level object.
One way to prefetch objects is to recursively retrieve all objects pointed to by objects that are the result of the top level query. (As used herein, the term "prefetching" refers to the operation of retrieving data from the RDBMS 112, in response to an object query, for the purpose of initializing objects related to objects that form the result of the object query.) This would almost certainly result in major performance problems by fetching too many objects that are not needed by the application.
A second alternative is to not fetch any object except the top-level objects but initialize the pointers using some special values. Dereferencing such special pointers will lead to an interrupt that can be trapped and the object pointed-to can be retrieved at that time. This second solution is called "object faulting" and can also cause performance problems since dereferencing every pointed-to object will cause an SQL query to be generated and executed to retrieve one object. This will also most likely result in low performance.
In the present invention, a third approach is preferably used to prefetch data. According to this third approach, the application 104 (or user) is required to provide zero or more prefetch paths with the object query. If a prefetch path is not provided, then only the base attributes of the top-level objects are initialized. If additional objects need to be prefetched and initialized, then the user must explicitly specify the paths (starting from the top-level objects) leading to those objects. Only the objects along these paths (called the prefetch paths) are fetched and initialized. Other relationship attributes that are not along the specified prefetch paths will have invalid pointers.
Prefetch paths are passed by the user as strings along with the original object query. The first query generator 402 transfers the translated object query as well as the prefetch paths to the second query generator 404. The second query generator 404 uses the translated object query and the prefetch path (as well as information obtained from the schema mapping module 108) to generate relational queries that are capable of retrieving from the RDBMS 112 all data needed to initialized the objects and the attributes indicated by the prefetch paths.
1. Top Level Class: This parameter provides the name of the class being queried. Any information on this class can be obtained by accessing the schema mapping module 108.
The operation of the present invention shall now be described in greater detail with reference to a flowchart 502 shown in FIG. 5. Flowchart 502 represents the operation of the gateway 106 while processing an object query issued by the application 104. As discussed above, the application 104 sends zero or more prefetch paths along with the object query to the gateway 106. The flowchart 502 begins with step 504, where control immediately passes to step 506.
In step 506, the gateway 106 receives the object query (also called the original object query) and the prefetch paths, if any, from the application 104.
In step 508, the gateway 106 analyzes the object query and determines whether the object query is intended to access data in the object-oriented DBMS 110 only, or whether the object query is intended to access data in the RDBMS 112. The gateway 106 may do this, for example, by providing the class being queried to the schema mapping module 108. If the schema mapping module 108 returns information identifying a corresponding table, then the gateway 106 concludes that the object query is intended to access data in the RDBMS 112. Otherwise, the gateway 106 concludes that the object query is intended to access data only in the object DBMS 110. The gateway 106 can alternatively perform step 508 by requiring the application 104 (or the user) to call a special query module that is restricted to executing object queries on only relational DBMS data. All classes that are part of such an object query are assumed to be mapped to relational database data and if that is not the case an error is generated.
If the gateway 106 concludes that the object query is intended to access data only in the object DBMS 110, then step 510 is performed. In step 510, the gateway 106 passes the object query to the object DBMS 110. The object DBMS 110 processes the object query in a well known manner. Flowchart 502 is complete after step 510 is performed, as indicated by step 518.
If, in step 508, the gateway 106 concludes instead that the object query is intended to access data in the RDBMS 112, then step 512 is performed. In step 512, the first query generator 402 generates a translated object query from the original object query. The translated object query is capable of retrieving from the RDBMS 112 the information needed to construct the base attributes of the top-level object. The manner in which the first query generator 402 generates the translated object query is discussed above. The first query generator 402 passes the translated object query and the prefetch path(s), if any, to the second query generator 404.
In step 514, the second query generator 404 translates the prefetch paths (if any), which are in object-oriented form, to a nested representation of prefetch paths, still in object-oriented from. The second query generator 404 then analyzes the translated object query and the nested representation of prefetch path(s) and generates a set of relational queries for accessing the RDBMS 112. These relational queries are capable of retrieving from the RDBMS 112 information needed to construct objects specified in the prefetch path(s). The manner in which the second query generator 404 generates this set of relational queries is discussed below.
In step 516, the second query generator 404 passes the relational queries (generated in step 514) to the RDBMS 112. The RDBMS 112 processes the relational queries in a well known manner, and returns to the second query generator 404 the data that was retrieved by operation of the relational queries. The second query generator 404 (or some other component of the gateway 106) then merges the data, as needed. The merging operation is discussed below. This retrieved (and possibly merged) data is sufficient to enable the gateway 106 to construct the top-level object, and the other objects identified by the prefetch path(s), if any. The manner in which the second query generator 404 constructs these objects in accordance with this retrieved data is described in the above-referenced U.S. patent application entitled "System and Method for Efficiently Translating Relational Tuples to Object-Oriented Objects", Attorney Docket No. ST8-94-0051/1252.1720000, incorporated herein by reference in its entirety.
It is noted that, if no prefetch paths were passed to the second query generator 404, then in step 514 the second query generator 404 simply passes the translated object query to the RDBMS 112. In step 516, the RDBMS 112 processes the translated object query and transfers the retrieved data to the second query generator 404. The gateway 106 then uses this data to construct the top-level objects.
Flowchart 502 is complete after step 516 is performed, as indicated by step 518.
Second Query Generator
As discussed above, in step 514 the second query generator 404 uses the translated object query and the prefetch paths to produce a set of one or more relational queries that will fetch from the RDBMS 112 the relevant data needed to construct objects in the prefetch paths (in addition to the top-level objects). In practice, the process of generating these relational queries is driven by various factors like the availability of the outer join operator, the possibility of translating prefetch paths to a natural join as opposed to the default left outer join, and the types of relationships (one-to-one, one-to-many, many-to-many) that are implied along the prefetch paths.
The manner in which the second query generator 404 generates these relational queries from the translated object query and the prefetch paths shall now be described with reference to flowchart 602 shown in FIG. 6. (It is assumed in this discussion that one or more prefetch paths exist. The operation of the second query generator 404 when the application 104 or user did not transfer any prefetch paths to the first query generator 402 (in step 506, FIG. 5) is described above.) Flowchart 602 begins with step 604, where control immediately passes to step 606.
In step 606, the second query generator 404 analyzes the prefetch paths and collapses them into a recursive representation (called the nested prefetch structure or nested prefetch path representation) that eliminates duplicates and nests them such that each component in each prefetch path only appears once. The root of this nested prefetch structure is the top level class. By generating the nested prefetch structure, the operation of the second query generator 404 in step 608 is facilitated.
department, { proj-- set, { }!, emp-- set, { }!}!
The manner in which the second query generator 404 performs step 606 is as follows. The nested path representation of a prefetch path has two attributes, namely, the attribute or class where the path starts and a set of sub-- paths that are within it. All nested paths for a set of prefetch paths start from the top-level class. The algorithm to create a nested path representation for a set of prefetch paths is as follows:
1. A nested path object, path-- root, is created to represent the nested-path representation for all of the paths rooted at the class of the root-level objects. The class attribute of path-- root is set to be the name of the top-level class. The sub-- paths set of the path-- root is initialized to the empty set.
2. For each prefetch path starting from the top-level class, do steps 3 and 4.
Step 3. Set current-- path to be the path-- root. Set current-- step to be the first step in the current prefetch path (e.g., the prefetch path department.emp-- set has two steps, the first being "department" and the second being "emp-- set".).
Step 4. If a nested path exists in the sub-- paths set of the current-- path whose attribute value matches the current-- step, then do step 4a, otherwise do step 4b.
Step 4a . Set the current-- path to the matching nested path. If current-- step is the last step, then proceed to step 2 and process the next prefetch path. Otherwise, set current-- step to be the next step in the prefetch path, and repeat step 4.
Step 4b . Create a new nested path whose attribute value matches the current-- step. Add this new nested path to the sub-- paths set of the current-- path. Set the current-- path to the new nested path. If current-- step is the last step, then proceed to step 2 and process the next prefetch path. Otherwise, set current-- step to be the last step in the prefetch path, and repeat step 4.
The path-- root contains the nested prefetch representation at the end of the above algorithm.
In step 608, the second query generator 404 traverses the nested prefetch structure and generates the relational queries using schema mapping information obtained by appropriately querying the schema mapping module 108. In order to generate these relational queries, it is necessary to follow a number of rules (developed by the inventor). Which rule is followed depends on whether the prefetch paths contain one-to-one, one-to-many, or many-to-many relationships. The operation of the second query generator 404 while performing step 608 is described in the following section.
Generatinq Relational Queries from the Prefetch Path(s) (Step 608 of FIG. 6)
According to the present invention, the second query generator 404 translates each component of each prefetch path into one or more relational queries. The inventor has recognized that each component of each prefetch path can be evaluated using a well known left outer join operation (also called left join or outer join). Thus, the relational queries for each component of each prefetch path can be cascaded with all of the conditions and join terms on all queries to the left of the prefetch path component. In some cases, it is possible to combine the queries to create a more efficient set of relational queries. The manner in which these relational queries are generated shall be described by first considering a few examples.
FIG. 8 specifies an example schema mapping, an object query, and a prefetch path on the schema. In this case, there is a condition Dept :count>1000:! as well as a prefetch path on Emp.Dept. Since the path Emp.Dept occurs both in a condition as well as the prefetch path, it is clear that every Emp object that is the result of the query will necessarily have an associated Dept object.
We can therefore generate the relational query (which is equivalent to the object query) using a well known natural join (in other words, it is possible to avoid using a left join operation). The first query plan shown in FIG. 8 is the solution, and is also the optimal solution, if the Emp.Dept relationship is (1,1)--(1,1), that is, each Emp object is associated with one Dept object. The notation (m,n) is well known in the relevant art and indicates that there must be a minimum of m and a maximum of n. According to this first query plan, the values in columns eid, ename, did, and dname are retrieved from tables Employee E and Department D for those rows in these tables where E.salary is greater than 10, D.count is greater than 1000, and E.deptid is the same as D.did. (It is noted that the query plans discussed herein are presented using the well known SQL syntax. Thus, the meaning and operation of these query plans will be apparent to persons skilled in the relevant art.)
However, if there are multiple Emp objects associated with a Dept object (one-to-many), the first query plan of FIG. 8 will retrieve the same Dept data many times from the RDBMS 112. This is inefficient. In the case of one-to-many relationships, therefore, it is better (in most cases) to perform two queries on the RDBMS 112, a first which retrieves the tuples corresponding to the Emp objects, and a second which retrieves the tuples corresponding to the Dept objects that relate to the Emp objects chosen. This is indicated by the second query plan of FIG. 8.
Note that the first and second queries retrieve the primary key of Department (D.did) . These two streams are sorted by the join attribute (D.did) using the well known ORDER BY operation and the final merge is done in the gateway 106. This merge, which operates to match Employee tuple data with corresponding department tuple data (i.e., a particular person's department information is merged with the person's employee information), is facilitated since both streams have been sorted by D.did. Note that, with this second query plan shown in FIG. 8, it is still possible to avoid the use of a left join since, in this example, the condition Dept :count>1000:! and the prefetch path are both on Emp.Dept.
Let us now consider a case where a left join cannot be avoided. An example is given in FIG. 9. In this example, unlike in the earlier case of FIG. 8, we cannot convert the left join to a natural join, because a natural join will only retrieve Employee tuples that have an associated Department tuple. However, the answer to the object query in FIG. 9 (i.e., Emp :salary>10:!) could include Employee objects that do not have any associated Department objects. Therefore, a left outer join must be used here.
It is assumed that left join support is not available in the RDBMS. Furthermore, even if left join support is available in the RDBMS, executing the left join directly will result in duplicate data retrieval for one-to-many and many-to-many relationships and hence is not desirable to use it in those cases. So, the only case where a native left join may be used is the one-to-one case. In other cases, it is necessary to represent the object query using two relational, non-left join queries. Two possible query plans, each comprising two queries, are shown in FIG. 9. In both the first and second query plans of FIG. 9, each Employee tuple is retrieved exactly once. While each Department tuple is retrieved exactly once in the second query plan of FIG. 9, this is not the case in the first query plan of FIG. 9 if the Emp.Dept relationship is one-to-many. Therefore, the first query plan is suitable if the Emp.Dept is a one-to-one relationship and the second query plan is suitable if Emp.Dept is a one-to-many relationship. Note that in the second plan, the final merge to find the related Employee and Department tuples is done in the gateway 106.
The query plans used in the previous examples (FIGS. 8 and 9) can be used for many-to-many relationships also, but they might be inefficient since they could retrieve the same tuple multiple times. An example of a many-to-many relationship and more optimal query plans are given in FIG. 10. In the case of a many-to-many relationship, an intermediate table is involved in the join. In this example, two query plans are shown. The first plan shows the simplest way to do the left join and is likely to be inefficient for the many-to-many relationship case discussed here since it could get the same Employee and Project tuples multiple times. The second query plan contains three queries and is very efficient in terms of data retrieval even though it results in two merges and also a sort of the intermediate tables's tuples in the gateway 106.
Keeping in mind the tradeoffs discussed above, the inventor has developed a set of rules for generating query plans for various types of relationships. As should be clear from the discussion above, these query plans represent different ways that the second query generator 404 generates the set of relational queries for a prefetch path component. In this embodiment of the invention, the query plans were developed according to the following principle: choose the most efficient query plan from among those that will retrieve each copy of a tuple at most once. Other rules could alternatively have been developed if other principles/goals were employed. The development of such other rules in light of such other principles/goals will be apparent to persons skilled in the relevant art based on the discussion contained herein.
The inventor has defined three rules for one-to-one relationships (given in FIG. 11), and one rule each for one-to-many (given in FIG. 12) and many-to-many (given in FIG. 13) relationships. These rules have been optimized in such a way that the minimum number of tuples are retrieved from the RDBMS 112. Also, the query plans chosen would have been different if the inventor had decided to minimize the number of relational queries rather than minimizing duplicate data retrieval.
The nature of these rules, and the manner in which these rules are applied by the second query generator 404, shall now be described with reference to a flowchart 702 contained in FIG. 7. This flowchart 702 represents the manner in which the second query generator 404 translates a prefetch path component into one or more relational queries. In other words, flowchart 702 represents the manner in which the second query generator 404 performs step 608 of FIG. 6 (for one prefetch path component). Flowchart 702 begins with step 704, where control immediately passes to step 706.
In step 706, the second query generator 404 determines whether the relationship defined by the prefetch path component is a (0,1)-to-(0,1) relationship. The second query generator 404 does this by querying the schema mapping module 108 to obtain arity information. Given the prefetch path information, the schema mapping module 108 has the ability to provide information regarding foreign keys associated with a relationship as well as information on whether the type of a prefetch component is a single pointer or a set of pointers. The arity can be inferred by looking at the foreign key and type information for the prefetch component.
If the second query generator 404 determines that the prefetch path component defines a (0,1)-to-(0,1) relationship, then step 708 is performed.
In step 708, the second query generator 404 determines whether referential integrity is enforced. Referential integrity is defined as the mechanism by which a DBMS system maintains integrity of the relationships between foreign keys and primary keys, i.e., no dangling references are allowed to exist. All foreign keys will therefore point to valid primary keys if referential integrity is automatically maintained by the system. The second query generator 404 performs step 708 by appropriately querying the schema mapping module 108. If the second query generator 404 determines that referential integrity is enforced, then step 710 is performed.
In step 710, the second query generator 404 generates relational queries corresponding to the prefetch path component according to a Rule 1a. The form of the resulting relational queries for a given object query, a prefetch path, a relational schema, and an object schema is shown in FIG. 11. As indicated by FIG. 11, the second query generator 404 generates a first relational query and a second relational query according to Rule 1a (the second query is shown as being below the first query). The first query operates to retrieve from the RDBMS 112 data to construct objects of the top-level class which are not related to (i.e., which do not point to) objects along the prefetch path, and which satisfy the conditions present in the original object query. The second query operates to retrieve from the RDBMS 112 data to construct objects of the top-level class which are related to (i.e., which point to) objects along the prefetch path, and which satisfy the conditions present in the original object query. The second query also operates to retrieve from the RDBMS 112 data to construct these objects along the prefetch path.
The manner in which the second query generator 404 generates relational queries in accordance with Rule 1a shall now be described with reference to a flowchart 1402 in FIG. 14. Flowchart 1402 begins with step 1404, where control immediately passes to step 1406.
In step 1406, the second query generator 404 queries the schema mapping module 108 to identify the table in the RE)BMS 112 that maps to the queried class (also called the top-level class). For reference purposes, this is called the top-level table. In the example of FIG. 11, the queried class is "X", and the corresponding, top-level table is Xr. Also in step 1406, the second query generator 404 queries the schema mapping module 108 to identify the columns of the top-level table which map to the base attributes in the queried class. Further in step 1406, the second query generator 404 generates the "select" statement of the first query such that this "select" statement lists the columns of the top-level table which map to the base attributes in the queried class.
In step 1408, the second query generator 404 generates the "from" statement of the first query so that this "from" statement references the top-level table.
In step 1410, the second query generator 404 generates the "where" statement of the first query so that this "where" statement operates to retrieve tuples of the top-level table where (1) the condition list (as specified in the translated object query) are satisfied; and (2) the foreign key in the top-level table associated with the table indicated by the prefetch path component is null. In the example of FIG. 11, class Y lies along the prefetch path component "X.Y". Class Y maps to table Yr. Thus, table Yr is indicated by the prefetch path component X.Y. The top-level table, Xr, includes a foreign key Yfk which is associated with table Yr. Thus, this second condition specifies that tuples having Yfk equal to null are retrieved from table Xr (subject to the first condition).
For reference purposes, the class that lies along the prefetch path (i.e., class Y in the example of FIG. 11) is called the prefetch class. The table that maps to the prefetch class (i.e., class Yr in the example of FIG. 11) is called the prefetch table.
In step 1412, the second query generator 404 generates the "select" statement for the second query such that this "select" statement lists the columns of the top-level table which map to the base attributes in the queried class, and also lists the columns of the prefetch table which map to the base attributes in the prefetch class. The second query generator 404 may query the schema mapping module 108 to obtain schema mapping information to perform step 1412.
In step 1414, the second query generator 404 generates the "from" statement of the second query so that this "from" statement references the top-level table and the prefetch table.
In step 1416, the second query generator 404 generates the "where" statement of the second query so that this "where" statement operates to retrieve tuples of the top-level table and the prefetch table where (1) the condition list (as specified in the translated object query) are satisfied; and (2) the pertinent foreign key in the top-level table is equal to the primary key in the pref etch table. The "pertinent foreign key" is the foreign key that is associated with the prefetch table. Thus, in the example of FIG. 11, this pertinent foreign key is equal to Yfk. The primary key in the prefetch table Yr is assumed to be y1. Thus, this second condition specifies that tuples having Yfk equal to y1 are retrieved from tables Xr and Yr (subject to the first condition).
Flowchart 1402 is complete after step 1416 is performed, as indicated by step 1418.
Referring again to FIG. 7, if in step 708 the second query generator 404 determined that referential integrity is not enforced, then step 712 is performed. In step 712, the second query generator 404 generates relational queries corresponding to the prefetch path component according to a Rule 1b. The form of the resulting relational queries for a given object query, a prefetch path, a relational schema, and an object schema is shown in FIG. 11. An example of Rule 1b is discussed above as the first query plan in FIG. 9. As indicated by FIG. 11, the second query generator 404 generates a first relational query and a second relational query according to Rule 1b (the second query is shown as being below the first query). The first query operates to retrieve from the RDBMS 112 data to construct objects of the top-level class which are not related to (i.e., which do not point to) objects along the prefetch path, and which satisfy the conditions contained in the original object query. The second query operates to retrieve from the RDBMS 112 data to construct objects of the top-level class which are related to (i.e., which point to) objects along the prefetch path, and which satisfy the conditions contained in the original object query. The second query also operates to retrieve from the RDBMS 112 data to construct these objects along the prefetch path.
The manner in which the second query generator 404 generates relational queries in accordance with Rule 1b shall now be described with reference to a flowchart 1502 in FIG. 15. Flowchart 1502 begins with step 1504, where control immediately passes to step 1506.
In step 1506, the second query generator 404 generates the "select" statement of the first query such that this "select" statement lists the columns of the top-level table which map to the base attributes in the queried class. The second query generator 404 may query the schema mapping module 108 to obtain schema mapping information to perform step 1506. The performance of step 1506 is similar to the performance of step 1406, described above.
In step 1508, the second query generator 404 generates the "from" statement of the first query so that this "from" statement references the top-level table. The performance of step 1508 is similar to the performance of step 1408, described above.
In step 1510, the second query generator 404 generates the "where" statement of the first query so that this "where" statement operates to retrieve tuples of the top-level table where (1) the condition list (as specified in the translated object query) are satisfied; and (2) the foreign key in the top-level table associated with the prefetch table is not equal to the primary key in the prefetch table. The prefetch table is Yr, and Yfk is the foreign key in the top-level table Xr which is associated with this prefetch table Yr. It is assumed that the primary key in the prefetch table Yr is y1. Thus, this second condition specifies that tuples having Yfk not equal to any y1 are retrieved from table Xr (subject to the first condition).
In step 1512, the second query generator 404 generates the "select" statement for the second query such that this "select" statement lists the columns of the top-level table which map to the base attributes in the queried class, and also lists the columns of the prefetch table which map to the base attributes in the prefetch class. The second query generator 404 may query the schema mapping module 108 to obtain schema mapping information to perform step 1512.
In step 1514, the second query generator 404 generates the "from" statement of the second query so that this "from" statement references the top-level table and the prefetch table.
In step 1516, the second query generator 404 generates the "where" statement of the second query so that this "where" statement operates to retrieve tuples of the top-level table and the prefetch table where (1) the condition list (as specified in the translated object query) are satisfied; and (2) the pertinent foreign key in the top-level table is equal to the primary key in the prefetch table. The "pertinent foreign key" is the foreign key that is associated with the prefetch table. Thus, in the example of FIG. 11, this pertinent foreign key is equal to Yfk. The primary key in the prefetch table Yr is assumed to be y1. Thus, this second condition specifies that tuples having Yfk equal to y1 are retrieved from tables Xr and Yr (subject to the first condition).
Flowchart 1502 is complete after step 1516 is performed, as indicated by step 1518.
Referring again to FIG. 7, if in step 706 the second query generator 404 determines that the relationship defined by the prefetch path component is not a (0,1)-to-(0,1) relationship, then step 714 is performed. In step 714, the second query generator 404 determines whether the relationship defined by the prefetch path component is a (1,1)-to-(1,1) relationship. The operation of step 714 is similar to the operation of step 706. If the second query generator 404 determines that the prefetch path component defines a (1,1)-to-(1,1) relationship, then step 716 is performed.
In step 716, the second query generator 404 generates relational queries corresponding to the prefetch path component according to a Rule 1c. The form of the resulting relational queries for a given object query, a prefetch path, a relational schema, and an object schema is shown in FIG. 11. An example of Rule 1c is presented in FIG. 8 as the first query plan. As indicated by FIG. 11, the second query generator 404 generates a single relational query according to Rule 1c. This query operates to retrieve from the RDBMS 112 data to construct objects of the top-level class which point to objects along the prefetch path, and to construct these objects along the prefetch path.
The manner in which the second query generator 404 generates relational queries in accordance with Rule 1c shall now be described with reference to a flowchart 1602 in FIG. 16. Flowchart 1602 begins with step 1604, where control immediately passes to step 1606.
In step 1606, the second query generator 404 generates the "select" statement of the query such that this "select" statement lists the columns of the top-level table which map to the base attributes in the queried class, and the columns of the prefetch table which map to the base attributes of the prefetch class. The second query generator 404 may query the schema mapping module 108 to obtain schema mapping information to perform step 1606.
In step 1608, the second query generator 404 generates the "from" statement of the query so that this "from" statement references the top-level table and the prefetch table.
In step 1610, the second query generator 404 generates the "where" statement of the query so that this "where" statement operates to retrieve tuples of the top-level table and the prefetch table where (1) the condition list (as specified in the translated object query) are satisfied; and (2) the pertinent foreign key in the top-level table is equal to the primary key in the prefetch table. The "pertinent foreign key" is the foreign key that is associated with the prefetch table. Thus, in the example of FIG. 11, this pertinent foreign key is equal to Yfk. The primary key in the prefetch table Yr is assumed to be y1. Thus, this second condition specifies that tuples having Yfk equal to yl are retrieved from tables Xr and Yr (subject to the first condition).
Flowchart 1602 is complete after step 1610 is performed, as indicated by step 1612.
Referring again to FIG. 7, if in step 714 the second query generator 404 determines that the relationship defined by the prefetch path component is not a (1,1)-to-(1,1) relationship, then step 718 is performed. In step 718, the second query generator 404 determines whether the relationship defined by the prefetch path component is a one-to-many relationship. The operation of step 718 is similar to the operation of steps 706 and 714. If the second query generator 404 determines that the prefetch path component defines a one-to-many relationship, then step 720 is performed.
In step 720, the second query generator 404 generates relational queries corresponding to the prefetch path component according to a Rule 2. The form of the resulting relational queries for a given object query, a prefetch path, a relational schema, and an object schema is shown in FIG. 12. An example of Rule 2 is presented in FIG. 9 as the second query plan.
As indicated by FIG. 12, the second query generator 404 generates a first relational query and a second relational query according to Rule 2 (the second query is shown as being below the first query). The first query operates to retrieve from the RDBMS 112 data to construct objects of the top-level class that satisfy the conditions present in the original object query. The tuples that are retrieved by the first query are sorted according to the foreign key in the top-level table that is related to (i.e., that identifies tuples in) the prefetch table. The second query operates to retrieve from the RDBMS 112 data to construct objects that are along the prefetch path and that are related to (i.e., pointed to by) the top-level objects obtained by the first query. The tuples that are retrieved by the second query are sorted according to the primary key of the prefetch table. The gateway 106 merges the tuples retrieved by the first and second queries.
The manner in which the second query generator 404 generates relational queries in accordance with Rule 2 shall now be described with reference to a flowchart 1702 in FIG. 17. Flowchart 1702 begins with step 1704, where control immediately passes to step 1706.
In step 1706, the second query generator 404 generates the "select" statement of the first query such that this "select" statement lists the columns of the top-level table which map to the base attributes in the queried class, and also lists the foreign key in the top-level table associated with the prefetch table. The second query generator 404 queries the schema mapping module 108 to obtain schema mapping information to perform step 1706.
In step 1708, the second query generator 404 generates the "from" statement of the first query so that this "from" statement references the top-level table.
In step 1710, the second query generator 404 generates the "where" statement of the first query so that this "where" statement operates to retrieve tuples of the top-level table where the conditions related to the queried class (and specified in the translated object query) are satisfied.
In step 1712, the second query generator 404 generates an "order by" statement to order the tuples retrieved from the top-level table by the foreign key described above (with respect to step 1706).
In step 1714, the second query generator 404 generates the "select" statement for the second query such that this "select" statement lists the columns of the prefetch table which map to the base attributes in the prefetch class. The second query generator 404 may query the schema mapping module 108 to obtain schema mapping information to perform step 1714.
In step 1716, the second query generator 404 generates the "from" statement of the second query so that this "from" statement references the top-level table and the prefetch table.
In step 1718, the second query generator 404 generates the "where" statement of the second query so that this "where" statement operates to retrieve tuples of the prefetch table where (1) the condition list (as specified in the translated object query) are satisfied; and (2) the pertinent foreign key in the top-level table is equal to the primary key in the prefetch table. The "pertinent foreign key" is the foreign key that is associated with the prefetch table. Thus, in the example of FIG. 12, this pertinent foreign key is equal to Yfk. The primary key in the prefetch table Yr is assumed to be y1. Thus, this second condition specifies that tuples having Yfk equal to y1 are retrieved from table Yr (subject to the first condition).
In step 1720, the second query generator 404 generates an "order by" statement to order the tuples retrieved from the prefetch table by the primary key of the prefetch table.
Flowchart 1702 is complete after step 1720 is performed, as indicated by step 1722.
Note that the flowchart 1702 is for the case when the foreign key is present in the top-level table and points to the prefetch table. In the case where the foreign key is present in the direction opposite to the prefetch path (i.e., from the prefetch table to the top-level table even though the prefetch hint is always from the top-level class to the prefetch class) , the flowchart 1702 has to be modified in the following way: The foreign key will be fetched in the query generated for the prefetch table and not in the query for the top-level table as described above in step 1706. Also, step 1712 will need to order the top-level table's tuples by their primary key. In step 1718, the additional join (i.e., condition (2)) is changed to be as follows: "foreign key in table corresponding to prefetch class is equal to primary key corresponding to queried (or top-level) class". Finally, step 1720 should be changed to order the tuples of the prefetch table by the foreign key. The merging will be done using the primary key in the top-level table with the foreign key in the prefetch table. Note that the above applies for both 1-to 1 and 1-to-many cases but not for the many-to-many case.
Referring again to FIG. 7, if in step 718 the second query generator 404 determines that the prefetch path component does not define a one-to-many relationship, then the second query generator 404 concludes that the prefetch path component defines a many-to-many relationship. In this case, step 722 is performed.
In step 722, the second query generator 404 generates relational queries corresponding to the prefetch path component according to a Rule 3. The form of the resulting relational queries for a given object query, a prefetch path, a relational schema, and an object schema is shown in FIG. 13. An example of Rule 3 is presented in FIG. 10.
As indicated by FIG. 13, the second query generator 404 generates a first relational query, a second relational query, and a third relational query according to Rule 3 (the second query is shown as being below the first query, and the third query is shown as being below the second query). The first query operates to retrieve from the RDBMS 112 data to construct objects of the top-level class that satisfy the conditions present in the original object query. The tuples that are retrieved by the first query are sorted according to the primary key of the top-level table.
The intermediate table stores the foreign key from the top-level table that references the prefetch table. These foreign keys are called the top-level foreign keys for reference purposes. The intermediate table also stores the foreign key from the prefetch table that references the top-level table. These foreign keys are called the prefetch foreign keys for reference purposes. The second query operates to identify tuples in the intermediate table that satisfy the conditions present in the original object query, and that relate to the tuples retrieved by the first query (i.e., where the top-level foreign key is equal to the top-level table's foreign key). The second query retrieves from these identified tuples the top-level foreign key and the prefetch foreign key. These tuples retrieved by the second query are sorted by the top-level foreign key.
The third query operates to retrieve from the RDBMS 112 data to construct objects of the prefetch class that satisfy the conditions present in the original object query, and that relate to the tuples retrieved by the first query. The tuples that are retrieved by the third query are sorted according to the primary key of the prefetch table.
The manner in which the second query generator 404 generates relational queries in accordance with Rule 3 shall now be described with reference to a flowchart 1802 in FIGS. 18A and 18B. Flowchart 1802 begins with step 1804, where control immediately passes to step 1806.
In step 1806, the second query generator 404 generates the "select" statement of the first query such that this "select" statement lists the columns of the top-level table which map to the base attributes in the queried class. The second query generator 404 may query the schema mapping module 108 to obtain schema mapping information to perform step 1806.
In step 1808, the second query generator 404 generates the "from" statement of the first query so that this "from" statement references the top-level table.
In step 1810, the second query generator 404 generates the "where" statement of the first query so that this "where" statement operates to retrieve tuples of the top-level table where the conditions related to the queried class (and specified in the translated object query) are satisfied.
In step 1812, the second query generator 404 generates an "order by" statement to order the tuples retrieved from the top-level table by the primary key of the top-level table (in the example of FIG. 13, the primary key of the top-level table Xr is assumed to be x1.
In step 1814, the second query generator 404 generates the "select" statement of the second query such that this "select" statement lists the pertinent foreign keys (of the top-level and prefetch tables) stored in the intermediate table. (In the example of FIG. 13, table XY is the intermediate table.) The "pertinent foreign key" of the top-level table is the foreign key that is associated with the prefetch table (Xfk in the example of FIG. 13) . The "pertinent foreign key" of the prefetch table is the foreign key that is associated with the top-level table (Yfk in the example of FIG. 13) . The second query generator 404 may query the schema mapping module 108 to obtain schema mapping information to perform step 1814.
In step 1816, the second query generator 404 generates the "from" statement of the second query so that this "from" statement references the top-level table and the intermediate table.
In step 1818, the second query generator 404 generates the "where" statement of the second query so that this "where" statement operates to retrieve tuples of the intermediate table where: (1) the condition list (as specified in the translated object query) are satisfied; and (2) the primary key of the top-level table is equal to the pertinent foreign key of the top-level table (Xfk in the example of FIG. 13).
In step 1820, the second query generator 404 generates an "order by" statement to order the tuples retrieved from the intermediate table by the pertinent foreign key of the top-level table (Xfk in the example of FIG. 13).
In step 1824, the second query generator 404 generates the "select" statement for the third query such that this "select" statement lists the columns of the prefetch table which map to the base attributes in the prefetch class. The second query generator 404 may query the schema mapping module 108 to obtain schema mapping information to perform step 1824.
In step 1826, the second query generator 404 generates the "from" statement of the third query so that this "from" statement references the top-level table, the prefetch table, and the intermediate table.
In step 1828, the second query generator 404 generates the "where" statement of the third query so that this "where" statement operates to retrieve tuples of the prefetch table where (1) the condition list (as specified in the translated object query) are satisfied; (2) the top-level table's foreign key retrieved from the intermediate table is equal to the primary key in the top-level table; and (3) the prefetch table's foreign key retrieved from the intermediate table is equal to the primary key in the prefetch table.
In step 1830, the second query generator 404 generates an "order by" statement to order the tuples retrieved from the intermediate table by the primary key of the prefetch table.
Flowchart 1802 is complete after step 1830 is performed, as indicated by step 1832.
Alternate Embodiment for Generating Relational Oueries
According to an alternate embodiment of the present invention, the second query generator 404 generates relational queries by modifying the parent query. Consider, for example, Rule 1c shown in FIG. 11. In the example of FIG. 11, the prefetch path component is "X.Y". As described above, the second query generator 404 generates a relational query (shown in FIG. 11; this query is called the "Y query" for reference purposes) according to Rule 1c to obtain data needed to construct objects of class Y. The parent query for this Y query is called the "X query" for reference purposes. For this particular example, the X query is equal to the translated object query (since X is the root or top-level class). The form of the translated object query (the X query) is as follows:
SELECT X.x1, . . . , X.xn
FROM Xr X
WHERE <xlated-- conditionlist>
According to the alternate embodiment of the present invention, the second query generator 404 modifies this X query in a straightforward manner to generate the Y query (rather than by starting from scratch as described above with reference to FIG. 16).
Now assume that the following prefetch path component also exists: X.Y.Z (where Z is another class in the object schema that maps to table Zr). According to the present invention, the second query generator 404 generates a relational query (called the "Z query" for reference purposes) to obtain data needed to construct objects of class Z. The parent query for the Z query is the Y query, shown in FIG. 11. According to the alternate embodiment of the present invention, the second query generator 404 modifies the Y query to generate the Z query.
The same is true for Rules 1a, 1b, 2, and 3. Consider Rule 1a. According to this alternate embodiment, the first query is partially generated by modifying its parent query. In some cases, the parent query of the first query is the translated object query (although this is not always the case). Similarly, the second query is generated by modifying its parent query. According to the present invention, the second query's parent query is defined to be the first query. Thus, the second query is generated by modifying the partially completed first query. The form of the first query is finalized after the second query is generated.
For example, consider again the translated object query:
The first query is partially generated by modifying its parent query (the translated object query), such that the partially completed first query is as follows:
In other words, the partially completed first query is simply equal to the translated object query. The second query is then generated by modifying its parent query, i.e., the partially completed first query. Steps similar to steps 1412-1416 in flowchart 1402 are performed to implement such modifications. Then, the first query is modified and its form is finalized. In particular, a step similar to step 1410 is performed to add the condition "AND X.Yfk =Y.y1" to the "where" statement. It is advantageous to add this condition to the "where" statement at this point, since we can then implement the query generation algorithm by efficiently making a single traversal of the nested path (comprising the set of all prefetch paths), generating the query for the parent and then transforming the parent query to generate the query for the child, and so on.
The manner in which the second query generator 404 implements Rules 1b, 2, and 3 according to this alternate embodiment will be apparent to persons skilled in the relevant art based on the above discussion.
Multiple Prefetch Paths
The rules described above only handle one prefetch path. It is possible that multiple prefetch paths will exist for the same object query. An example of multiple prefetch paths on a many-to-many relationship and the chosen query plan is given in FIG. 19. Notice that the number of queries executed may increase with each additional prefetch path. In addition to generating more queries, handling multiple prefetch paths may require multiple sorts on the same set of objects. Unlike in the single prefetch path case, where the sort on a foreign key could always be pushed to the RDBMS 112, in the case of multiple prefetch paths, only one sort per class (or table) can be delegated to the RDBMS 112 (using an ORDER BY clause) and the other sorts are executed in the gateway 106 using intermediate types. Also, even in the single prefetch path case, there are cases where extra merges and sorts must be performed in the gateway (e.g., Rule 3a).
As described above, the present invention includes the first query generator 402, the second query generator 404, and the schema mapping module 108. This embodiment assumes that the user or application provides zero or more prefetch paths with the original object query.
According to an alternate embodiment, the present invention represents the second query generator 404 only, operating in an environment containing the application 104, the object-oriented DBMS 110, and the RDBEMS 112. This alternate embodiment also assumes that the user or application provides zero or more prefetch paths. This alternate embodiment further assumes that the environment in which the second query generator 404 is contained includes some schema mapping mechanism (such as the schema mapping module 108) for providing schema mapping information when appropriately queried, and some initial query generator (such as the first query generator 402) for generating the translated object query from the original object query. It is assumed that the second query generator 404 receives any schema mapping information that it requires (the details of such information are discussed above), and that it receives the translated object query.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5212787 *Mar 12, 1991May 18, 1993International Business Machines CorporationMethod and apparatus for accessing a relational database without exiting an object-oriented environmentUS5263167 *Nov 22, 1991Nov 16, 1993International Business Machines CorporationUser interface for a relational database using a task object for defining search queries in response to a profile object which describes user proficiencyUS5291583 *Dec 14, 1990Mar 1, 1994Racal-Datacom, Inc.Automatic storage of persistent ASN.1 objects in a relational schemaUS5295256 *Dec 14, 1990Mar 15, 1994Racal-Datacom, Inc.Automatic storage of persistent objects in a relational schemaUS5379419 *Dec 7, 1990Jan 3, 1995Digital Equipment CorporationMethods and apparatus for accesssing non-relational data files using relational queriesUS5426780 *Feb 28, 1992Jun 20, 1995Intergraph CorporationSystem for dynamic segmentation analysis using conversion of relational data into object-oriented dataUS5448727 *Apr 30, 1991Sep 5, 1995Hewlett-Packard CompanyDomain based partitioning and reclustering of relations in object-oriented relational database management systemsUS5450581 *Oct 11, 1994Sep 12, 1995International Business Machines CorporationSystem for copying from one database management system to another by translating authorization statementsUS5499371 *Mar 22, 1995Mar 12, 1996Persistence Software, Inc.Method and apparatus for automatic generation of object oriented code for mapping relational data to objectsUS5504885 *Jun 29, 1993Apr 2, 1996Texas Instruments IncorporatedO-R gateway: a system for connecting object-oriented application programs and relational databasesUS5548749 *Oct 29, 1993Aug 20, 1996Wall Data IncorporatedSemantic orbject modeling system for creating relational database schemasUS5550971 *Jun 2, 1995Aug 27, 1996U S West Technologies, Inc.Method and system for generating a user interface adaptable to various database management systemsUS5564113 *Jun 7, 1995Oct 8, 1996International Business Machines CorporationComputer program product for rendering relational database management system differences transparentUS5596746 *Oct 26, 1994Jan 21, 1997General Electric CompanyMethod for transforming relational data base schemas into object models using ideal table meta modelsUS5615362 *Mar 22, 1995Mar 25, 1997Persistence Software, Inc.Method and apparatus for managing relational data in an object cacheUS5694598 *Oct 12, 1994Dec 2, 1997U S West Technologies, Inc.Method for mapping data between a relational format and an object-oriented format* Cited by examinerNon-Patent CitationsReference1Domscheit et al., "Conflict Assessment with Pending Patent Applications for Silver Edition 1," Boblingen Programming Lab, Jul. 31, 1995, pp. ii-9.2 *Domscheit et al., Conflict Assessment with Pending Patent Applications for Silver Edition 1, B o blingen Programming Lab, Jul. 31, 1995, pp. ii 9.3Eliot et al., "Working with Persistent Objects: to Swizzler or Not to Swizzle," IEEE Transactions on Software Engineering, vol. 18, No. 8, Aug., 1992, pp. 657-673.4 *Eliot et al., Working with Persistent Objects: to Swizzler or Not to Swizzle, IEEE Transactions on Software Engineering, vol. 18, No. 8, Aug., 1992, pp. 657 673.5Kemper et al., "Adaptable Pointer Swizzling Strategies in Object Bases," IEEE, RWTH Technical University, Aachen, Germany, 1993, pp. 155-162.6 *Kemper et al., Adaptable Pointer Swizzling Strategies in Object Bases, IEEE, RWTH Technical University, Aachen, Germany, 1993, pp. 155 162.7Orenstein et al., "Query Processing in the ObjectStore Database System," Proceedings of the ACM SIGMOD Conference, Jun., 1992, San Diego, California, pp. 403-412.8 *Orenstein et al., Query Processing in the ObjectStore Database System, Proceedings of the ACM SIGMOD Conference, Jun., 1992, San Diego, California, pp. 403 412.9Urban et al., "An Object-Oriented Query Language Interface to Relational Databases in a Multidatabase Database Environment," IEEE, Arizona State University, 1994, pp. 387-394.10 *Urban et al., An Object Oriented Query Language Interface to Relational Databases in a Multidatabase Database Environment, IEEE, Arizona State University, 1994, pp. 387 394.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS5918231 *Feb 26, 1996Jun 29, 1999Nec CorporationObject-oriented database management system with improved usage efficiency of main memoryUS5925100 *Mar 21, 1996Jul 20, 1999Sybase, Inc.Client/server system with methods for prefetching and managing semantic objects based on object-based prefetch primitive present in client's executing applicationUS5963933 *Jun 25, 1997Oct 5, 1999International Business Machines CorporationEfficient implementation of full outer join and anti-joinUS5995973 *Aug 29, 1997Nov 30, 1999International Business Machines CorporationStoring relationship tables identifying object relationshipsUS6047284 *May 14, 1997Apr 4, 2000Portal Software, Inc.Method and apparatus for object oriented storage and retrieval of data from a relational databaseUS6078925 *Jun 7, 1995Jun 20, 2000International Business Machines CorporationComputer program product for database relational extendersUS6078926 *Dec 18, 1997Jun 20, 2000Persistence Software, Inc.Method and apparatus for performing multi-class object fetch in a database management systemUS6108664 *Oct 31, 1997Aug 22, 2000Oracle CorporationObject views for relational dataUS6122627 *May 9, 1997Sep 19, 2000International Business Machines CorporationSystem, method, and program for object building in queries over object viewsUS6175837Jun 29, 1998Jan 16, 2001Sun Microsystems, Inc.Object-relational mapping toll that processes viewsUS6226637 *Sep 8, 1999May 1, 2001International Business Machines Corp.System, method, and program, for object building in queries over object viewsUS6260045 *May 22, 1998Jul 10, 2001Apple Computer, Inc.Method and apparatus for optimizing interface dispatching in an object-oriented programming environmentUS6268850Jun 29, 1998Jul 31, 2001Sun Microsystems, Inc.User interface for the specification of lock groupsUS6356886 *Nov 30, 1995Mar 12, 2002Electronic Data Systems CorporationApparatus and method for communicating with a knowledge baseUS6360223 *Jun 29, 1998Mar 19, 2002Sun Microsystems, Inc.Rule-based approach to object-relational mapping strategiesUS6374235Jun 25, 1999Apr 16, 2002International Business Machines CorporationMethod, system, and program for a join operation on a multi-column table and satellite tables including duplicate valuesUS6374252 *Oct 16, 1997Apr 16, 2002I2 Technologies Us, Inc.Modeling of object-oriented database structures, translation to relational database structures, and dynamic searches thereonUS6374256Jun 29, 1998Apr 16, 2002Sun Microsystems, Inc.Method and apparatus for creating indexes in a relational database corresponding to classes in an object-oriented applicationUS6385618Jun 29, 1998May 7, 2002Sun Microsystems, Inc.Integrating both modifications to an object model and modifications to a database into source code by an object-relational mapping toolUS6397203 *Sep 30, 1998May 28, 2002International Business Machines CorporationDefining object classes to match corresponding specialized data types in a relational databaseUS6397204Jun 25, 1999May 28, 2002International Business Machines CorporationMethod, system, and program for determining the join ordering of tables in a join queryUS6430556 *Nov 1, 1999Aug 6, 2002Sun Microsystems, Inc.System and method for providing a query object development environmentUS6446063Jun 25, 1999Sep 3, 2002International Business Machines CorporationMethod, system, and program for performing a join operation on a multi column table and satellite tablesUS6477527 *Mar 7, 2001Nov 5, 2002International Business Machines CorporationSystem, method, and program for object building in queries over object viewsUS6484180 *Aug 2, 1999Nov 19, 2002Oracle CorporationAccessing domain object data stored in a relational database systemUS6499036Aug 12, 1998Dec 24, 2002Bank Of America CorporationMethod and apparatus for data item movement between disparate sources and hierarchical, object-oriented representationUS6505190 *Jun 28, 2000Jan 7, 2003Microsoft CorporationIncremental filtering in a persistent query systemUS6529915Dec 6, 1999Mar 4, 2003Portal Software, Inc.Computer-implemented program product and method of deferring allocation of storage for array elements of objectsUS6591275 *Jun 2, 2000Jul 8, 2003Sun Microsystems, Inc.Object-relational mapping for tables without primary keysUS6609133Jan 5, 2001Aug 19, 2003Sun Microsystems, Inc.Integrating both modifications to an object model and modifications to a database into source code by an object-relational mapping toolUS6728726 *Mar 5, 1999Apr 27, 2004Microsoft CorporationPrefetching and caching persistent objectsUS6973457May 10, 2002Dec 6, 2005Oracle International CorporationMethod and system for scrollable cursorsUS7089331Feb 29, 2000Aug 8, 2006Oracle International CorporationMethod and mechanism for reducing client-side memory footprint of transmitted dataUS7103590 *Aug 24, 2001Sep 5, 2006Oracle International CorporationMethod and system for pipelined database table functionsUS7103613 *May 14, 2003Sep 5, 2006International Business Machines CorporationObject oriented query root leaf inheritance to relational join translator method, system, article of manufacture, and computer program productUS7111016Nov 18, 2002Sep 19, 2006Bank Of America CorporationMethod and apparatus for data item movement between disparate sources and hierarchical, object-oriented representationUS7130856Jul 20, 2002Oct 31, 2006Microsoft CorporationMap and data location providerUS7133880Apr 11, 2000Nov 7, 2006Oracle International CorporationObject views for relational dataUS7162469Jul 20, 2002Jan 9, 2007Microsoft CorporationQuerying an object for propertiesUS7165075 *Jul 20, 2002Jan 16, 2007Microsoft CorporationObject graph faulting and trimming in an object-relational database systemUS7191182Jul 20, 2002Mar 13, 2007Microsoft CorporationContainment hierarchy in a database systemUS7389284 *May 10, 2002Jun 17, 2008Oracle International CorporationMethod and mechanism for efficient processing of remote-mapped queriesUS7412436Jul 20, 2002Aug 12, 2008Microsoft CorporationSystem and interface for manipulating a databaseUS7461053Jan 18, 2005Dec 2, 2008Microsoft CorporationSystem and interface for manipulating a databaseUS7555488Feb 19, 2004Jun 30, 2009Microsoft CorporationPrefetching and caching persistent objectsUS7610351May 10, 2002Oct 27, 2009Oracle International CorporationMethod and mechanism for pipelined prefetchingUS7613715Apr 7, 2006Nov 3, 2009Microsoft CorporationMap and data location providerUS7634456Sep 7, 2004Dec 15, 2009Oracle International CorporationSQL structure analyzerUS7636740 *Nov 3, 2005Dec 22, 2009Electronic And Telecommunications Research InstituteDatabase cache systemUS7650357 *Jan 13, 2005Jan 19, 2010Microsoft CorporationTranslation of object queries involving inheritenceUS7653652 *Aug 17, 2004Jan 26, 2010Microsoft CorporationDatabase schema for structured query language (SQL) serverUS7664730Sep 7, 2004Feb 16, 2010Oracle International CorporationMethod and system for implementing a SQL profileUS7664778Sep 7, 2004Feb 16, 2010Oracle International CorporationSQL tuning setsUS7702622 *Jun 29, 2007Apr 20, 2010Microsoft CorporationAdvanced techniques for SQL generation of performancepoint business rulesUS7734657Jul 28, 2006Jun 8, 2010Microsoft CorporationContainment hierarchy in a database systemUS7739263 *Sep 7, 2004Jun 15, 2010Oracle International CorporationGlobal hintsUS7757226Mar 17, 2004Jul 13, 2010Oracle International CorporationMethod and mechanism for performing a rolling upgrade of distributed computer softwareUS7765224 *Nov 18, 2005Jul 27, 2010Microsoft CorporationUsing multi-dimensional expression (MDX) and relational methods for allocationUS7788285May 14, 2004Aug 31, 2010Oracle International CorporationFiner grain dependency tracking for database objectsUS7801856Aug 9, 2006Sep 21, 2010Oracle International CorporationUsing XML for flexible replication of complex typesUS7805411Sep 7, 2004Sep 28, 2010Oracle International CorporationAuto-tuning SQL statementsUS7809768Apr 27, 2006Oct 5, 2010Oracle International CorporationMethod and apparatus for object oriented storage and retrieval of data from a relational databaseUS7836032 *Mar 28, 2006Nov 16, 2010International Business Machines CorporationRemapping child references when parent reference updates are processedUS7853961Jun 30, 2005Dec 14, 2010Microsoft CorporationPlatform for data services across disparate application frameworksUS7877397Jul 30, 2007Jan 25, 2011Microsoft CorporationExtensible command execution for entity data model platformUS7895241Oct 16, 2007Feb 22, 2011Schlumberger Technology Corp.Method and apparatus for oilfield data repositoryUS7917538Sep 14, 2006Mar 29, 2011Bank Of America CorporationMethod and apparatus for data item movement between disparate sources and hierarchical, object-oriented representationUS8020144Jun 29, 2007Sep 13, 2011Microsoft CorporationMetadata-based application deploymentUS8102980Jun 8, 2007Jan 24, 2012Oracle International CorporationRevenue management systems and methods with bill and account suppressionUS8116326Jun 28, 2006Feb 14, 2012Oracle International CorporationRevenue management system and methodUS8117358Jul 28, 2006Feb 14, 2012Oracle International CorporationRevenue management system and method utilizing database backupUS8150866Jan 7, 2009Apr 3, 2012Semmle LimitedCreating concise and re-useable queries over complex dataUS8180787Sep 14, 2005May 15, 2012International Business Machines CorporationApplication portability and extensibility through database schema and query abstractionUS8200604Nov 1, 2007Jun 12, 2012Microsoft CorporationMulti-platform business calculation rule language and execution environmentUS8223777Nov 15, 2006Jul 17, 2012Oracle International CorporationGateway for achieving low latency and high availability in a real time event processing systemUS8223935May 1, 2006Jul 17, 2012Oracle International CorporationRevenue management systems and methodsUS8250112Jun 17, 2009Aug 21, 2012International Business Machines CorporationConstructing declarative componentized applicationsUS8260825 *May 11, 2009Sep 4, 2012Business Objects Software LimitedFunctionally-dependent analysis objectsUS8326888Jan 5, 2011Dec 4, 2012Schlumberger Technology CorporationMethod and apparatus for oilfield data repositoryUS8369500Jun 8, 2007Feb 5, 2013Oracle International CorporationRevenue management systems and methods with sponsored top-up optionsUS8422651Jun 8, 2007Apr 16, 2013Oracle International CorporationRevenue management systems and methods with re-rating and rebillingUS8462923Jun 8, 2007Jun 11, 2013Oracle International CorporationRevenue management systems and methods with payment suspense managementUS8554782Mar 19, 2012Oct 8, 2013Semmle LimitedCreating concise and re-useable queries over complex dataUS8612468Mar 2, 2005Dec 17, 2013Red Hat, Inc.System and method for retrieving data from a relational database management systemUS8631049Mar 27, 2012Jan 14, 2014International Business Machines CorporationConstructing declarative componentized applicationsUS8650536 *Mar 25, 2005Feb 11, 2014Ca, Inc.Modular server architectureUS8738591Nov 23, 2011May 27, 2014Oracle International CorporationSorting transactions in a memory object storeUS8798576Jun 8, 2007Aug 5, 2014Oracle International CorporationRevenue management systems and methods with enhanced rolloverUS8825629Sep 7, 2004Sep 2, 2014Oracle International CorporationMethod for index tuning of a SQL statement, and index merging for a multi-statement SQL workload, using a cost-based relational query optimizerUS8825805Apr 25, 2006Sep 2, 2014Oracle International CorporationMethod and mechanism for reducing client-side memory footprint of transmitted dataUS8856178Nov 23, 2011Oct 7, 2014Oracle International CorporationCommitting events where transaction threads have read-only access to shared memoryUS8886764 *Sep 29, 2010Nov 11, 2014Systemite AbQuick uploadUS8983934Sep 7, 2004Mar 17, 2015Oracle International CorporationSQL tuning baseUS9009181 *Aug 23, 2007Apr 14, 2015International Business Machines CorporationAccessing objects in a service registry and repositoryUS9244938Aug 29, 2014Jan 26, 2016Oracle International CorporationMethod and mechanism for reducing client-side memory footprint of transmitted dataUS20010047372 *Feb 12, 2001Nov 29, 2001Alexander GorelikNested relational data modelUS20030120600 *Nov 18, 2002Jun 26, 2003Gurevich Michael N.Method and apparatus for data item movement between disparate sources and hierarchical, object-oriented representationUS20030182273 *Mar 22, 2002Sep 25, 2003Goldberg Robert N.Method and apparatus for generating a query objectUS20030204514 *Feb 26, 2003Oct 30, 2003Portal Software, Inc.Method and apparatus for object oriented storage and retrieval of data from a relational databaseUS20040010498 *Jul 10, 2002Jan 15, 2004Lin Tser YengObject persistence to relational database within run-time environment supporting attributes and reflectionUS20040015488 *Jul 20, 2002Jan 22, 2004Anonsen Steven P.Containment hierarchy in a database systemUS20040015489 *Jul 20, 2002Jan 22, 2004Anonsen Steven P.Querying an object for propertiesUS20040015516 *Jul 20, 2002Jan 22, 2004Harter Steven VirgilObject graph faulting and trimming in an object-relational database systemUS20040162841 *Feb 19, 2004Aug 19, 2004Microsoft CorporationPrefetching and caching persistent objectsUS20040210564 *Jun 26, 2001Oct 21, 2004Kenneth OksanenIndexing method and system for relational databasesUS20040230584 *May 14, 2003Nov 18, 2004International Business Machines CorporationObject oriented query root leaf inheritance to relational join translator method, system, article of manufacture, and computer program productUS20040260706 *Jul 17, 2003Dec 23, 2004Microsoft CorporationQuerying an object for propertiesUS20050027725 *Aug 17, 2004Feb 3, 2005Microsoft CorporationDatabase schema for structured query language (SQL) ServerUS20050097091 *Sep 7, 2004May 5, 2005Oracle International CorporationSQL tuning baseUS20050119999 *Sep 7, 2004Jun 2, 2005Oracle International CorporationAutomatic learning optimizerUS20050120000 *Sep 7, 2004Jun 2, 2005Oracle International CorporationAuto-tuning SQL statementsUS20050120001 *Sep 7, 2004Jun 2, 2005Oracle International CorporationSQL structure analyzerUS20050125393 *Sep 7, 2004Jun 9, 2005Oracle International CorporationSQL tuning setsUS20050125398 *Sep 7, 2004Jun 9, 2005Oracle International CorporationGlobal hintsUS20050125427 *Sep 7, 2004Jun 9, 2005Oracle International CorporationAutomatic SQL tuning advisorUS20050125432 *Jan 13, 2005Jun 9, 2005Microsoft CorporationTranslation of object queries involving inheritenceUS20050125452 *Sep 7, 2004Jun 9, 2005Oracle International CorporationSQL profileUS20050138015 *Sep 7, 2004Jun 23, 2005Oracle International CorporationHigh load SQL driven statistics collectionUS20050160090 *Feb 24, 2005Jul 21, 2005Microsoft CorporationMethod and system for accessing database objects in polyarchical relationships using data path expressionsUS20050177557 *Sep 7, 2004Aug 11, 2005Oracle International CorporationAutomatic prevention of run-away query executionUS20050187917 *Sep 7, 2004Aug 25, 2005Oracle International CorporationMethod for index tuning of a SQL statement, and index merging for a multi-statement SQL workload, using a cost-based relational query optimizerUS20050210461 *Mar 17, 2004Sep 22, 2005Oracle International CorporationMethod and mechanism for performing a rolling upgrade of distributed computer softwareUS20050235275 *Mar 25, 2005Oct 20, 2005Christopher BettsModular server architectureUS20050251523 *May 7, 2004Nov 10, 2005Oracle International CorporationMinimizing downtime for application changes in database systemsUS20060116999 *Nov 30, 2004Jun 1, 2006International Business Machines CorporationSequential stepwise query condition buildingUS20060148572 *Nov 3, 2005Jul 6, 2006Lee Hun JDatabase cache systemUS20060190478 *Apr 27, 2006Aug 24, 2006Portal Software, Inc.Method and apparatus for object oriented storage and retrieval of data from a relational databaseUS20060195460 *Sep 16, 2005Aug 31, 2006Microsoft CorporationData model for object-relational dataUS20060195476 *Jun 30, 2005Aug 31, 2006Microsoft CorporationPlatform for data services across disparate application frameworksUS20060195615 *Apr 25, 2006Aug 31, 2006Oracle International CorporationMethod and mechanism for reducing client-side memory footprint of transmitted dataUS20060200438 *Mar 2, 2005Sep 7, 2006Red Hat, Inc.System and method for retrieving data from a relational database management systemUS20060224628 *Jan 27, 2006Oct 5, 2006Bea Systems, Inc.Modeling for data servicesUS20060235867 *Apr 7, 2006Oct 19, 2006Microsoft CorporationMap and data location providerUS20060265411 *Jul 28, 2006Nov 23, 2006Microsoft CorporationContainment hierarchy in a database systemUS20070011194 *Sep 14, 2006Jan 11, 2007Bank Of America CorporationMethod and apparatus for data item movement between disparate sources and hierarchical, object-oriented representationUS20070112834 *Nov 17, 2005May 17, 2007Farr James ADatabase consolidation toolUS20070118510 *Nov 18, 2005May 24, 2007Microsoft CorporationOptimization of leaf-level multi-dimensional calculation using scriptsUS20070118516 *Nov 18, 2005May 24, 2007Microsoft CorporationUsing multi-dimensional expression (MDX) and relational methods for allocationUS20070174318 *Jan 26, 2006Jul 26, 2007International Business Machines CorporationMethods and apparatus for constructing declarative componentized applicationsUS20070239807 *Mar 28, 2006Oct 11, 2007Morgan Timothy SSiebel CRM LOV/MLOV remapping toolUS20070266041 *Aug 29, 2006Nov 15, 2007Microsoft CorporationConcept of relationshipsets in entity data model (edm)US20080040369 *Aug 9, 2006Feb 14, 2008Oracle International CorporationUsing XML for flexible replication of complex typesUS20080235280 *Oct 16, 2007Sep 25, 2008Schlumberger Technology CorporationMethod and apparatus for oilfield data repositoryUS20090006370 *Jun 29, 2007Jan 1, 2009Microsoft CorporationAdvanced techniques for sql generation of performancepoint business rulesUS20090006409 *Jun 29, 2007Jan 1, 2009Microsoft CorporationMetadata-based application deploymentUS20090037394 *Jul 30, 2007Feb 5, 2009Microsoft CorporationExtensible command execution for entity data model platformUS20090055432 *Aug 23, 2007Feb 26, 2009International Business Machines CorporationAccessing objects in a service registry and repositoryUS20090177640 *Jan 7, 2009Jul 9, 2009Semmle LimitedCreating concise and re-useable queries over complex dataUS20090254584 *Jun 17, 2009Oct 8, 2009International Business Machines CorporationMethods and Apparatus for Constructing Declarative Componentized ApplicationsUS20100010979 *Jan 14, 2010International Business Machines CorporationReduced Volume Precision Data Quality Information Cleansing Feedback ProcessUS20100287223 *May 11, 2009Nov 11, 2010Jean-Yves CrasFunctionally-dependent analysis objectsUS20110082917 *Sep 29, 2010Apr 7, 2011Soederberg Jan OkQuick uploadUS20110131248 *Jun 2, 2011Thepaut SergeAnalysis groups for semantic layerUS20110167089 *Jul 7, 2011Schlumberger Technology CorporationMethod and apparatus for oilfield data repositoryUS20140181151 *Dec 21, 2012Jun 26, 2014Didier MazoueQuery of multiple unjoined viewsEP1383055A2 *Jul 17, 2003Jan 21, 2004Microsoft CorporationMap and data location providerEP1383056A2 *Jul 21, 2003Jan 21, 2004Microsoft CorporationQuerying an object-relational database systemEP1387297A2 *Jul 21, 2003Feb 4, 2004Microsoft CorporationTranslation of object property joins to relational database joinsEP1484675A3 *May 27, 2004Dec 24, 2008Microsoft CorporationSystem and method for generating scripts for defining database objectsWO2000010083A2 *Aug 12, 1999Feb 24, 2000Concord SolutionsMethod and apparatus for data item movement between disparate sources and hierarchical, object-oriented representationWO2001071492A1 *Mar 20, 2000Sep 27, 2001Shen JianjunMethod and system for data management in an object-oriented system* Cited by examinerClassifications U.S. Classification1/1, 707/999.102, 707/999.004, 707/999.003, 707/999.1International ClassificationG06F17/30Cooperative ClassificationY10S707/99943, Y10S707/99934, G06F17/30595, G06F17/30607, Y10S707/99933European ClassificationG06F17/30S8T, G06F17/30S8RLegal EventsDateCodeEventDescriptionJan 2, 2002REMIMaintenance fee reminder mailedJun 10, 2002LAPSLapse for failure to pay maintenance feesAug 6, 2002FPExpired due to failure to pay maintenance feeEffective date: 20020609RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services