公开(公告)号：US07505957B2

公开(公告)日：2009-03-17

申请号：US10643644

申请日：2003-08-19

申请人： Roberta J. Cochrane ,  Mir H. Pirahesh ,  Richard S. Sidle

发明人： Roberta J. Cochrane ,  Mir H. Pirahesh ,  Richard S. Sidle

IPC分类号： G06F7/00 ,  G06F17/30

CPC分类号： G06F17/30457 ,  G06F17/30489 ,  Y10S707/99932 ,  Y10S707/99933

摘要： Disclosed is a method and system for incrementally maintaining algebraic functions in automatic summary tables (ASTs) of at least one relational database. The method associates a work area with each algebraic function in each AST. Each work area is comprised of one or more variables. The method populates the variables within each work area for each algebraic function when each AST is created and when each AST is updated. The method maintains each work area by adding and subtracting to and from its associated variables when the associated data changes in the relational database. The functions that compute the variables of the work areas are distributive and thus incrementally maintainable. The method computes and recomputes the algebraic function within an AST after the updates have changed one or more of the variables of its work area.

摘要翻译： 公开了一种用于在至少一个关系数据库的自动汇总表（AST）中逐渐维持代数函数的方法和系统。 该方法将工作区域与每个AST中的每个代数函数相关联。 每个工作区域都包含一个或多个变量。 当创建每个AST和更新每个AST时，该方法为每个代数函数填充每个工作区域内的变量。 该方法通过在关系数据库中相关联的数据更改时向其关联变量添加和减少来维护每个工作区域。 计算工作区变量的函数是分布式的，因此可以逐步维护。 该方法在更新改变其工作区域的一个或多个变量之后，计算并重新计算AST内的代数函数。

公开(公告)号：US5546576A

公开(公告)日：1996-08-13

申请号：US390196

申请日：1995-02-17

申请人： Roberta J. Cochrane ,  Mir H. Pirahesh ,  Richard S. Sidle

发明人： Roberta J. Cochrane ,  Mir H. Pirahesh ,  Richard S. Sidle

IPC分类号： G06F17/30

CPC分类号： G06F17/30448 ,  G06F17/30371 ,  G06F17/3051 ,  Y10S707/99932

摘要： An automated system for detecting and preventing mutating table violations of database integrity in a SQL query before generation and selection of an optimal query execution plan (QEP). This system modifies the query graph model (QGM) to restrict the choice of execution plans to those that avoid mutating table integrity (MTI) violations, thereby forcing database integrity during table mutation when executing the optimal QEP. Mutating table integrity violations are detected by evaluating the position in the QGM of each write-node referencing a particular base table with respect to each of the positions of all other read- and write-nodes referencing of the same base table. Every common-referencing node pair is tested for sequencing conflicts and a data-flow dam is inserted in the QGM where necessary to force the completion of the execution of one node before initiating execution of the other common-referencing node. The system of this invention allows processing of all non-cyclic and most cyclic SQL queries known to cause mutating table integrity violations, such as queries having searched and positioned inserts, deletes and updates, and row-level triggers.

摘要翻译： 一种用于在生成和选择最优查询执行计划（QEP）之前，在SQL查询中检测和防止突变表违反数据库完整性的自动化系统。 该系统修改查询图模型（QGM），将执行计划的选择限制为避免突变表完整性（MTI）违规的选择，从而在执行最佳QEP时强制表突变期间的数据库完整性。 通过评估参考相同基准表的所有其他读 - 写节点的每个位置的引用特定基表的每个写节点的QGM中的位置来检测突变表完整性违反。 测试每个共同参考节点对的排序冲突，并且在QGM中插入数据流大坝，必要时强制完成一个节点的执行，然后再启动其他公共引用节点的执行。 本发明的系统允许处理已知导致突变表完整性违例的所有非循环和大多数循环SQL查询，例如具有搜索和定位的插入，删除和更新的查询以及行级触发器。

公开(公告)号：US5280612A

公开(公告)日：1994-01-18

申请号：US801769

申请日：1991-11-26

申请人： Raymond A. Lorie ,  Chandrasekaran Mohan ,  Mir H. Pirahesh

