US6502089B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Generating restriction queries using tensor representations
Assignee: International Business Machines Corp
•
Filing: 1999-11-17
•
Granted: 2002-12-31
•
Expires: 2019-11-17
Abstract
Abstract Query results and statistics regarding them are generated using a novel representation of an n-attribute relation as an order n relational tensor. Orders of the relational tensor respectively correspond to each of the attributes, and each coordinate along an order relates to a key value of the corresponding attribute. Numeric values are stored in the relational tensor, each numeric value representing a count of tuples having the attribute key values that correspond to the coordinate of the numeric value along the orders of the relational tensor. This storage representation is useful in a variety of contexts for enhancing the performance of a RDBMS system. Specifically, in a first aspect of the invention, a tensor representation can be used to generate statistics for a user query so that the relational database system can determine, from among two candidate approaches, an approach to use in processing the user query based on the statistic. Also, a a data-representing relational tensor can be used to produce results for a restrict operation such as the SQL operations DISTINCT, PROJECTION, EQUALS, LESS THAN, LESS THAN OR EQUAL, GREATER THAN, GREATER THAN OR EQUAL and LIKE.
Inventors
- 👤 Lance Christopher Amundsen
- 👤 Robert Joseph Bestgen
- 👤 Richard Dale Hoffman
- 👤 Daniel Virgil Toft
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 21:08
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2452; G06F16/24528; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933
Claims Analysis
Total Claims: 46
Claim 1
Independent Claim
115 words
A method of performing a query in a relational database system, comprising: storing a relation comprising a plurality of tuples formed over a plurality of attributes, in a multi-order relational tensor, wherein orders of said multi-order relational tensor correspond to individual attributes, and coordinates along an order of said multi-order relational tensor correspond to values of the corresponding attribute, and numeric values at coordinate locations within said multi-order relational tensor represent a count of tuples in said relation having the attribute values that correspond to the coordinates of the numeric value along the orders of the multi-order relational tensor, and performing the query in the memory of a computer system using the multi-order relational tensor.
Claim 2
Independent Claim
115 words
A method of performing a query in a relational database system, comprising: storing a relation comprising a plurality of tuples formed over a plurality of attributes, in a multi-order relational tensor, wherein orders of said multi-order relational tensor correspond to individual attributes, and coordinates along an order of said multi-order relational tensor correspond to values of the corresponding attribute, and numeric values at coordinate locations within said multi-order relational tensor represent a count of tuples in said relation having the attribute values that correspond to the coordinates of the numeric value along the orders of the multi-order relational tensor, and performing the query in the memory of a computer system using the multi-order relational tensor.
Claim 3
Dependent Claim
15 words
The method of claim 1 wherein said query comprises a restriction query having a criterion.
Claim 4
Dependent Claim
38 words
The method of claim 2 wherein said query comprises a query having operations selected from the group of SQL operations including DISTINCT, PROJECTION, EQUALS, LESS THAN, LESS THAN OR EQUAL, GREATER THAN, GREATER THAN OR EQUAL and LIKE.
Claim 5
Dependent Claim
41 words
The method of claim 2 wherein performing said query comprises: forming a relational selection tensor representing the criterion of the restriction query, and forming a relational tensor product of said relational selection tensor and said multi-order relational tensor storing said relation.
Claim 6
Dependent Claim
30 words
The method of claim 4 wherein forming a relational selection tensor comprises building said relational selection tensor from a plurality of criteria derived from the criterion of said restriction query.
Claim 7
Dependent Claim
55 words
The method of claim 5 wherein building said relational selection tensor comprises: forming intermediate relational selection tensors representing each of said plurality of criteria, and forming a relational tensor product of the intermediate relational selection tensors to form said relational selection tensor representing the plurality of criteria derived from the criterion of the restriction query.
Claim 8
Dependent Claim
38 words
The method of claim 4 wherein said relational selection tensor is a relational tensor having orders that are compatible with orders in said multi-order relational tensor storing said relation, and holding only numeric values of one or zero.
Claim 9
Dependent Claim
50 words
The method of claim 7 wherein said relational selection tensor holds a numeric value of one in those coordinates corresponding to tuple values meeting the criterion in the query, and holds a numeric value of zero in those coordinates corresponding to tuple values not meeting the criterion in the query.
Claim 10
Dependent Claim
39 words
The method of claim 4 wherein the relational tensor product of two relational tensors, is formed by multiplying numeric values in corresponding coordinates of the relational tensors to produce numeric values for that coordinate in a resulting relational tensor.
Claim 11
Dependent Claim
50 words
The method of claim 9 wherein the relational tensors operated upon by the relational tensor product do not have complete correspondence in the domain of coordinates of the relational tensors along each of their orders, and wherein forming the relational tensor product further comprises accommodating relational tensors with mismatched domains.
Claim 12
Dependent Claim
53 words
The method of claim 4 wherein orders of said relational selection tensor are expanded to match those of said multi-order relational tensor, by adding a needed order to the relational selection tensor and associating each coordinate value in the added order with a replica of the existing orders of the relational selection tensor.
Claim 13
Dependent Claim
69 words
The method of claim 11 wherein the domains of coordinates along the orders of said relational selection tensor are matched with the domains of coordinates along the orders of said multi-order relational tensor, by identifying any coordinates in an order of the relational selection tensor not found in the corresponding order of the multi-order relational tensor, and adding any such coordinates to the order of the second relational tensor.
Claim 14
Dependent Claim
22 words
The method of claim 12 wherein zero values are placed in all locations of said relational selection tensor corresponding to added coordinates.
Claim 15
Dependent Claim
69 words
The method of claim 4 wherein the domains of coordinates along the orders of said multi-order relational tensor are matched with the domains of coordinates along the orders of said relational selection tensor, by identifying any coordinates on an order of the multi-order relational tensor not found in the corresponding order of the relational selection tensor, and adding any such coordinates to the order of the relational selection tensor.
Claim 16
Dependent Claim
54 words
The method of claim 4 adapted to perform a restrict operation requesting return of only unique values in one or more particular attribute of tuples matching a query, further comprising: normalizing a result of said relational tensor product, by replacing all non-zero values in all locations in said result with a value of one.
Claim 17
Dependent Claim
14 words
The method of claim 1 wherein said query includes an SQL SELECT DISTINCT operation.
Claim 18
Dependent Claim
14 words
The method of claim 1 wherein said query includes an SQL SELECT LIKE operation.
Claim 19
Dependent Claim
45 words
The method of claim 4 adapted to perform a restrict operation requesting return of only one or more attributes of tuples matching a query, further comprising: contracting a result of said tensor product along all orders than those corresponding to the attributes to be returned.
Claim 20
Dependent Claim
13 words
The method of claim 18 wherein said query includes an SQL PROJECTION operation.
Claim 21
Independent Claim
133 words
An apparatus for performing a query in a relational database system, comprising: a data storage device, wherein the data storage device stores a relational database, the relational database comprising one or more relations, each relation comprising one or more tuples on one or more attributes, the relational database including a multi-order relational tensor, wherein orders of said multi-order relational tensor correspond to individual attributes, and coordinates along an order of said multi-order relational tensor correspond to values of the corresponding attribute, and numeric values at coordinate locations within said multi-order relational tensor represent a count of tuples in a relation having the attribute values that correspond to the coordinates of the numeric value along the orders of the multi-order relational tensor, and a processor executing the query using the stored multi-order relational tensor.
Claim 22
Independent Claim
133 words
An apparatus for performing a query in a relational database system, comprising: a data storage device, wherein the data storage device stores a relational database, the relational database comprising one or more relations, each relation comprising one or more tuples on one or more attributes, the relational database including a multi-order relational tensor, wherein orders of said multi-order relational tensor correspond to individual attributes, and coordinates along an order of said multi-order relational tensor correspond to values of the corresponding attribute, and numeric values at coordinate locations within said multi-order relational tensor represent a count of tuples in a relation having the attribute values that correspond to the coordinates of the numeric value along the orders of the multi-order relational tensor, and a processor executing the query using the stored multi-order relational tensor.
Claim 23
Dependent Claim
15 words
The apparatus of claim 20 wherein said query comprises a restriction query having a criterion.
Claim 24
Dependent Claim
38 words
The apparatus of claim 21 wherein said query comprises a query having operations selected from the group of SQL operations including DISTINCT, PROJECTION, EQUALS, LESS THAN, LESS THAN OR EQUAL, GREATER THAN, GREATER THAN OR EQUAL and LIKE.
Claim 25
Dependent Claim
43 words
The apparatus of claim 21 wherein said processor performs said query by forming a relational selection tensor representing the criterion of the restriction query, and forming a relational tensor product of said relational selection tensor and said multi-order relational tensor storing said relation.
Claim 26
Dependent Claim
30 words
The apparatus of claim 23 wherein forming a relational selection tensor comprises building said relational selection tensor from a plurality of criteria derived from the criterion of said restriction query.
Claim 27
Dependent Claim
55 words
The apparatus of claim 24 wherein building said relational selection tensor comprises: forming intermediate relational selection tensors representing each of said plurality of criteria, and forming a relational tensor product of the intermediate relational selection tensors to form said relational selection tensor representing the plurality of criteria derived from the criterion of the restriction query.
Claim 28
Dependent Claim
38 words
The apparatus of claim 23 wherein said relational selection tensor is a relational tensor having orders that are compatible with orders in said multi-order relational tensor storing said relation, and holding only numeric values of one or zero.
Claim 29
Dependent Claim
50 words
The apparatus of claim 26 wherein said relational selection tensor holds a numeric value of one in those coordinates corresponding to tuple values meeting the criterion in the query, and holds a numeric value of zero in those coordinates corresponding to tuple values not meeting the criterion in the query.
Claim 30
Dependent Claim
40 words
The apparatus of claim 23 wherein the relational tensor product of two relational tensors, tensor, is formed by multiplying numeric values in corresponding coordinates of the relational tensors to produce numeric values for that coordinate in a resulting relational tensor.
Claim 31
Dependent Claim
50 words
The apparatus of claim 28 wherein the relational tensors operated upon by the relational tensor product do not have complete correspondence in the domain of coordinates of the relational tensors along each of their orders, and wherein forming the relational tensor product further comprises accommodating relational tensors with mismatched domains.
Claim 32
Dependent Claim
53 words
The apparatus of claim 23 wherein orders of said relational selection tensor are expanded to match those of said multi-order relational tensor, by adding a needed order to the relational selection tensor and associating each coordinate value in the added order with a replica of the existing orders of the relational selection tensor.
Claim 33
Dependent Claim
69 words
The apparatus of claim 30 wherein the domains of coordinates along the orders of said relational selection tensor are matched with the domains of coordinates along the orders of said multi-order relational tensor, by identifying any coordinates in an order of the relational selection tensor not found in the corresponding order of the multi-order relational tensor, and adding any such coordinates to the order of the second relational tensor.
Claim 34
Dependent Claim
22 words
The apparatus of claim 31 wherein zero values are placed in all locations of said relational selection tensor corresponding to added coordinates.
Claim 35
Dependent Claim
69 words
The apparatus of claim 23 wherein the domains of coordinates along the orders of said multi-order relational tensor are matched with the domains of coordinates along the orders of said relational selection tensor, by identifying any coordinates on an order of the multi-order relational tensor not found in the corresponding order of the relational selection tensor, and adding any such coordinates to the order of the relational selection tensor.
Claim 36
Dependent Claim
51 words
The apparatus of claim 23 performing a restrict operation requesting return of only unique values in one or more particular attribute of tuples matching a query, said processor normalizing a result of said tensor product, by replacing all non-zero values in all locations in said result with a value of one.
Claim 37
Dependent Claim
14 words
The apparatus of claim 34 wherein said query includes an SQL SELECT DISTINCT operation.
Claim 38
Dependent Claim
14 words
The apparatus of claim 34 wherein said query includes an SQL SELECT LIKE operation.
Claim 39
Dependent Claim
43 words
The apparatus of claim 20 performing a restrict operation requesting return of only one or more attributes of tuples matching a query, said processor contracting a result of said tensor product along all orders than those corresponding to the attributes to be returned.
Claim 40
Dependent Claim
13 words
The apparatus of claim 37 wherein said query includes an SQL PROJECTION operation.
Claim 41
Dependent Claim
126 words
A program product comprising: a relational database comprising one or more relations, each relation comprising one or more tuples on one or more attributes, the relational database comprising a multi-order relational tensor, wherein orders of said multi-order relational tensor correspond to individual attributes, and coordinates along an order of said multi-order relational tensor correspond to values of the corresponding attribute, and numeric values at coordinate locations within said multi-order relational tensor represent a count of tuples in a relation having the attribute values that correspond to the coordinates of the numeric value along the orders of the multi-order relational tensor, a relational database system adapted to retrieve data from said relational database, and signal bearing media bearing the multi-order relational tensor and the relational database system.
Claim 42
Dependent Claim
126 words
A program product comprising: a relational database comprising one or more relations, each relation comprising one or more tuples on one or more attributes, the relational database comprising a multi-order relational tensor, wherein orders of said multi-order relational tensor correspond to individual attributes, and coordinates along an order of said multi-order relational tensor correspond to values of the corresponding attribute, and numeric values at coordinate locations within said multi-order relational tensor represent a count of tuples in a relation having the attribute values that correspond to the coordinates of the numeric value along the orders of the multi-order relational tensor, a relational database system adapted to retrieve data from said relational database, and signal bearing media bearing the multi-order relational tensor and the relational database system.
Claim 43
Dependent Claim
14 words
The program product of claim 39 wherein the signal bearing media comprises transmission media.
Claim 44
Dependent Claim
14 words
The program product of claim 40 wherein the signal bearing media comprises recordable media.
Claim 45
Dependent Claim
124 words
A memory for storing data for access by a relational database system, the relational database system retrieving data from a relational database stored at least partially in said memory, the relational database comprising one or more relations, each relation comprising one or more tuples on one or more attributes, the memory comprising: a multi-order relational tensor, wherein orders of said multi-order relational tensor correspond to individual attributes, and coordinates along an order of said multi-order relational tensor correspond to values of the corresponding attribute, and numeric values at coordinate locations within said multi-order relational tensor represent a count of tuples in a relation having the attribute values that correspond to the coordinates of the numeric value along the orders of the multi-order relational tensor.
Claim 46
Dependent Claim
124 words
A memory for storing data for access by a relational database system, the relational database system retrieving data from a relational database stored at least partially in said memory, the relational database comprising one or more relations, each relation comprising one or more tuples on one or more attributes, the memory comprising: a multi-order relational tensor, wherein orders of said multi-order relational tensor correspond to individual attributes, and coordinates along an order of said multi-order relational tensor correspond to values of the corresponding attribute, and numeric values at coordinate locations within said multi-order relational tensor represent a count of tuples in a relation having the attribute values that correspond to the coordinates of the numeric value along the orders of the multi-order relational tensor.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-12-30 | 2006-07-01 | 2006-12-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-12-30 | 2010-07-01 | 2010-12-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-12-30 | 2014-07-01 | 2014-12-31 | $7700.00 | Window Closed / Lapsed |