公开(公告)号：US06374264B1

公开(公告)日：2002-04-16

申请号：US09207926

申请日：1998-12-09

申请人： Philip L. Bohannon ,  Rajeev Rastogi ,  Srinivasan Seshadri ,  Abraham Silberschatz ,  Sundararajarao Sudarshan

发明人： Philip L. Bohannon ,  Rajeev Rastogi ,  Srinivasan Seshadri ,  Abraham Silberschatz ,  Sundararajarao Sudarshan

IPC分类号： G06F1730

CPC分类号： G06F11/1474 ,  G06F11/1471 ,  G06F2201/80 ,  Y10S707/99932 ,  Y10S707/99953

摘要： A method of detecting and recovering from data corruption of a database is characterized by the step of protecting data of the database with codewords, one codeword for each region of the database; and verifying that a codeword matches associated data before the data is read from the database to prevent transaction-carried corruption. A deferred maintenance scheme is recommended for the codewords protecting the database such that the method of detecting and recovering from data corruption of a database may comprise the steps of protecting data of the database with codewords, one codeword for each region of the database; and asynchronously maintaining the codewords to improve concurrency of the database. Moreover, the database may be audited by using the codewords and noting them in a table and protecting regions of the database with latches. Once codeword values are computed and checked against noted values in memory, a flush can cause codewords from outstanding log records to be applied to the stored codeword table.

摘要翻译： 一种从数据库的数据损坏中检测和恢复的方法的特征在于利用码字保护数据库的数据的步骤，数据库的每个区域的一个码字; 并且在从数据库读取数据之前验证码字匹配相关联的数据以防止交易携带的损坏。 对于保护数据库的代码字，建议使用延迟维护方案，以便检测和恢复数据库的数据损坏的方法可以包括以下代码字来保护数据库的数据的步骤，数据库的每个区域的一个代码字; 并且异步地维护码字以改善数据库的并发性。 此外，可以通过使用码字来审核数据库，并在表中注明数据库，并用锁存器保护数据库的区域。 一旦根据存储器中的标记值计算和检查码字值，则刷新可以使来自未完成的日志记录的码字被应用于存储的码字表。

公开(公告)号：US6122645A

公开(公告)日：2000-09-19

申请号：US2635

申请日：1998-01-05

申请人： Philip L. Bohannon ,  Dennis W. Leinbaugh ,  Rajeev Rastogi ,  Srinivasan Seshadri ,  Abraham Silberschatz ,  Sundararajarao Sudarshan

发明人： Philip L. Bohannon ,  Dennis W. Leinbaugh ,  Rajeev Rastogi ,  Srinivasan Seshadri ,  Abraham Silberschatz ,  Sundararajarao Sudarshan

IPC分类号： G06F17/30

CPC分类号： G06F17/30309 ,  Y10S707/99953 ,  Y10S707/99954

摘要： For use with a database of data records organized into components, the database stored in a memory, a processing system for, and method of, physically versioning the database. In one embodiment, the processing system includes: (1) a component copier that creates a physical copy of an original component to be affected by an update transaction to be applied to the database, and that causes pointers in nodes of the physical copy to point to other nodes in the physical copy, (2) a data updater, associated with the component copier, that applies the update transaction to the physical copy to create therefrom a new physical version, the original component remaining unaffected by the update transaction and (3) a pointer updater, associated with the data updated, that employs an atomic word write to revise a component pointer, associated with the database, to cause the pointer to point to the new physical version.

摘要翻译： 为了与组织成组件的数据记录的数据库一起使用，存储在内存中的数据库，处理系统以及对数据库进行物理版本化的方法。 在一个实施例中，处理系统包括：（1）组件复印机，其创建将要被应用于数据库的更新事务影响的原始组件的物理副本，并且使物理副本的节点中的指针指向 到物理副本中的其他节点，（2）与组件复印机相关联的数据更新器，将更新事务应用于物理副本以从其创建新的物理版本，原始组件不受更新事务的影响，（3 ）与更新的数据相关联的指针更新器，其使用原子字写入来修改与数据库相关联的组件指针，以使指针指向新的物理版本。

公开(公告)号：US06449623B1

公开(公告)日：2002-09-10

申请号：US09207927

申请日：1998-12-09

申请人： Philip L. Bohannon ,  Rajeev Rastogi ,  Srinivasan Seshadri ,  Abraham Silberschatz ,  Sundararajarao Sudarshan

