公开(公告)号：US06081800A

公开(公告)日：2000-06-27

申请号：US807344

申请日：1997-02-28

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

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

IPC分类号： G06F17/30

CPC分类号： G06F17/30324 ,  Y10S707/99931 ,  Y10S707/99933 ,  Y10S707/99938

摘要： A method and apparatus for generating and using bitmaps in a database system that employs multi-level identifiers is provided. The generated bitmaps include bits that correspond to the identifiers that have been assigned to existing records, as well as bits that correspond to all intervening multi-level identifiers that have not yet been assigned. Therefore, when new rows are inserted into the table associated with the bitmap, new bits do not have to be inserted into the existing bitmap. When existing rows are deleted, the bits that correspond to the deleted rows are not themselves deleted, but are simply set to a value that indicates that the corresponding row does not satisfy the criteria associated with the bitmap.

摘要翻译： 提供了一种在采用多级标识符的数据库系统中生成和使用位图的方法和装置。 生成的位图包括对应于已经分配给现有记录的标识符的位以及对应于尚未被分配的所有中间多级标识符的位。 因此，当将新行插入到与位图关联的表中时，新位不必插入到现有位图中。 当现有行被删除时，对应于被删除行的位本身不被删除，而是被简单地设置为指示相应行不满足与位图相关联的标准的值。

公开(公告)号：US5907297A

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

申请号：US808560

申请日：1997-02-28

申请人： Jeffrey I. Cohen ,  Michael Depledge ,  Hakan Jakobsson ,  Cetin Ozbutun

发明人： Jeffrey I. Cohen ,  Michael Depledge ,  Hakan Jakobsson ,  Cetin Ozbutun

IPC分类号： H03M7/30

CPC分类号： H03M7/30 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99937

摘要： A method and apparatus for compressing data is provided. The invention compresses an input bit stream into a compressed output bit stream. The input bit streams are byte aligned and classified. Bytes with all bits set to value zero are classified as gap bytes. Bytes with only one bit set to value one are classified as offset bytes. All other bytes are classified as map bytes. Groups of adjacent bytes are organized into two types of groups. The first type is a gap bit group. A gap map group contains gap bytes and one offset byte. The second type is the gap map group. It contains gap bytes and map bytes. The number of gap bytes in a group is called a gap size. The groups are compressed into four types of atoms. Each type of atom has one control byte, zero or more gap size bytes, and zero or map bytes. A control byte describes the atom. The map bytes in an atom are copies of the map bytes in the control group.

摘要翻译： 提供了一种用于压缩数据的方法和装置。 本发明将输入比特流压缩为压缩输出比特流。 输入位流是字节对齐和分类的。 所有位设置为零的字节被分类为间隙字节。 只有一位设置为值1的字节被分类为偏移字节。 所有其他字节都被分类为地图字节。 相邻字节组被分为两种类型的组。 第一种类型是间隙位组。 间隙图组包含间隙字节和一个偏移字节。 第二种是间隙图组。 它包含间隙字节和映射字节。 一组中间隙字节的数量称为间隙大小。 这些基团被压缩成四种类型的原子。 每种类型的原子都有一个控制字节，零个或多个间隙大小的字节，零或映射字节。 控制字节描述原子。 原子中的映射字节是控制组中映射字节的副本。

公开(公告)号：US5899988A

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

申请号：US807451

申请日：1997-02-28

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

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

IPC分类号： G06F17/30

CPC分类号： G06F17/30312 ,  Y10S707/99933 ,  Y10S707/99937 ,  Y10S707/99953

摘要： A method and apparatus provide bitmapped indexing with high granularity locking. Whenever a change is made to a data table upon which a bitmapped index is based, two differential entries are generated and stored as index entries in the bitmapped index. Each differential entry identifies a bit to be flipped in the corresponding bitmap index entry. When applied to corresponding bitmap index entry, the changes are reflected in the appropriate bitmaps. Whenever a bitmap is read from the bitmapped index, any corresponding differential entries are applied so that the resulting bitmap reflects the change made to the data table.

摘要翻译： 一种方法和装置提供具有高粒度锁定的位图索引。 无论何时对位图索引所基于的数据表进行更改，都会生成两个差分条目，并将其作为索引条目存储在位图索引中。 每个差分条目标识要在相应位图索引条目中翻转的位。 当应用于相应的位图索引条目时，更改将反映在适当的位图中。 每当从位映射索引读取位图时，应用任何相应的差分条目，以便生成的位图反映对数据表所做的更改。

公开(公告)号：US5819256A

公开(公告)日：1998-10-06

申请号：US752128

申请日：1996-11-20

申请人： Cetin Ozbutun ,  Michael Depledge ,  Hakan Jakobsson ,  Jeffrey I. Cohen

发明人： Cetin Ozbutun ,  Michael Depledge ,  Hakan Jakobsson ,  Jeffrey I. Cohen

IPC分类号： G06F17/30

CPC分类号： G06F17/30324 ,  G06F17/30489 ,  Y10S707/99932

摘要： A method and apparatus for processing count queries in a database system is provided. The database server determines whether it is possible for the target data specified in a count query to contain null values. If the target data cannot contain null values, the count query is converted into a count star query. Count star queries are executed by counting the number of records that store the target data without actually reading and evaluating the target data. If an index for the table that stores the target data exists, then the number of records are counted without accessing the table itself by counting record identifiers in the index. If the index is a bitmap index, the number of bits that are set in bitmaps from the index are counted without actually generating record identifiers from the bitmaps. Many processes are used to generate intermediate count values from the bitmaps. The intermediate count values are summed to produce a total count value. For count queries that contain group by clauses, intermediate count values are generated for each distinct key value. The intermediate count values are summed to produce a total count value for each distinct key value.