发明人： Raymond A. Lorie ,  Chandrasekaran Mohan ,  Mir H. Pirahesh

IPC分类号： G06F12/00 ,  G06F17/30 ,  G06F15/40

CPC分类号： G06F17/30356 ,  G06F17/30362 ,  Y10S707/99938 ,  Y10S707/99939 ,  Y10S707/99953

摘要： An improved concurrency control system for application to a distributed concurrent transaction and query processing system using multi-version database records to overcome delays arising from lock conflicts. Read-only queries are afforded a consistent "stable state" of the database during the life of the query. Updating transactions requiring locks can proceed without waiting for the termination of long queries. At least two database versions are necessary, although availability of more versions permits long read-only queries to phase-out over time without forcing new queries to use aged "stable-state" data and without roll-back. Read-only queries can be terminated and converted to locking transactions to permit an update of the "stable state" database version before the queries would normally terminate. A novel record key structure having a plurality of substructures corresponding to the several database versions is used to access database records. Rapid selection of proper record version and efficient version tracking and updating is effected using several bit-mapped transaction index tables.

摘要翻译： 一种改进的并发控制系统，用于应用于分布式并发事务和查询处理系统，使用多版本数据库记录来克服由锁定冲突引起的延迟。 在查询期间，只读查询提供了数据库一致的“稳定状态”。 更新需要锁定的事务可以进行，而无需等待长时间查询的终止。 至少需要两个数据库版本，尽管更多版本的可用性允许长时间只读查询逐渐淘汰，而不会强制新查询使用老化的“稳定状态”数据，而无需回滚。 只读查询可以终止并转换为锁定事务，以便在查询正常终止之前更新“稳定状态”数据库版本。 具有对应于多个数据库版本的多个子结构的新颖的记录关键结构被用于访问数据库记录。 使用几个位映射的事务索引表来快速选择适当的记录版本和高效的版本跟踪和更新。

公开(公告)号：US5590324A

公开(公告)日：1996-12-31

申请号：US384925

申请日：1995-02-07

申请人： Ting Y. Leung ,  Mir H. Pirahesh ,  Michelle M. Jou ,  David E. Simmen

发明人： Ting Y. Leung ,  Mir H. Pirahesh ,  Michelle M. Jou ,  David E. Simmen

IPC分类号： G06F17/30

CPC分类号： G06F17/30454 ,  G06F17/30463 ,  Y10S707/99935

摘要： A method and apparatus for optimizing SQL queries by propagating and exploiting column nullability. Column nullability is identified and propagated using a three-valued logic, wherein a column of a table can be identified nullability information is exploited to optimize query operations through transformations. In one aspect of the present invention, quantified predicates (such as ">ALL") are transformed into simple predicates involving singleton subqueries so that indexing can be exploited. In another aspect of the present invention, "is not null" predicates are generated and pushed for certain aggregate queries. In still another aspect of the present invention, intersect operations are transformed into joins. The end result is that the present invention can significantly enhance the performance of the queries.

摘要翻译： 通过传播和利用列可空性来优化SQL查询的方法和装置。 使用三值逻辑来识别和传播列可空性，其中可以识别表的列可利用性来利用信息来优化通过转换的查询操作。 在本发明的一个方面，量化谓词（例如“> ALL”）被转换成涉及单例子查询的简单谓词，以便可以利用索引。 在本发明的另一方面，“不为空”的谓词被生成并被推送用于某些聚合查询。 在本发明的另一方面，相交操作被转换为联接。 最终结果是本发明可以显着提高查询的性能。

公开(公告)号：US5551031A

公开(公告)日：1996-08-27

申请号：US487300

申请日：1995-06-07

申请人： Josephine M. Cheng ,  Chandrasekaran Mohan ,  Mir H. Pirahesh

发明人： Josephine M. Cheng ,  Chandrasekaran Mohan ,  Mir H. Pirahesh

IPC分类号： G06F17/30

CPC分类号： G06F17/30498 ,  Y10S707/99932

