Lucent Technologies Inc.

Indian Institute of Technology Bombay

At+t Corp.

Columbia University

Indian Institute of Technology Hyderabad

Sundararajarao Sudarshan

Rajeev R Rastogi

Abraham Silberschatz

Srinivasan Seshadri

Philip L Bohannon

Divesh Srivastava

Hosagrahar Visvesvaraya Jagadish

Philip Lewis Bohannon

Ramarao Kanneganti

Karthik Ramachandra

Dennis W Leinbaugh

Peter J Stuckey

Kenneth Andrew Ross

Daniel Francis Lieuwen

Prasan Roy

Jacques Gava

Arun Chaitanya Miriappalli

Mohana Krishna Lakhamraju

Varun Simhadri

Ravindra Guravannavar

Systems, methods, and computer-readable medium, are disclosed for transforming user-defined-function invocations in a query-based environment. A user-defined-function (UDF) and a query invoking the UDF are received. The UDF is parsed into a plurality of statements. A first expression tree corresponding to the UDF and a second expression tree corresponding the query are constructed, and merged using an operator to generate a transformed expression. The transformed expression is simplified, using transformation rules, if it is determined that is can be simplified.

Decorrelation of user-defined function invocations in queries

The present disclosure proposes the method for optimizing the performance of data base/web-service backed applications by automatically prefetching query results. The proposed system and methods automatically insert prefetch instructions at the earliest possible points across procedure calls in application source code, in presence of conditional branching and loops. A data flow analysis technique called anticipable expressions analysis is extended, to analyze anticipability of queries. The benefit of prefetching is limited due to the presence of assignment statements and conditional branches that precede the query execution statement. Enhancements such as code motion, chaining and rewriting prefetch requests are devised to increase benefits of prefetching. These techniques perform equivalence preserving program and query transformations.

Method for optimizing performance of database/web-service backed applications by automatically prefetching query results

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.

Method and apparatus for detecting and recovering from data corruption of a database via read logging

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.

Method and apparatus for detecting and recovering from data corruption of a database via read prechecking and deferred maintenance of codewords

A reference counting a garbage collection process employs a reference counting technique in which only the &ldquo;last&rdquo; detected strong pointer is followed to an object. Moreover, no assumptions are made about the phase locking used in the transaction and strict WAL is not followed. Indeed, a relatively restricted local traversal of the object graph is employed which leads to higher efficiency. Furthermore, in a client-server arrangement, updates made by a transaction running at the client may be reflected at the server after the transaction ends, and the updates are not required to be forced to the server before the end of the transaction.

Garbage collection in object oriented databases using transactional cyclic reference counting

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 (&ldquo;ERT&rdquo;) is maintained. During the fuzzy traversal all new inserted and deleted references are tracked in a Temporary Reference Table (&ldquo;TRT&rdquo;). 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.

On-line reorganization in object-oriented databases

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.

System and method for aging versions of data in a main memory database

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.

System and method for physically versioning data in a main memory

An equivalence rule having the multiset version of the relational algebraic theta-semijoin operator is used in effectuating Constraint Magic rewriting on a computer programming language query having non-equality, as well as equality, predicates. In particular, the rule effectuates Constraint Magic rewriting for a single join. When applied repeatedly on a sequence of joins, Constraint Magic rewriting is effectuated for a single block query. The rule may be used to generate relational algebraic expressions to optimize or determine the equivalency of queries. Cost estimates for alternative ways of evaluating a complex query can be efficiently computed. Based on these computed cost estimates, the least costly implementation of a complex query is determined.

Effecting constraint magic rewriting on a query with the multiset

A collection of equivalence rules involving the multiset version of the relational algebraic theta-semijoin operator is used to generate relational algebraic expressions equivalent to a computer programming language query. These expressions may be employed as a search space which is utilized by, for example, optimizing software or software that determines the equivalency of queries. Cost formulas for the multiset version of the theta-semijoin operator may be used in computing cost estimates for the generated expressions. Based on these computed cost estimates, the least costly implementation of a complex query is determined. Thus, queries are cost-based optimized on both a local and global basis by use of the relational algebraic theta-semijoin operator.

Optimization of queries using relational algebraic theta-semijoin

A method of incrementally maintaining a first materialized view of data in a database, by means of an additional materialized view, first determines whether a cost in time of incrementally maintaining the first materialized view with the additional materialized view is less than the cost of incrementally maintaining the first materialized view without the additional materialized view. The method creates the additional materialized view only if the cost in time is less therewith. Determining whether the cost of employing an additional materialized view is less includes using an expression directed acyclic graph that corresponds to the first materialized view. Another method of determining whether the cost is less includes pruning an expression directed acyclic graph to produce a single expression tree, and using the single expression tree to determine whether the cost is less. Both the expression directed acyclic graph and the single expression tree contain equivalence nodes. One or more possible materialized views are selected by marking the equivalence nodes, and materializing one or more views corresponding to the marked equivalence nodes. One or more possible materialized views are also selected by determining which of the views, if materialized, would result in a lowest cost of incrementally maintaining the first materialized view. The method is also used to reduce the cost in time of maintaining a first materialized view employed to check an integrity constraint of the database.

Cost-based maintenance of materialized views

A data base system buffers incoming records according to destination in the disk or non-volatile memory. The data is compressed and transferred to disk when sufficient data has been accumulated for a particular disk destination. Techniques for compressing the compression dictionary as well as the data stream are described.

System for compression and buffering of a data stream with data

The invention relates to a system for maintaining a log of incoming records for a database system. Seek points are inserted into the compressed data log in a manner that allows recovery to start from a specified point without a need for decompressing earlier portions of the log. The initial block of data is used as the compression dictionary. A new compression sequence using the same initial compression dictionary is started at each seek point.

Method and system for compressing a data stream in a database log so as

For use with an active database stored in volatile memory for direct revision thereof, the active database having multiple checkpoints and a stable log, having a tail stored in the volatile memory, for tracking revisions to the active database to allow corresponding revisions to be made to the multiple checkpoints, the active database subject to corruption, a system for, and method of, restoring the active database and a computer system containing the same. The system includes: (1) a checkpoint determination controller that determines which of the multiple checkpoints is a most recently completed checkpoint and copies the most recently completed checkpoint to the volatile memory to serve as an unrevised database for reconstructing the active database and (2) a revision application controller that retrieves selected ones of the revisions from the stable log and the tail and applies the revisions to the unrevised database thereby to restore the active database. In an advantageous embodiment, the applied revisions include log records at an operation level (lower level of abstration than transactions), and the revision application controller, using memory locks while restoring the active database, releases ones of the memory locks as a function of applying ones of the log records.

System and method for restoring a multiple checkpointed database in view

A fast crash safe method and apparatus for enforcing mutually exclusive access to shared resources in a computer system through the use of semaphores. The acquisition and release of the semaphores is implemented at the user process level. An overestimate and underestimate of semaphore ownership are maintained in memory by library provided semaphore acquisition and release code. A cleanup routine reconciles the overestimate and underestimate to determine the ownership status of the semaphores.

Growing community of inventors

Bombay, India

Sundararajarao Sudarshan