Method and an apparatus for the processing of queries to a database

• US 6,732,091 B1
• Filed: 07/24/2001
• Issued: 05/04/2004
• Est. Priority Date: 04/16/1999
• Status: Expired due to Term

• Current Assignee: TARGIT A/S
• Original Assignee: TARGIT A/S
• Inventors: Middelfart, Morten
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): Nguyen, Cindy
• Application Number:
  US09/869,316
• Time in Patent Office: 1,015 Days
• Field of Search: 707/3, 707/4, 707/5, 707/2
• US Class Current: 707/718
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

An apparatus and a method of processing queries to a relational database stored on a computer readable medium including a representation of relations between sections in tables in the database. The method includes identifying tables which contain a specified type of data, generating a plurality of queries (e.g., SQL queries) by selecting at least some primary tables from the identified tables, selecting a set of tables, each table in the set being related to a primary table via N relations, and repeating this, N being varied for each repetition, until the set of tables contains the specified data, and selecting an optimal one of the generated queries.

Claims

1. A method of processing queries to a relational database stored on a computer readable medium, said computer readable medium comprising a representation of relations between tables in the database, said method comprising the steps of:

identifying tables which contain data requested by a user;

generating a plurality of queries, in that a set of primary tables is selected from the identified tables, and in that, for each primary table, a set of tables is selected which set is formed by gradually increasing the number of relations maximally used to reach, via said relations, from the primary table to any table included in the set, until the set of tables contains the data requested by the user; and

selecting an optimal one of the plurality of queries by measuring a response time as the time it takes to obtain data in the relational database with a given query, and selecting the query or queries giving rise to the shortest response time as an optimal query.

2. The method according to claim 1, wherein queries from the plurality of queries are selected by selecting the queries in which the maximum number of elements of relations to be used in order to reach the primary table from an arbitrary table in the set of tables containing the specified data, is as small as possible for the plurality of queries.

3. The method according to claim 1, wherein each of the queries selected from the plurality of queries is given a neural value which, for a given query, is updated on the basis of a measurement of a response time for the given query, and one query is selected from the selected queries on the basis of a probability of selecting the query given by the neural values.

4. The method according to claim 3, wherein each section involved in a query is given a weight value which weights the neural values on the basis of the influence which the section has on the response time for queries.

5. The method according to claim 1, wherein the primary table is a fact table and the set of tables is a set of dimension tables.

6. A computer readable medium comprising a program code for performing the method defined in claim 1.

7. An apparatus for processing queries to a relational database according to the method defined in claim 1.