摘要： A computer database system utilizes a method for performing a right outer join of database tables without sorting the inner table (T.sub.2). The processing of each tuple in the outer table (T.sub.1) includes the preservation in the joint output of all tuples in T.sub.2 which are in its responsibility region. The initialization step of the process preserves in the join output all of the tuples in T.sub.2 which have column set values less than the lowest column set value in T.sub.1, i.e. the first tuple in T.sub.1, since T.sub.1 is sorted or accessed using a sorted index. The responsibility region for tuples in T.sub.1, other than the last tuple, is defined as those tuples which have column set values less than the column set value for the next tuple in T.sub.1 and greater than or equal to the column set value for the current T.sub.1 tuple. The last tuple in T.sub.1 must preserve all of the tuples in T.sub.2 which have not already been preserved in T.sub.2, i.e. all tuples greater than or equal to its column set value. If T.sub.1 has duplicate values for the column set value, only the last one preserves the associated T.sub.2 tuples. Additional methods for parallel execution of the outer join methods and methods for applying the outer join methods to subqueries (i.e., an All (or universal) Right Join (ARJOIN) and an Existential Right Join (ERJOIN)) are described.

摘要翻译： 计算机数据库系统利用用于执行数据库表的右外连接的方法，而不排序内表（T2）。 外表（T1）中每个元组的处理包括在其责任区域的T2中所有元组的联合输出中的保存。 该进程的初始化步骤在连接输出中保留所有T2中的元组，它们的列设置值小于T1中的最低列设置值，即T1中的第一个元组，因为使用排序索引对T1进行排序或访问。 T1中的元组的责任区域除了最后一个元组之外，被定义为具有小于T1中下一个元组的列设置值的列设置值大于或等于当前T1的列设置值的元组 元组 T1中的最后一个元组必须保留T2中尚未保存在T2中的所有元组，即大于或等于其列设置值的所有元组。 如果T1具有列设置值的重复值，则只有最后一个值保留关联的T2元组。 描述了用于并行执行外连接方法和将外连接方法应用于子查询（即，全（或通用）右连接（ARJOIN）和存在右连接（ERJOIN））的附加方法。

公开(公告)号：US5615361A

公开(公告)日：1997-03-25

申请号：US384759

申请日：1995-02-07

申请人： Ting Y. Leung ,  Mir H. Pirahesh ,  David E. Simmen ,  Lori G. Strain ,  Sanjai Tiwari

发明人： Ting Y. Leung ,  Mir H. Pirahesh ,  David E. Simmen ,  Lori G. Strain ,  Sanjai Tiwari

IPC分类号： G06F17/30

CPC分类号： G06F17/30436 ,  G06F17/30451 ,  G06F17/30454 ,  Y10S707/954 ,  Y10S707/99933

摘要： The present invention optimizes SQL queries by exploiting uniqueness properties. In identifying whether the generalized 1-tuple condition exists, the query is first analyzed to determine whether any columns referenced in a predicate of the query are bound. According to the present invention, columns may be bound to constant values or correlated columns or columns that are already bound. The bound columns, if any, are then analyzed to determine whether any of the bound columns comprise a key for its associated table. If these conditions exist, then the query satisfies the 1-tuple condition, in that it returns at most one tuple. Once the generalized 1-tuple condition has been identified to exist for the query, important query transformations can be performed for optimization purposes. These query transformations comprise the transformation of scalar subqueries into joins, or the elimination of distinctiveness requirements (i.e., DISTINCT keywords) from SELECT clauses.

摘要翻译： 本发明通过利用唯一性来优化SQL查询。 在识别广义1元组条件是否存在时，首先分析查询以确定查询谓词中引用的任何列是否被绑定。 根据本发明，列可以绑定到已经结合的常数值或相关的列或列。 然后分析绑定的列（如果有的话），以确定任何绑定列是否包含其关联表的键。 如果这些条件存在，则查询满足1元组条件，因为它最多返回一个元组。 一旦确定了查询的广义1元组条件，就可以执行重要的查询转换来进行优化。 这些查询转换包括将标量子查询转换为联接，或从SELECT子句中消除明确性要求（即DISTINCT关键字）。

公开(公告)号：US5557791A

公开(公告)日：1996-09-17

申请号：US325942

申请日：1994-10-19

申请人： Josephine M. Cheng ,  Chandrasekaran Mohan ,  Mir H. Pirahesh

