Browse Prior Art Database

Dual Run-Length Encoding for Relational Data Base Matrices

IP.com Disclosure Number: IPCOM000047785D
Original Publication Date: 1983-Dec-01
Included in the Prior Art Database: 2005-Feb-08
Document File: 2 page(s) / 40K

Publishing Venue

IBM

Related People

Glickman, D: AUTHOR [+3]

Abstract

This article describes a method for enhancing performance of relational join queries in a relational data base accessing system through runlength encoding (RLE) of the stored data base attributes both vertically, column by column, and horizontally, row by row. For a given set of data bases each record in the file may be encoded in matrix format by setting a "1" bit in the appropriate column locations to produce a set of inverted matrix files. Each matrix is then run-length encoded in the vertical and horizontal directions. Thus, for example, the "Type" file is run-length encoded as follows: (Image Omitted) The relational query: "Which departments sell red items?" is satisfied as the "join" between the data bases "Type" and "Sales" linked on the attribute "Item.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 63% of the total text.

Page 1 of 2

Dual Run-Length Encoding for Relational Data Base Matrices

This article describes a method for enhancing performance of relational join queries in a relational data base accessing system through runlength encoding (RLE) of the stored data base attributes both vertically, column by column, and horizontally, row by row. For a given set of data bases each record in the file may be encoded in matrix format by setting a "1" bit in the appropriate column locations to produce a set of inverted matrix files. Each matrix is then run-length encoded in the vertical and horizontal directions. Thus, for example, the "Type" file is run-length encoded as follows:

(Image Omitted)

The relational query: "Which departments sell red items?" is satisfied as the "join" between the data bases "Type" and "Sales" linked on the attribute "Item." The "Type" data base is entered vertically on the "Color" attribute. Hits are found at displacements 1 and 4 down the column 3. The horizontal RLE is then entered for rows 1 and 4, yielding in both cases Item A. (Note: In this example the "Item" attributes two options could have also been easily examined vertically. However, in the general case where the attribute may have had several hundred options this would become computationally tedious.) The "Sales" matrix is now entered vertically on the "Item" attribute option A. A hit is found with a displacement 1. Hence, the horizontal RLE matrix is entered for row 1 encoding on bits in columns 1-260 un...