公开(公告)号：US06195656B1

公开(公告)日：2001-02-27

申请号：US09311171

申请日：1999-05-13

申请人： Cetin Ozbutun ,  Jeffrey I. Cohen ,  Hakan Jakobsson ,  Mark Kremer ,  Michael Depledge ,  Quoc Tai Tran ,  Alexander C. Ho ,  Julian Hyde

发明人： Cetin Ozbutun ,  Jeffrey I. Cohen ,  Hakan Jakobsson ,  Mark Kremer ,  Michael Depledge ,  Quoc Tai Tran ,  Alexander C. Ho ,  Julian Hyde

IPC分类号： G06F1730

CPC分类号： G06F17/30324 ,  G06F17/3061 ,  Y10S707/99931 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99937

摘要： A method and apparatus for segmenting bitmaps in a bitmap index is provided. A segmented bitmap includes a plurality of bitmap segments that are used to indicate which records in a body of records that is associated with the segmented bitmap satisfy a particular criteria. Each bitmap segment contains a string of bits that correspond to a corresponding range of records in the body of records. There may be gaps between the ranges represented by the bitmap segments when, for example, the body of records does not contain records in a particular range. For the purposes of retrieval, compression, de-compression, locking and logging, the database system treats each bitmap segment as a distinct data item.

公开(公告)号：US6067540A

公开(公告)日：2000-05-23

申请号：US808584

申请日：1997-02-28

申请人： Cetin Ozbutun ,  Jeffrey I. Cohen ,  Hakan Jakobsson ,  Mark Kremer ,  Michael Depledge ,  Quoc Tai Tran ,  Alexander C. Ho ,  Julian Hyde

发明人： Cetin Ozbutun ,  Jeffrey I. Cohen ,  Hakan Jakobsson ,  Mark Kremer ,  Michael Depledge ,  Quoc Tai Tran ,  Alexander C. Ho ,  Julian Hyde

IPC分类号： G06F17/30

CPC分类号： G06F17/30324 ,  G06F17/3061 ,  Y10S707/99931 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99937

摘要： A method and apparatus for segmenting bitmaps in a bitmap index is provided. A segmented bitmap includes a plurality of bitmap segments that are used to indicate which records in a body of records that is associated with the segmented bitmap satisfy a particular criteria. Each bitmap segment contains a string of bits that correspond to a corresponding range of records in the body of records. There may be gaps between the ranges represented by the bitmap segments when, for example, the body of records does not contain records in a particular range. For the purposes of retrieval, compression, de-compression, locking and logging, the database system treats each bitmap segment as a distinct data item.

摘要翻译： 提供了一种用于分割位图索引中的位图的方法和装置。 分段位图包括多个位图段，其用于指示与分段位图相关联的记录体中的哪些记录满足特定标准。 每个位图片段都包含一个比特串，它们对应于记录主体中对应的记录范围。 当例如记录体不包含特定范围内的记录时，位图段所表示的范围之间可能存在间隙。 为了检索，压缩，解压缩，锁定和记录的目的，数据库系统将每个位图段视为不同的数据项。

公开(公告)号：US6141656A

公开(公告)日：2000-10-31

申请号：US807429

申请日：1997-02-28

申请人： Cetin Ozbutun ,  Jeffrey I. Cohen ,  Michael Depledge ,  Julian Hyde ,  Hakan Jakobsson ,  Mark Kremer ,  Quoc Tai Tran

发明人： Cetin Ozbutun ,  Jeffrey I. Cohen ,  Michael Depledge ,  Julian Hyde ,  Hakan Jakobsson ,  Mark Kremer ,  Quoc Tai Tran

IPC分类号： G06F17/30

CPC分类号： G06F17/30324 ,  G06F17/30495 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99942

摘要： A method for performing logical operations on bitmap streams from segmented bitmaps. The logical operations include the AND, OR, and Set Minus operations. One embodiment of the invention performs the logical AND operation on a plurality of bitmap streams by searching for a set of overlapping bitmap segments. The ranges corresponding to the overlap among the overlapping bitmap segments are scanned to generate non-gap results. One embodiment of the invention performs the logical OR operation on a plurality of bitmap streams. To generate a result for a given range, only the bitmap segments overlapping the given range are ORed together. One embodiment of the invention performs a Set Minus between bitmap streams. A set minus is the ANDing of a first condition with the negation of another condition. To generate a set minus result, the ranges corresponding to the gaps in the bitmap associated with the negated condition are ignored.

摘要翻译： 一种从分段位图执行位图流的逻辑运算的方法。 逻辑运算包括AND，OR和Set Minus操作。 本发明的一个实施例通过搜索一组重叠的位图片段来对多个位图流执行逻辑与运算。 对与重叠位图片段之间的重叠相对应的范围被扫描以产生非间隙结果。 本发明的一个实施例对多个位图流执行逻辑或运算。 要为给定范围生成一个结果，只有与给定范围重叠的位图片段被合并在一起。 本发明的一个实施例在位图流之间执行集合减法。 一个减号是第一个条件与否定另一个条件的AND。 为了生成一个减去的结果，忽略与否定条件关联的位图中的间隙对应的范围。

公开(公告)号：US5963935A

公开(公告)日：1999-10-05

申请号：US808586

申请日：1997-02-28

申请人： Cetin Ozbutun ,  Jeffrey I. Cohen ,  Michael Depledge ,  Julian Hyde ,  Hakan Jakobsson ,  Mark Kremer ,  Quoc Tai Tran

发明人： Cetin Ozbutun ,  Jeffrey I. Cohen ,  Michael Depledge ,  Julian Hyde ,  Hakan Jakobsson ,  Mark Kremer ,  Quoc Tai Tran

IPC分类号： G06F17/30

CPC分类号： G06F17/30336 ,  G06F17/30324 ,  G06F17/30495 ,  Y10S707/99932 ,  Y10S707/99933

摘要： A method for combining within memory a limit, a plurality of bitmap streams from bitmaps of indefinite size and number. The bitmap streams are merged into a resulting bitmap which can be used in subsequent logical operations.In order to perform a merge within a memory limit, the method relies on the data compression. When compression by itself may be ineffective, the method produces a resulting bitmap for a reduced range.The ensures the production of a resulting bitmap. When the range is reduced, the method may be repeated to produce a merge for a range beyond the reduced range.

摘要翻译： 一种用于在存储器内组合限制的方法，来自不定大小和数量的位图的多个位图流。 位图流被合并到可以在随后的逻辑操作中使用的结果位图。 为了在内存限制内执行合并，该方法依赖于数据压缩。 当压缩本身可能无效时，该方法会产生缩小范围的结果位图。 确保生成的位图。 当范围减小时，可以重复该方法以产生超出缩小范围的范围的合并。