发明人： Josephine M. Cheng ,  Chandrasekaran Mohan ,  Mir H. Pirahesh

IPC分类号： G06F17/30

CPC分类号： G06F17/30498 ,  Y10S707/99932

摘要： A computer database system utilizes a method for performing a right outer join of database tables without sorting the inner table (T.sub.2). The processing of each tuple in the outer table (T.sub.1) includes the preservation in the joint output of all tuples in T.sub.2 which are in its responsibility region. The initialization step of the process preserves in the join output all of the tuples in T.sub.2 which have column set values less than the lowest column set value in T.sub.1, i.e. the first tuple in T.sub.1, since T.sub.1 is sorted or accessed using a sorted index. The responsibility region for tuples in T.sub.1, other than the last tuple, is defined as those tuples which have column set values less than the column set value for the next tuple in T.sub.1 and greater than or equal to the column set value for the current T.sub.1 tuple. The last tuple in T.sub.1 must preserve all of the tuples in T.sub.2 which have not already been preserved in T.sub.2, i.e. all tuples greater than or equal to its column set value. If T.sub.1 has duplicate values for the column set value, only the last one preserves the associated T.sub.2 tuples. Additional methods for parallel execution of the outer join methods and methods for applying the outer join methods to subqueries (i.e., an All (or universal) Right Join (ARJOIN) and an Existential Right Join (ERJOIN)) are described.

摘要翻译： 计算机数据库系统利用用于执行数据库表的右外连接的方法，而不排序内表（T2）。 外表（T1）中每个元组的处理包括在其责任区域的T2中所有元组的联合输出中的保存。 该进程的初始化步骤在连接输出中保留所有T2中的元组，它们的列设置值小于T1中的最低列设置值，即T1中的第一个元组，因为使用排序索引对T1进行排序或访问。 T1中的元组的责任区域除了最后一个元组之外，被定义为具有小于T1中下一个元组的列设置值的列设置值大于或等于当前T1的列设置值的元组 元组 T1中的最后一个元组必须保留T2中尚未保存在T2中的所有元组，即大于或等于其列设置值的所有元组。 如果T1具有列设置值的重复值，则只有最后一个值保留关联的T2元组。 描述了用于并行执行外连接方法和将外连接方法应用于子查询（即，全（或通用）右连接（ARJOIN）和存在右连接（ERJOIN））的附加方法。

公开(公告)号：US5546570A

公开(公告)日：1996-08-13

申请号：US390112

申请日：1995-02-17

申请人： John A. McPherson, Jr. ,  Mir H. Pirahesh ,  Tuong C. Truong ,  Daniel J. Coyle, Jr.

发明人： John A. McPherson, Jr. ,  Mir H. Pirahesh ,  Tuong C. Truong ,  Daniel J. Coyle, Jr.

IPC分类号： G06F17/30

CPC分类号： G06F17/30595 ,  Y10S707/954 ,  Y10S707/99932 ,  Y10S707/99934

摘要： The present invention provides an evaluation strategy for the execution of SQL queries involving recursion and table queues in a relational database management system. The table queue is established for the query in the memory of the computer, and tuples are generated by tuple-producing operators in the query for storage into the table queue. As operators of the query read the stored tuples from the table queue, a first end-of-file condition, termed a Temporary End-Of-File, occurs when all of the tuples currently stored in the table queue have been retrieved and control is returned to the operator reading from the table queue. A retry request for additional tuples is generated by the operator through the table queue to the tuple-producing operators. If the tuple-producing operators can generate additional tuples, then these additional tuples are stored into the table queue and control is returned to the operator reading from the table queue in response to the retry request. If the tuple-producing operators cannot generate the additional tuples, then a second end-of-file condition, termed a Permanent End-Of-File, occurs and control is returned to the operator reading from the table queue.

摘要翻译： 本发明提供了在关系数据库管理系统中执行涉及递归和表队列的SQL查询的评估策略。 为计算机的存储器中的查询建立表队列，并且元组由查询中的元组生成操作符生成，用于存储到表队列中。 当查询的运算符从表队列中读取存储的元组时，当检索到当前存储在表队列中的所有元组，并且控件为“否”时，会发生称为临时文件结束文件的第一个文件结束条件 返回到操作员从表队列中读取。 对于额外的元组的重试请求由操作员通过表队列生成到元组生成操作符。 如果元组生成操作符可以生成额外的元组，那么这些额外的元组被存储到表队列中，并且响应于重试请求将控制返回给操作员从表队列读取。 如果元组生成运算符不能生成额外的元组，则会发生称为永久文件结束的第二个文件结束条件，并将控制权从表队列返回给操作员进行读取。

