Optimizing an exclusion join operation using a bitmap index...

Details Optimizing an exclusion join operation using a bitmap index... Optimizing an exclusion join operation using a bitmap index...

2005-10-18

2005-10-18

Robinson, Greta (Department: 2167)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

06957210

ABSTRACT:
A method, computer program and database system are disclosed for performing an exclusion join of at least a first table T1and a second table T2, where each of the tables has an associated Star Map, S1and S2, respectively. Each Star Map includes bitmap entries having locations indexed by the hash of one or more values associated with one or more join key columns of its associated table. The method, computer program, and database system include a) performing one or more Boolean operations using the bitmap entries of the Star Maps S1and S2to produce bitmap entries in a Star Map SJ where there is a corresponding set bitmap entry in S1and no corresponding set bitmap entry in S2; b) using SJ to identify qualifying rows from the first table T1; and c) providing the qualifying rows as an exclusion join result.

REFERENCES:
patent: 5426760 (1995-06-01), Moreland
patent: 5706495 (1998-01-01), Chadha et al.
patent: 5781896 (1998-07-01), Dalal
patent: 5787435 (1998-07-01), Burrows
patent: 5802521 (1998-09-01), Ziauddin et al.
patent: 5873074 (1999-02-01), Kashyap et al.
patent: 5905985 (1999-05-01), Malloy et al.
patent: 5937408 (1999-08-01), Shoup et al.
patent: 5953723 (1999-09-01), Linoff et al.
patent: 5960428 (1999-09-01), Lindsay et al.
patent: 5960434 (1999-09-01), Schimmel
patent: 5963933 (1999-10-01), Cheng et al.
patent: 5963954 (1999-10-01), Burrows
patent: 6049804 (2000-04-01), Burgess et al.
patent: 6088691 (2000-07-01), Bhargava et al.
patent: 6105020 (2000-08-01), Lindsay et al.
patent: 6397204 (2002-05-01), Liu et al.
patent: 6446063 (2002-09-01), Chen et al.
patent: 6484159 (2002-11-01), Mumick et al.
patent: 6606638 (2003-08-01), Tarin
patent: 6618729 (2003-09-01), Bhashyam et al.
patent: 6684203 (2004-01-01), Waddington et al.
Shum, Parallel Implementations of Exclusion Joins, Proceedings of the Fifth IEEE Symp. on Parallel and Distributed Processings, Dec. 1-4, 1993, pp. 742-747.
Toyama et al., Hash-Based Symmetric Data Structure and Join Algorithm for OLAP Applications, IEEE International Symposium Proceedings on Database Engineering and Applications, Aug. 2-4, 1999, pp. 231-238.
Johnson, Relational Database Structure: Links, Joins and Normalization, <http://acl.arts.usyd.edu.au/VISTA/14-relational_databases/detailed_example.htm> pp. 1-5, Sep. 29, 1999.
Bontempo et al. , Accelerating Indexed Searching, copywright 1997 Miller Freeman Inc., www.dbpd.com/vault/bontempo.htm.

Affiliated with

Also associated with

Rating

Optimizing an exclusion join operation using a bitmap index... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Optimizing an exclusion join operation using a bitmap index..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimizing an exclusion join operation using a bitmap index... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3491883