摘要翻译： 提供了一种用于处理数据库系统中的计数查询的方法和装置。 数据库服务器确定计数查询中指定的目标数据是否可能包含空值。 如果目标数据不能包含空值，则计数查询将转换为计数星形查询。 通过计数存储目标数据的记录数量而不实际读取和评估目标数据来执行计数星形查询。 如果存在目标数据的表的索引存在，则通过计数索引中的记录标识符来计数记录数，而不访问表本身。 如果索引是位图索引，则从索引中的位图中设置的位数将被计数，而不会从位图实际生成记录标识符。 许多进程用于从位图生成中间计数值。 将中间计数值相加以产生总计数值。 对于包含group by子句的计数查询，会为每个不同的键值生成中间计数值。 将中间计数值相加以产生每个不同键值的总计数值。

公开(公告)号：US06205442B1

公开(公告)日：2001-03-20

申请号：US09311654

申请日：1999-05-13

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

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

IPC分类号： G06F1730

CPC分类号： H03M7/30 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99934 ,  Y10S707/99937

摘要： A method and apparatus for compressing data is provided. The invention compresses an input bit stream into a compressed output bit stream. The input bit streams are byte aligned and classified. Bytes with all bits set to value zero are classified as gap bytes. Bytes with only one bit set to value one are classified as offset bytes. All other bytes are classified as map bytes. Groups of adjacent bytes are organized into two types of groups. The first type is a gap bit group. A gap map group contains gap bytes and one offset byte. The second type is the gap map group. It contains gap bytes and map bytes. The number of gap bytes in a group is called a gap size. The groups are compressed into four types of atoms. Each type of atom has one control byte, zero or more gap size bytes, and zero or map bytes. A control byte describes the atom. The map bytes in an atom are copies of the map bytes in the control group.

摘要翻译： 提供了一种用于压缩数据的方法和装置。 本发明将输入比特流压缩为压缩输出比特流。 输入位流是字节对齐和分类的。 所有位设置为零的字节被分类为间隙字节。 只有一位设置为值1的字节被分类为偏移字节。 所有其他字节被分类为映射字节。相邻字节的组被分为两种类型的组。 第一种类型是间隙位组。 间隙图组包含间隙字节和一个偏移字节。 第二种是间隙图组。 它包含间隙字节和映射字节。 一组中的间隙字节数称为间隙大小。这些组被压缩成四种类型的原子。 每种类型的原子都有一个控制字节，零个或多个间隙大小的字节，零或映射字节。 控制字节描述原子。 原子中的映射字节是控制组中映射字节的副本。

公开(公告)号：US5963932A

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

申请号：US846520

申请日：1997-04-29

申请人： Hakan Jakobsson ,  Michael Depledge ,  Jeffrey I. Cohen ,  Cetin Ozbutun

发明人： Hakan Jakobsson ,  Michael Depledge ,  Jeffrey I. Cohen ,  Cetin Ozbutun

IPC分类号： G06F17/30

CPC分类号： G06F17/30592 ,  G06F17/30436 ,  G06F17/30463 ,  Y10S707/99932 ,  Y10S707/99933

摘要： In processing a query, a database server parses a string describing a query into a query representation. The query string is parsed again to generate a replica of the query representation. Various transformations can be applied to the replica in order to reduce the amount of processing for the query. In addition, transformations are applied to the query string before parsing again to produce a transformed query representation. A transformed query representation is selected for processing a query according to an estimated cost of using the query representation.

摘要翻译： 在处理查询时，数据库服务器将描述查询的字符串解析为查询表示。 再次分析查询字符串以生成查询表示的副本。 可以对副本应用各种转换，以减少查询的处理量。 另外，在再次解析之前，将转换应用于查询字符串以产生转换后的查询表示。 选择经变换的查询表示以根据使用查询表示的估计成本来处理查询。

公开(公告)号：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.

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

公开(公告)号：US5924088A

公开(公告)日：1999-07-13

申请号：US808094

申请日：1997-02-28

申请人： Hakan Jakobsson ,  Michael Depledge ,  Cetin Ozbutun ,  Jeffrey I. Cohen

发明人： Hakan Jakobsson ,  Michael Depledge ,  Cetin Ozbutun ,  Jeffrey I. Cohen

IPC分类号： G06F17/30

CPC分类号： G06F17/30327 ,  G06F17/30463 ,  Y10S707/99931 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99934

摘要： A list of indexes, from which indexes are selected for an index access path, is sorted by number of columns upon which each index is built. From the sorted list of indexes, a set of index access methods is generated in a heuristically ordered set of passes from a given WHERE clause. The index access methods that comprise the index access path are selected from the set of index access methods according to a cost/benefit analysis.

摘要翻译： 为索引访问路径选择索引的索引列表按照每个索引构建的列数进行排序。 从索引的排序列表中，以给定的WHERE子句的启发式有序集合生成一组索引访问方法。 根据成本/效益分析，从索引访问方法集中选择构成索引访问路径的索引访问方法。

公开(公告)号：US06266662B1

公开(公告)日：2001-07-24

申请号：US09617207

申请日：2000-07-17

申请人： Cetin Ozbutun ,  Jeffrey I. Cohen ,  Hakan Jakobsson ,  Michael Depledge ,  Alexander C. Ho

发明人： Cetin Ozbutun ,  Jeffrey I. Cohen ,  Hakan Jakobsson ,  Michael Depledge ,  Alexander C. Ho

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.

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