公开(公告)号：US5367675A

公开(公告)日：1994-11-22

申请号：US807281

申请日：1991-12-13

申请人： Josephine M.-K. Cheng ,  Sheldon J. Finkelstein ,  Donald J. Haderle ,  Mir H. Pirahesh ,  Yun Wang

发明人： Josephine M.-K. Cheng ,  Sheldon J. Finkelstein ,  Donald J. Haderle ,  Mir H. Pirahesh ,  Yun Wang

IPC分类号： G06F17/30 ,  G06F15/403

CPC分类号： G06F17/30451 ,  G06F17/30466 ,  Y10S707/99932

摘要： An automated method is provided for optimizing a query for retrieving data from a relational database in a computer relational database management system. The method uses rules for identifying queries for which duplicates are a factor in retrieving the proper data from the database. The method then merges queries with table expressions, views and subqueries when possible without causing duplicates to be unnecessarily retrieved.

摘要翻译： 提供了一种自动化方法，用于优化从计算机关系数据库管理系统中的关系数据库检索数据的查询。 该方法使用用于识别查询的规则，重复项是从数据库检索正确数据的因素。 然后，该方法可能会将查询与表表达式，视图和子查询合并，而不会导致不必要地检索重复。

公开(公告)号：US5548758A

公开(公告)日：1996-08-20

申请号：US463968

申请日：1995-06-05

申请人： Mir H. Pirahesh ,  Ting Y. Leung ,  Guy M. Lohman ,  Eugene J. Shekita ,  David E. Simmen

发明人： Mir H. Pirahesh ,  Ting Y. Leung ,  Guy M. Lohman ,  Eugene J. Shekita ,  David E. Simmen

IPC分类号： G06F17/30

CPC分类号： G06F17/30454 ,  Y10S707/99932 ,  Y10S707/99935

摘要： A method and apparatus for optimizing SQL queries in a relational database management system uses early-out join transformations. An early-out join comprises a many-to-one existential join, wherein the join scans an inner table for a match for each row of the outer table and terminates the scan for each row of the outer table when a single match is found in the inner table. To transform a many-to-many join to an early-out join, the query must include a requirement for distinctiveness, either explicitly or implicitly, in one or more result columns for the join operation. Distinctiveness can be specified using the DISTINCT keyword in the SELECT clause or can be implied from the predicates present in the query. The early-out join transformation also requires that no columns of the inner table be referenced after the join, or if an inner table column is referenced after the join, that each referenced column be "bound". A referenced column can be bound in one of three ways: (1) an inner table column can be bound to a constant through an equality predicate, (2) an inner table column can be bound to an outer table column, or (3) an inner table column can be bound to a correlated value, wherein the correlated value originates outside the query block. In all three cases, an inner table column can be bound through the transitivity of equality predicates.

摘要翻译： 用于优化关系数据库管理系统中的SQL查询的方法和装置使用早期连接变换。 早期连接包括多对一存在连接，其中，连接扫描内部表以获取外部表的每一行的匹配，并且当找到单个匹配时终止外部表的每一行的扫描 内表。 要将多对多连接转换为早期连接，查询必须在连接操作的一个或多个结果列中明确或隐式地包含独特性的要求。 可以使用SELECT子句中的DISTINCT关键字指定不同之处，也可以从查询中存在的谓词中暗示。 早期连接转换还要求在连接之后不引用内部列的列，或者如果在连接之后引用了内部列列，则每个引用的列都将被“绑定”。 引用的列可以通过三种方式之一来绑定：（1）内表列可以通过相等谓词绑定到常量，（2）内表列可绑定到外表列，或（3） 可以将内表列绑定到相关值，其中相关值起始于查询块之外。 在所有三种情况下，内表列可以通过相等谓词的传递性来约束。