发明人： Philip L. Bohannon ,  Rajeev Rastogi ,  Srinivasan Seshadri ,  Abraham Silberschatz ,  Sundararajarao Sudarshan

IPC分类号： G06F1200

CPC分类号： G06F11/1474 ,  G06F11/1471 ,  G06F2201/80 ,  Y10S707/99932 ,  Y10S707/99953

摘要： A method of detecting and recovering from data corruption of a database is characterized by the step of logging information about reads of a database in memory to detect errors in data of the database, wherein said errors in data of said database arise from one of bad writes of data to the database, of erroneous input of data to the database by users and of logical errors in code of a transaction. The read logging method may be implemented in a plurality of database recovery models including a cache-recovery model, a prior state model a redo-transaction model and a delete transaction model. In the delete transaction model, it is assumed that logical information is not available to allow a redo of transactions after a possible error and the effects of transactions that read corrupted data are deleted from history and any data written by a transaction reading Ararat data is treated as corrupted.

摘要翻译： 从数据库的数据损坏中检测和恢复的方法的特征在于记录关于数据库在存储器中的读取的信息的步骤，以检测数据库的数据中的错误，其中所述数据库的数据中的错误来自坏写入之一 的数据，数据由用户错误地输入到数据库以及事务代码中的逻辑错误。 读取记录方法可以在包括高速缓存恢复模型，先前状态模型，重做事务模型和删除事务模型的多个数据库恢复模型中实现。 在删除事务模型中，假设逻辑信息不可用于允许在可能的错误之后重做事务，并且从历史中删除读取损坏的数据的事务的影响，并且处理由读取Ararat数据的事务写入的任何数据被处理 被破坏。

公开(公告)号：US06343296B1

公开(公告)日：2002-01-29

申请号：US09389337

申请日：1999-09-03

申请人： Mohana Krishna Lakhamraju ,  Rajeev Rastogi ,  Srinivasan Seshadri ,  Sundararajarao Sudarshan

发明人： Mohana Krishna Lakhamraju ,  Rajeev Rastogi ,  Srinivasan Seshadri ,  Sundararajarao Sudarshan

IPC分类号： G06F1730

CPC分类号： G06F17/30607 ,  Y10S707/99938 ,  Y10S707/99943 ,  Y10S707/99944

摘要： An on-line reorganization method of an object-oriented database with physical references involves a novel fuzzy traversal of the database, or a partition thereof, to identify the approximate parents of all migrating objects. Where the entire database is traversed the process begins from its persistent root. For traversals of a partition the process begins from each object with a reference pointing to it from outside the partition. To facilitate the identification of these inter-partitional objects an External Reference Table (“ERT”) is maintained. During the fuzzy traversal all new inserted and deleted references are tracked in a Temporary Reference Table (“TRT”). After the fuzzy traversal is completed, for each migrating object, a lock is obtained on the identified approximate parents and on all new parents in which references to the object were inserted, as indicated by the TRT. Based on the information in the TRT, locks are released on all approximate parents whose references to the object have been deleted. The references to the migrating object in the remaining set of locked parents are updated, the object is relocated and the locks are released. Alternatively, each parent of a migrating object can be individually locked, updated and released.

摘要翻译： 具有物理引用的面向对象数据库的在线重组方法涉及数据库或其分区的新颖的模糊遍历，以识别所有迁移对象的近似父母。 在整个数据库遍历的过程中，进程从其持久根开始。 对于遍历分区，进程从每个对象开始，引用从分区外部引用它。 为了便于识别这些跨部门对象，维护了外部参考表（“ERT”）。 在模糊遍历期间，所有新插入和删除的引用将在临时参考表（“TRT”）中进行跟踪。 模糊遍历完成后，对于每个迁移对象，在所标识的近似父母以及所有新父母上获取锁定，其中插入了对象的引用，如TRT所示。 根据TRT中的信息，在对对象的引用已被删除的所有近似父类上释放锁。 在剩余的一组锁定的父项中对迁移对象的引用被更新，对象被重新定位并且锁被释放。 或者，可以单独锁定，更新和释放迁移对象的每个父项。

公开(公告)号：US6125371A

公开(公告)日：2000-09-26

申请号：US914744

申请日：1997-08-19

