Abstract:
Provided is a solution for storing data, the data comprising a set of tables, each table comprising a set of columns, each column comprising a set of values, each value being one or more data types. In the solution, a binary tree can be created for each of the data types. Each binary tree can comprise a set of nodes. A set of arrays can be associated with each node of the binary tree. The array associated with each node of each binary tree can correspond to one of the columns that comprises the value of the data type represented by the node of the binary tree. Each array can indicate at least one table row and column from the plurality of tables in which the value of the data type represented by the node of the binary tree occurs.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of European Patent Application No. 08100528.2 filed 16 Jan. 2008, entitled “AVOIDING DATABASE RELATED JOINS WITH SPECIALIZED INDEX STRUCTURES”, which is assigned to the assignee of the present application, and the teachings of which are hereby incorporated by reference in their entirety. 
     BACKGROUND 
     The present invention relates to data processing and more specifically to data structures in data processing systems. 
     In a relational database, data is stored in different tables. These tables may be bound together using referential integrity. For instance, data may be split into fact and dimension tables. The dimension tables define different key/value tuples with unique keys and descriptive values. The fact tables then reference this information. 
     Where tables reference other tables, the time taken for query execution is not optimal. Joins between tables increase the amount of processing required for a query. 
     Hybrid tree array databases have been contemplated. Such a database provides flexibility, allowing fast key searching typical of a tree database, and sequential searching of all data fields typical of an array database. It does not, however, address the problem of querying data stored over joined relational database tables. 
     SUMMARY 
     According to an embodiment of the present invention, there is provided a method of storing data. The data comprises a set of tables, each table comprising a set of columns, each column comprising a set of values, each value being one or more data types. In the solution, a binary tree can be created for each of the data types. Each binary tree can comprise a set of nodes. A set of arrays can be associated with each node of the binary tree. The array associated with each node of each binary tree can correspond to one of the columns that comprise the value of the data type represented by the node of the binary tree. Each array can indicate at least one table row and column from the plurality of tables in which the value of the data type represented by the node of the binary tree occurs. 
     According to an embodiment of the present invention, there is provided a computer program product. The computer program product includes software code portions for performing a method in accordance with an embodiment of the present invention when the program is run on a data processing system. 
     According to an embodiment of the present invention, there is provided a data processing system for storing data. The data comprises a set of tables, each table comprising a set of columns, each column comprising a set of values, each value being one or more data types. In the solution, a binary tree can be created for each of the data types. Each binary tree can comprise a set of nodes. A set of arrays can be associated with each node of the binary tree. The array associated with each node of each binary tree can correspond to one of the columns that comprise the value of the data type represented by the node of the binary tree. Each array can indicate at least one table row and column from the plurality of tables in which the value of the data type represented by the node of the binary tree occurs. 
     According to an embodiment of the present invention, there is provided a data structure. The data structure stores data. The data comprises a set of tables, each table comprising a set of columns, each column comprising a set of values, each value being one or more data types. In the solution, a binary tree can be created for each of the data types. Each binary tree can comprise a set of nodes. A set of arrays can be associated with each node of the binary tree. The array associated with each node of each binary tree can correspond to one of the columns that comprise the value of the data type represented by the node of the binary tree. Each array can indicate at least one table row and column from the plurality of tables in which the value of the data type represented by the node of the binary tree occurs. 
    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
         FIG. 1  shows a block diagram of a data processing system. 
         FIG. 2  shows a flow diagram illustrating steps performed in a method of storing data. 
         FIG. 3  shows tables containing data. 
         FIG. 4  shows a binary tree. 
         FIG. 5  shows a binary tree. 
         FIGS. 6-8  show tables containing data. 
         FIGS. 9-13  show steps involved in the execution of a query. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1  shows a block diagram of a data processing system  100 . The data processing system  100  includes microprocessor  102 , memory  104 , auxiliary storage interface  106 , terminal interface  108 , and network interface  110 . These components may be interconnected through the use of a system bus. Auxiliary storage interface  106  may be used to connect mass storage devices which store data to the data processing system  100 . 
     Memory  104  contains an operating system  112 , an application program  114 , and data structure  116 . Data structure  116  is used to provide data storage that avoids the problems caused by joins between tables. Methods for creating and querying data structure  116  are described below. Data processing system  100  can utilize well known virtual addressing mechanisms that allow programs of data processing system  200  to behave as if they only have access to a large, single storage entity instead of accessing multiple, smaller storage entities such as memory  104 , and any mass storage devices connected via auxiliary storage interface  106 . Therefore, while operating system  112 , application  114  and data structure  116  are shown to reside in memory  104 , those skilled in the art will recognize that these programs are not necessarily all completely contained in memory  104  at the same time. It should also be noted that the term memory is used here to generically refer to the entire virtual memory of data processing system  100 . 
     Although data processing system  100  is shown to contain only a single main microprocessor, those skilled in the art will appreciate that the present invention may be practiced using a data processing system that has multiple microprocessors, and/or multiple busses. 
     Terminal interface  108  is used to directly connect one or more terminals to data processing system  200 . These terminals may be non-intelligent or fully programmable workstations, and are used to allow system administrators and users to communicate with data processing system  100 . 
     Network interface  110  is used to connect other computer systems and/or workstations to data processing system  100  in networked fashion. For instance, the network interface can include a connection to the internet and the World Wide Web, or internal web-based systems (typically called intranets). The present invention applies equally no matter how data processing system  100  may be connected to other computer systems and/or workstations, regardless of whether the connection is made using present day analogue and/or digital techniques or via some networking mechanisms of the future. 
     Operating system  112  can be any operating system, such as windows, AIX etc., and those skilled in the art will appreciate that the spirit and scope of the present invention is not limited to any one operating system. 
     Application program  114  can be any type of application program which accesses data stored in data structure  116 . Thus, the application could include a computerized catalogue, process documentation, inventory, personal lists, or data warehouses to name several examples. 
       FIG. 2  shows a method  200  for storing data from relational data tables in a binary tree. In step  202 , a binary tree is created for each data type. Data types include, for instance, integer, character, string, and other data types known to those skilled in the art. In step  204 , an array is associated with each node of the binary tree. The array associated with each node of the binary tree indicates where the value of the data type corresponding to the node of the binary tree occurs in the original relational table. In step  205 , data is loaded from relational database systems into these tree structures where each different value occurrence results in a new tree node. Each tree node stores the information where the value was original existing in the relational database table as RowID value. In step  206 , index tables are created from the original relational tables containing the indexes of the nodes on the binary tree having the value contained in that location of the original relational data table. 
     Methods consistent with the invention are described below with reference to an example given in  FIG. 3 . 
       FIG. 3  shows relational data tables  300  and  310 . Table  300  contains data relating to products, and table  310  contains data relating to product groups. The column [GroupID] in table  300  references the column [ID] in table  310 . Thus, a join between tables  300  and  310  is defined. 
       FIG. 4  shows a binary tree created from tables  300  and  310  for the data type integer. Binary tree  400  has nodes  402 ,  404 ,  406 ,  408 , and  410 . The nodes have indices  412 ,  414 ,  416 ,  418 , and  420 . Associated with each node are arrays (one per column of the set of columns of the data type, represented by the tree) containing data indicative of where the value of the node occurred in the tables  300  and  310 . 
       FIG. 5  shows a binary tree  500  for the data type string. Binary tree  500  has nodes  502 ,  504 ,  506 , and  508 . The nodes on binary tree  500  have indices  512 ,  514 ,  516  and  518 . 
       FIG. 6  shows three arrays associated with node  406  of binary tree  400 . Table  600  (representing the three arrays as columns) indicates where the value of node  406  (which is  300 ) occurred in tables  300  and  310 . Table  600  shows the row ID where the value  300  occurs in the columns of tables  300  and  310 . 
       FIG. 7  shows an index table created showing the indices where the values of binary tree  400  occurred in table  300 . 
       FIG. 8  shows an index table showing the indices where the values in table  310  occur in binary trees  400  and  500 . 
     The execution of a query on a data structure consistent with an embodiment of the present invention is described below with reference to  FIGS. 9-13 . 
     The query used as an example here is the determination of the all the product prices for products in the product group toys. The first step as shown in  FIG. 9  involves finding the node in the tree  500  containing the searched value toys. This is node  506 . The array associated with node  506 , denoted by  906  in  FIG. 9  is then accessed to determine the row ID of the index table product group which corresponds to the string value toys. 
       FIG. 10  shows this lookup in index table  800  with the row ID  2  and the value index for the [NAME] as well as for [ID] index is 2. 
       FIG. 11  shows the lookup of the index in the tree  400  corresponding to the product [ID] which in turn corresponds to the product group name ‘toys’. Once this index is known, tree  400  can be accessed directly via this index to determine the product IDs from the table corresponding to the index  2 . 
       FIG. 12  shows the node  406 , representing the index  2  and having the value  300  within the tree  400 . This returns all row ID for the column [GroupID] within the product table  600 . The column product [ID] of table  600  thus returns the row IDs of the required products. 
       FIG. 13  shows the lookup in table  700  of the prices for the products having the row ID numbers determined from table  600 . Thus a list of products can be generated without any further index or data scan. 
     Embodiments of the invention may be implemented as an accelerator for an existing database system. The methods and systems described herein may be part of a database system in addition to relational database tables. Part of the data may be kept in a mainframe, and parts may be off loaded to non-mainframe systems such as blades where the memory costs are reduced. Queries and searches may be split between the accelerator and a relational database system. Parts of an access graph may be processed using the methods and systems described above, with other parts processed using other techniques. 
     The invention can take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment containing both hardware and software elements. In one embodiment, the invention is implemented in software which includes but is not limited to firmware, resident software, microcode, etc. 
     Furthermore, the invention can take the form of a computer program product accessible from a computer usable, or computer readable medium providing program code for use by or in connection with a computer or any instruction execution system. For the purposes of this description, a computer usable or computer readable medium can be any apparatus that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device. 
     The medium can be an electronic, magnetic, optical, electromagnetic, infrared or semiconductor system (or apparatus or device) or a propagation medium. Examples of a computer readable medium include a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory, a read only memory, a rigid magnetic disc and an optical disc. Current examples of optical discs include compact disc read only memory, compact disc read/write, and DVD. 
     A data processing system suitable for storing and/or executing program code will include at least one processor coupled directly or indirectly to memory elements through a system bus. The memory elements can include local memory employed during execution of the program code bulk storage and cache memories which provide temporary storage of at least some program code in order to reduce the number of times code must be retrieved from bulk storage during execution. 
     Input/output or I/O devices (including but not limited to keyboards, displays, pointing devices, etc) can be coupled to the system directly or through intervening I/O controllers. 
     Network adapters may also be coupled to the system to enable the data processing system to become coupled to other data processing systems or remote printers or storage devices through intervening private or public networks. Modems, cable modems, and Ethernet cards are just a few of the currently available types of network adapters.