Generating join queries using tensor representations

• US 6,564,204 B1
• Filed: 04/14/2000
• Issued: 05/13/2003
• Est. Priority Date: 04/14/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Driesch, Robert Douglas Jr., Toft, Daniel Virgil, Bestgen, Robert Joseph, Abdo, Abdo Esmail, Amundsen, Lance Christopher
• Primary Examiner(s): Corrielus, Jean M.
• Assistant Examiner(s): Liang, Gwen
• Application Number:
  US09/549,845
• Time in Patent Office: 1,124 Days
• Field of Search: 707/3, 707/5, 707/2, 707/102, 707/4, 713/193
• US Class Current: 707/714
• CPC Class Codes: G06F 16/2456 Join operations
• 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

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, a data-representing relational tensor can be used to produce results for join operations such as the SQL operations JOIN, LEFT OUTER JOIN, RIGHT OUTER JOIN and FULL OUTER JOIN.

Claims

1. A method of performing a join query in a relational database system by combining a first and a second relation each comprising a plurality of tuples formed over a plurality of attributes including a common attribute, comprising:

storing said first and second relations in respective first and second relational tensors each having one or more orders, wherein an order of a relational tensor corresponds to an attribute of a relation represented by the relational tensor, and coordinates along an order of a relational tensor correspond to values of the corresponding attribute, and numeric values at coordinate locations within said relational tensor represent a count of tuples in said relation having the attribute values that correspond to the coordinate(s) of the numeric value along the order(s) of the relational tensor, and

combining numeric values at matching coordinates in said first and second relational tensors to produce a result relational tensor having attributes found in said first and second relations.

2. The method of claim 1 wherein combining numeric values in said first and second relational tensors comprises expanding said first relational tensor to conform to said second relational tensor by modifying said first relational tensor to include orders of said second relational tensor not found in said first relational tensor.

3. The method of claim 2 wherein combining numeric values in said first and second relational tensors further comprises expanding said second relational tensor to conform to said first relational tensor by modifying said second relational tensor to include orders of said first relational tensor not found in said second relational tensor.

4. The method of claim 3 wherein combining numeric values in said first and second relational tensors further comprises forming a relational tensor product of said expanded first and second relational tensors.

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

6. The method of claim 5 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.

7. The method of claim 1 wherein combining numeric values in said first and second relational tensors comprises matching the domains of coordinates along orders of said first relational tensor with the domains of coordinates along the orders of said second relational tensor, by identifying any coordinates in an order of the second relational tensor not found in the corresponding order of the first relational tensor, and adding any such coordinates to the order of the first relational tensor.

8. The method of claim 7 wherein zero values are placed in all locations of said first relational tensor corresponding to added coordinates.

9. The method of claim 7 wherein combining numeric values in said first and second relational tensors further comprises adding null coordinate values to orders of said first relational tensor not found in said second relational tensor.

10. The method of claim 9 wherein combining numeric values in said first and second relational tensors further comprises inserting values of zero or one in all locations of said first relational tensor corresponding to said null coordinate values.

11. The method of claim 9 wherein combining numeric values in said first and second relational tensors further comprises expanding said second relational tensor to conform to said first relational tensor by modifying said second relational tensor to include orders of said first relational tensor not found in said second relational tensor.

12. The method of claim 11 wherein combining numeric values in said first and second relational tensors further comprises forming a relational tensor product of said expanded first and second relational tensors.

13. The method of claim 12 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.

14. The method of claim 13 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.

15. The method of claim 9 wherein combining numeric values in said first and second relational tensors further comprises matching the domains of coordinates along orders of said second relational tensor with the domains of coordinates along the orders of said expanded first relational tensor, by identifying any coordinates in an order of the first relational tensor not found in the corresponding order of the second relational tensor, and adding any such coordinates to the order of the second relational tensor.

16. The method of claim 15 wherein zero values are placed in all locations of said second relational tensor corresponding to added coordinates.

17. The method of claim 15 wherein combining numeric values in said first and second relational tensors further comprises forming a relational tensor product of said expanded first and second relational tensors.

18. The method of claim 17 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.

19. An apparatus for performing a join query in a relational database system, comprising:

a data storage device, wherein the data storage device stores a relational database, the relational database comprising two or more relations, each relation comprising one or more tuples on one or more attributes including a common attribute,

the relational database including first and second relational tensors, wherein orders of said relational tensors correspond to individual attributes, and coordinates along an order of said relational tensors correspond to values of the corresponding attribute, and numeric values at coordinate locations within said relational tensors 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 relational tensors, and

a processor performing the join query by combining numeric values at matching coordinates in said first and second relational tensors to produce a result relational tensor having attributes found in said first and second relations.

20. A program product comprising:

a relational database comprising two or more relations, each relation comprising one or more tuples on one or more attributes including a common attribute, the relational database comprising two or more multi-order relational tensors, wherein orders of said relational tensors correspond to individual attributes, and coordinates along an order of said relational tensors correspond to values of the corresponding attribute, and numeric values at coordinate locations within said 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 relational tensor,

relational database system adapted to retrieve data from said relational database, and perform a join query by combining numeric values at matching coordinates in said first and second relational tensors to produce a result relational tensor having attributes found in said first and second relations, and,

signal bearing media bearing the relational tensor and the relational database system.

21. The program product of claim 20 wherein the signal bearing media comprises transmission media.

22. The program product of claim 20 wherein the signal bearing media comprises recordable media.