申请人： Philip L. Bohannon ,  Dennis W. Leinbaugh ,  Rajeev Rastogi ,  Srinivasan Seshadri ,  Abraham Silberschatz ,  Sundararajarao Sudarshan

发明人： Philip L. Bohannon ,  Dennis W. Leinbaugh ,  Rajeev Rastogi ,  Srinivasan Seshadri ,  Abraham Silberschatz ,  Sundararajarao Sudarshan

IPC分类号： G06F17/30

CPC分类号： G06F17/30309 ,  G06F2216/09 ,  Y10S707/99954

摘要： For use with a database of data records stored in a memory, a system and method for increasing a memory capacity and a memory database employing the system or the method. The system includes: (1) a time stamping controller that assigns a time stamp to transactions to be performed on the database, the time stamp operates to preserve an order of the transactions, (2) a versioning controller that creates multiple versions of ones of the data records affected by the transactions that are update transactions and (3) an aging controller, which is associated with each of the time stamping and versioning controllers, that monitors a measurable characteristic of the memory and deletes ones of the multiple versions of the ones of the data records in response to the time stamp and the measurable characteristic thereby to increase memory capacity.

摘要翻译： 用于存储在存储器中的数据记录的数据库，用于增加存储器容量的系统和方法以及采用该系统或方法的存储器数据库。 该系统包括：（1）时间戳控制器，为在数据库上执行的事务分配时间戳，时间戳操作以保持事务的顺序，（2）版本控制器，其创建多个版本的 由更新事务的事务影响的数据记录和（3）与每个时间戳和版本控制器相关联的老化控制器，其监视存储器的可测量特性并删除其中的一个版本 的数据记录，以响应于时间戳和可测量的特性，从而增加存储器容量。

公开(公告)号：US06502095B2

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

申请号：US09391988

申请日：1999-09-09

申请人： Yuri J. Breitbart ,  Raghavan V. Komondoor ,  Rajeev Rastogi ,  Srinivasan Seshadri ,  Abraham Silberschatz

发明人： Yuri J. Breitbart ,  Raghavan V. Komondoor ,  Rajeev Rastogi ,  Srinivasan Seshadri ,  Abraham Silberschatz

IPC分类号： G06F1730

CPC分类号： G06F17/30575 ,  Y10S707/966 ,  Y10S707/99938 ,  Y10S707/99943 ,  Y10S707/99945

摘要： A system for, and method of, ensuring serialization of lazy updates in a distributed database described by a directed acyclic copy graph. In one embodiment, the system includes: (1) a timestamp module that creates a unique timestamp for each of the lazy updates and (2) a propagation module, associated with the timestamp module, that employs edges of the directed acyclic copy graph to propagate the lazy updates among replicas in the distributed database according to said unique timestamp and ensure the serialization.

摘要翻译： 一种用于确保在由有向非循环复制图描述的分布式数据库中对延迟更新进行序列化的系统和方法。 在一个实施例中，系统包括：（1）时间戳模块，其为每个延迟更新创建唯一的时间戳，以及（2）与时间戳模块相关联的传播模块，其使用有向非循环复制图的边缘来传播 根据所述唯一的时间戳，分布式数据库中的副本之间的懒惰更新，并确保序列化。

公开(公告)号：US08010121B2

公开(公告)日：2011-08-30

申请号：US11797562

申请日：2007-05-04

申请人： Partha Dutta ,  Sharad Jaiswal ,  Rajeev Rastogi

发明人： Partha Dutta ,  Sharad Jaiswal ,  Rajeev Rastogi

IPC分类号： H04W4/00

CPC分类号： H04W84/18 ,  H04W16/28 ,  H04W72/04

摘要： An example embodiment includes determining a cut of a graph to obtain a bi-partite sub-graph, where the graph represents a plurality of nodes and links between the plurality of nodes in a wireless mesh network. A channel is assigned to the bi-partite graph, and the obtained bi-partite subgraph is removed from the graph. The determining, assigning and removing steps are repeated until the graph has been divided into k bi-partite subgraphs, where k is the number of channels being used for scheduling.

摘要翻译： 示例实施例包括确定图形的切割以获得双分子图，其中图表示无线网状网络中的多个节点之间的多个节点和链路。 将通道分配给双分图，并从图中除去获得的双分子图。 重复确定，分配和删除步骤，直到该图被划分为k个双分子子图，其中k是用于调度的信道数。

公开(公告)号：US20080159316A1

公开(公告)日：2008-07-03

