Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2003-05-08
2004-10-19
Mizrahi, Diane D (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06807546
ABSTRACT:
COPYRIGHT STATEMENT
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
APPENDIX DATA
This application includes a transmittal under 37 C.F.R. Sec. 1.52(e) of a Computer Program Listing Appendix. The Appendix comprises text files that are IBM-PC machine and Microsoft Windows Operating System compatible. The files include the following list of files.
Object Description: File 1; Object ID: qog_subplannode.txt, created: May 6, 2003, 10:47 am, size 3.62 KB; Object Contents: Source Code.
Object Description: File. 2; Object ID: qog_optgov.txt, created: May 6, 2003, 10:48 am, size 6.07 KB; Object Contents: Source Code.
All of the material disclosed in the Computer Program Listing Appendix can be found at the U.S. Patent and Trademark Office archives and is hereby incorporated by reference into the present application.
BACKGROUND OF INVENTION
1. Field of the Invention
The present invention relates generally to information processing environments and, more particularly, to a database management system (DBMS) having a methodology for distributing query optimization effort over large search spaces.
2. Description of the Background Art
Computers are very powerful tools for storing and providing access to vast amounts of information. Computer databases are a common mechanism for storing information on computer systems while providing easy access to users. A typical database is an organized collection of related information stored as “records” having “fields” of information. As an example, a database of employees may have a record for each employee where each record contains fields designating specifics about the employee, such as name, home address, salary, and the like.
Between the actual physical database itself (i.e., the data actually stored on a storage device) and the users of the system, a database management system or DBMS is typically provided as a software cushion or layer. In essence, the DBMS shields the database user from knowing or even caring about underlying hardware-level details. Typically, all requests from users for access to the data are processed by the DBMS. For example, information may be added or removed from data files, information may be retrieved from, or updated in, such files; and so forth, all without user knowledge of underlying system implementation. In this manner, the DBMS provides users with a conceptual view of the database that is removed from the hardware level. The general construction and operation of a database management system is known in the art. See e.g., Date, C., “An Introduction to Database Systems, Volume I and II”, Addison Wesley, 1990; the disclosure of which is hereby incorporated by reference.
DBMS systems have long since moved from a centralized mainframe environment to a decentralized or distributed environment. One or more PC “client” systems, for instance, may be connected via a network to one or more server-based database systems (SQL database server). Commercial examples of these “client/server” systems include Powersoft (r) clients connected to one or more Sybase (r) SQL Anywhere (r) Studio (Adaptive Server (r) Anywhere) database servers. Both Powersoft and Sybase SQL Anywhere Studio (Adaptive Server Anywhere) are available from Sybase, Inc. of Dublin, Calif.
In today's computing environment, database technology can be found on virtually any device, from traditional mainframe computers to cellular phones. Sophisticated applications, whether human resources information systems or sales force automation systems, can “push” much of their complexity into the database itself. Indeed, this represents one of the main benefits of database technology. The challenge, however, is to support these applications, and the complex queries they generate, on small computing devices. At the same time, users expect the productivity and reliability advantages of using a relational DBMS.
One purpose of a database system is to answer decision support queries. A query may be defined as a logical expression over the data and the data relationships set forth in the database, and results in the identification of a subset of the database. Consider, for instance, the execution of a request for information from a relational DBMS. In operation, this request is typically issued by a client system as one or more Structured Query Language or “SQL” queries for retrieving particular data (e.g., a list of all employees earning $10,000 or more) from database tables on a server. In response to this request, the database system typically returns the names of those employees earning $10,000, where “employees” is a table defined to include information about employees of a particular organization. The syntax of SQL is well documented, see e.g., “Information Technology—Database languages—SQL”, published by the American National Standards Institute as American National Standard ANSI/ISO/IEC 9075: 1992, the disclosure of which is hereby incorporated by reference.
SQL queries express what results are requested but do not state how the results should be obtained. In other words, the query itself does not tell how the query should be evaluated by the DBMS. Rather, a component called the optimizer determines the “plan” or the best method of accessing the data to implement the SQL query. The query optimizer is responsible for transforming an SQL request into an access plan composed of specific implementations of the algebraic operator selection, projection, join, and so forth. The role of a query optimizer in a relational DBMS system is to find an adequate execution plan from a search space of many semantically equivalent alternatives. One component of this task is join enumeration. Since relational databases typically only provide physical operators that can join two tables at a time, an n-way join must be executed as a sequence of two-way joins, and there are many possible such sequences. The optimizer must enumerate some or all of these sequences and choose one based on estimates of their relative execution costs. In general, this problem is NP-complete. (See e.g., Ibaraki, T. et al “On the Optimal Nesting Order for Computing N-Relational Joins”, ACM Transactions on Database Systems, 9(3): 482-502, September 1984. See also e.g., Ono, K. et al “Measuring the Complexity of Join Enumeration in Query Optimization”, in Proceedings of the 16th International Conference on Very Large Data Bases, pp. 314-325, Brisbane, Australia, August 1990, Morgan Kaufmann; and Steinbrunn, M. et al “Heuristic and Randomized Optimization for the Join Ordering Problem”, The VLDB Journal, 6(3): 191-208, August 1997.) An NP-complete problem is any one of a class of computational problems for which no efficient solution has been found.
In practice, query optimizers restrict the sequences or plans that are considered so that an adequate plan can be found in a reasonable amount of time. Examples of such limitations include: restricting the search to left-deep trees where the inner operand of each join is a single table (see e.g., Cluet, S. et al “On the Complexity of Generating Optimal Left-deep Processing Trees with Cross Products”, in Proceedings of the Fifth International Conference on Database Theory (ICDT '95), pp. 54-67, Prague, Czech Republic, January 1995, Springer-Verlag); requiring each join to have at least one equi-join predicate of the form (column1=column2); considering only a subset of the available physical join methods (e.g., only nested loop joins); considering only a subset of the possible table access methods (e.g., only index scans); and deferring Cartesian products as late in the plan as possible. (See e.g., Morishita, S. “Avoiding Cartesian Products for Multiple Joins”, Journal of the ACM, 44(1): 57-85, January 1997. Also see e.g., Selinger, P. G. et al “Acces
Mizrahi Diane D
Riddle G. Mack
Smart John A.
Sybase Inc.
LandOfFree
Database system with methodology for distributing query... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Database system with methodology for distributing query..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Database system with methodology for distributing query... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3307516