Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2005-10-18
2005-10-18
Wassum, Lihe S (Department: 2167)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06957222
ABSTRACT:
A method, computer program and database system are disclosed for performing an outer join of at least a first table T1 and a second table T2. The join has join conditions. Each of the tables has an associated Star Map, S1 and S2, respectively. Each Star Map includes bitmap entries which have locations indexed by the hash of one or more values associated with one or more join key columns of its associated table. A bitmap entry in a Star Map, if set, indicates the presence of a row in its associated table that has entries in the one or more join key columns that together hash to the location of the bitmap entry. The method, computer program and database system include a) performing one or more Boolean operations using the bitmap entries of the Star Maps S1 and S2 to produce set bitmap entries in a Star Map SJ where there is a corresponding set bitmap entry in S1 and a corresponding set bitmap entry in S2, b) selecting a row from table T1 and hashing the combined entries in the one or more join key columns of the selected T1 row to identify a bitmap entry in SJ, and c) if the identified bitmap entry in SJ is not set, projecting the selected T1 row with a NULL corresponding to data from table T2. If d) the identified bitmap entry in SJ is set, performing the following: d1) if no row in T2 satisfies the join conditions and has entries in its one or more join key columns that together hash to the location of the identified set bitmap entry in SJ, projecting the selected T1 row and a NULL corresponding to data from table T2, d2) otherwise, for each row from T2 that satisfies the join condition and has entries in its one or more join key columns that together hash to the location of the identified set bitmap entry in SJ, projecting the selected T1 row with data from the row from T2, and e) repeating b)-d) for all rows in T1.
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.
Bontempo et al.. Accelerating Indexed Searching, copywright 1997 Miller Freeman Inc., www.dbpd.com/vault/bontempo.htm.
Shum, Parallel Implementations of Exclusion Joins, Proceedings of the Fifth Ieee Symp. on Paralllel and Distributed Processings, 1-4 Dec. 1993, pp. 742-747.
Toyama et al., Hash-Based Symmetric Data Structure and Join Algorithm for OLAP Applications, IEEE Internaional Symposium Proceedings on Database Engineering and Applications, 2-4 Aug. 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.
Baker & Botts LLP
NCR Corporation
Rayyan Susan
Wassum Lihe S
LandOfFree
Optimizing an outer 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 outer 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 outer join operation using a bitmap index... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3474766