申请号：US11797562

申请日：2007-05-04

申请人： Partha Dutta ,  Sharad Jaiswal ,  Rajeev Rastogi

发明人： Partha Dutta ,  Sharad Jaiswal ,  Rajeev Rastogi

IPC分类号： H04L12/28

CPC分类号： H04W84/18 ,  H04W16/28 ,  H04W72/04

摘要： An example embodiment includes determining a cut of a graph to obtain a bi-partite sub-graph, where the graph represents a plurality of nodes and links between the plurality of nodes in a wireless mesh network. A channel is assigned to the bi-partite graph, and the obtained bi-partite subgraph is removed from the graph. The determining, assigning and removing steps are repeated until the graph has been divided into k bipartite subgraphs, where k is the number of channels being used for scheduling.

摘要翻译： 示例实施例包括确定图形的切割以获得双分子图，其中图表示无线网状网络中的多个节点之间的多个节点和链路。 将通道分配给双分图，并从图中除去获得的双分子图。 重复确定，分配和删除步骤，直到图被划分为k个二分图，其中k是用于调度的信道数。

公开(公告)号：US20080059439A1

公开(公告)日：2008-03-06

申请号：US11468533

申请日：2006-08-30

申请人： Wenfei Fan ,  Rajeev Rastogi

发明人： Wenfei Fan ,  Rajeev Rastogi

IPC分类号： G06F17/30

CPC分类号： G06F17/2205 ,  G06F16/8358 ,  G06F16/86 ,  G06F17/2229 ,  G06F17/2247

摘要： The invention provides a system and method for translating XPATH queries into SQL queries with a simple least fixpoint (LFP) operator, which is already supported by most commercial RDBMS. The method comprises the steps of (a) rewriting an input query into a regular query, which is capable of capturing both DTD recursion and XPATH queries in a uniform framework; and (b) translating the regular query to an SQL query with LFP. The invention further provides optimization techniques for reducing the use of the LFP operator. As a result, the invention is capable of answering a large class of XPATH queries by means of only low-end RDBMS features already available in most RDBMS.

摘要翻译： 本发明提供了一种用于将 XPATH 查询转换为 SQL 查询的系统和方法，该查询具有简单的最低修正点（ LFP ）运算符，它已被 最商业的 RDBMS 。 该方法包括以下步骤：（a）将输入查询重写为常规查询，其能够在统一框架中捕获 DTD 递归和 XPATH 查询; 和（b）使用 LFP 将常规查询转换为 SQL 查询。 本发明还提供了用于减少 LFP 运算符的使用的优化技术。 因此，本发明能够通过仅在大多数 RDBMS中已经提供的低端 RDBMS 功能来回答大量 XPATH 查询。

公开(公告)号：US07328220B2

公开(公告)日：2008-02-05

申请号：US11025211

申请日：2004-12-29

申请人： Alin Dobra ,  Johannes Gehrke ,  Rajeev Rastogi ,  Minos Garofalakis

发明人： Alin Dobra ,  Johannes Gehrke ,  Rajeev Rastogi ,  Minos Garofalakis

IPC分类号： G06F17/00

CPC分类号： G06F17/30516 ,  G06F17/3046 ,  Y10S707/99936 ,  Y10S707/99942

摘要： A method of efficiently providing estimated answers to workloads of aggregate, multi-join SQL-like queries over a number of input data-streams. The method only examines each data elements once and uses a limited amount of computer memory. The method uses join graphs and atomic sketches that are essentially pseudo-random summaries formed using random binary variables. The estimated answer is the product of all the atomic sketches for all the vertices in the query join graph. A query workload is processed efficiently by identifying and sharing atomic sketches common to distinct queries, while ensuring that the join graphs remain well formed. The method may automatically minimize either the average query error or the maximum query error over the workload.

摘要翻译： 一种有效提供对多个输入数据流的聚合，多连接SQL类查询的工作负载的估计答案的方法。 该方法仅检查每个数据元素一次并使用有限数量的计算机存储器。 该方法使用连接图和原子素描，它们本质上是使用随机二进制变量形成的伪随机摘要。 估计答案是查询连接图中所有顶点的所有原子草图的乘积。 通过识别和共享不同查询共同的原子草图，同时确保连接图形式保持良好，可以有效地处理查询工作负载。 该方法可以自动最小化平均查询错误或工作负载上的最大查询错误。