Generating restriction queries using tensor representations

• US 6,502,089 B1
• Filed: 11/17/1999
• Issued: 12/31/2002
• Est. Priority Date: 11/17/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bestgen, Robert Joseph, Hoffman, Richard Dale, Amundsen, Lance Christopher, Toft, Daniel Virgil
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): RAYYAN, SUSAN F
• Application Number:
  US09/441,818
• Time in Patent Office: 1,140 Days
• Field of Search: 707/10, 707/3, 707/4, 707/200, 707/2, 709/217
• US Class Current: 707/714
• CPC Class Codes: G06F 16/24528 Standardisation; Simplification
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

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.

Claims

1. 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.

2. The method of claim 1 wherein said query comprises a restriction query having a criterion.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. The method of claim 12 wherein zero values are placed in all locations of said relational selection tensor corresponding to added coordinates.

14. 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.

15. 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.

16. The method of claim 1 wherein said query includes an SQL SELECT DISTINCT operation.

17. The method of claim 1 wherein said query includes an SQL SELECT LIKE operation.

18. 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.

19. The method of claim 18 wherein said query includes an SQL PROJECTION operation.

20. 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.

21. The apparatus of claim 20 wherein said query comprises a restriction query having a criterion.

22. 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.

23. 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.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

31. 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.

32. The apparatus of claim 31 wherein zero values are placed in all locations of said relational selection tensor corresponding to added coordinates.

33. 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.

34. 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.

35. The apparatus of claim 34 wherein said query includes an SQL SELECT DISTINCT operation.

36. The apparatus of claim 34 wherein said query includes an SQL SELECT LIKE operation.

37. 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.

38. The apparatus of claim 37 wherein said query includes an SQL PROJECTION operation.

39. 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.

40. The program product of claim 39 wherein the signal bearing media comprises transmission media.

41. The program product of claim 40 wherein the signal bearing media comprises recordable media.

42. 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.