We consider the recoverability of traditional R-tree index structures under concurrent updating transactions, an important issue that is neglected or treated inadequately in many proposals of R-tree concurrency control. We present two solutions to ARIES-based recovery of transactions on R-trees. These assume a standard fine-grained single-version update model with physiological write-ahead logging and steal-and-no-force buffering where records with uncommitted updates by a transaction may migrate from their original page to another page due to structure modifications caused by other transactions. Both solutions guarantee that an R-tree will remain in a consistent and balanced state in the presence of any number of concurrent forward-rolling and (totally or partially) backward-rolling multiaction transactions and in the event of process failures and system crashes. One solution maintains the R-tree in a strictly consistent state in which the bounding rectangles of pages are as tight as possible, while in the other solution this requirement is relaxed. In both solutions only a small constant number of simultaneous exclusive latches (write latches) are needed, and in the solution that only maintains relaxed consistency also the number of simultaneous nonexclusive latches is similarly limited. In both solutions, deletions are handled uniformly with insertions, and a logarithmic insertion-path length is maintained under all circumstances.

The multiversion B+-tree (MVBT) by Becker et al. assumes a single-data-item update model in which each new version created for a data item is given a timestamp that is unique across the entire MVBT. In this paper, we extend the MVBT model with multi-action transactions such that all (final) data-item versions created by a transaction are given the same timestamp. We show that the MVBT algorithms can be modified to work in a setting in which multiple readonly transactions and a single updating transaction operate concurrently in snapshot isolation on the MVBT, without compromising the asymptotically optimal time complexity of key inserts, key deletes, and key-range scans on any version. The structural consistency and balance of the MVBT is guaranteed by short-duration latching of pages, redo-only logging of structure modifications (version splits, key splits and page merges), and redo-undo logging of key insertions and deletions. The redo pass of our ARIES-based restart-recovery algorithm always produces a structurally consistent and balanced MVBT on which any undo action by a backward-rolling updating transaction can be performed logically if a physical undo is not possible. The standard steal-and-no-force buffering policy is assumed.

In a publish-subscribe system based on filtering of XML documents, subscribers specify their interests with profiles expressed in the XPath language. The system processes a stream of XML documents and delivers to subscribers a notification or content of documents that match the profiles. For filtering with profiles expressed as linear XPath queries, automaton-based approaches exist where the intractable size growth of a preconstructed deterministic finite automaton is avoided by using a nondeterministic automaton. In this article we examine how these general approaches, which do not assume the existence of any specific schema or document type definition (DTD), might benefit from the knowledge that all the XML documents to be filtered obey a given DTD.

Modern database applications increasingly often require access to historical versions of the database. Storing such multiversion data in a single-version B+ -tree database index is inefficient, especially for key-range queries. In this article, we present an index structure called the concurrent multiversion B+ -tree (CMVBT) for efficiently storing and querying multiversion data.

In a publish-subscribe system based on filtering of XML documents subscribers specify their interests with profiles expressed in the XPath language. The system processes a stream of XML documents and delivers to subscribers a notification or content of documents that match the profiles. We present a new XML-document-filtering algorithm that is based on the classic Aho-Corasick pattern-matching automaton. The automaton has a size linear in the sum of the sizes of the filters. We assume that the XML documents all conform to a given DTD; our algorithm utilizes the DTD in the preprocessing phase of the automaton to prune out descendant axes (//) and wildcards (*) from the XPath filters. The XPath subset currently supported consists of linear XPath expressions without predicates. In the case of a 683 MB protein-sequence database, we obtained a throughput of 18.8 MB/sec for 50 000 filters and 17.0 MB/sec for 500 000 filters, using a SAX parser with a throughput of 27 MB/sec.

We consider online bulk-delete operations on a large database table organized as a primary (sparse) B+-tree index on a multi-attribute key. Using the natural range partitions induced by prefixes of the key, we define a multi-granular key-range locking protocol in which a bulk operation locks a small number of logical fragments of the table covering the target of the operation. We also present an efficient and recoverable bulk-delete algorithm that minimizes the work needed in B-tree rebalancing and in transaction rollback. All the locks needed for a bulk-delete operation are acquired during a scan of the leaf pages covering the target key range; in this scan the records qualifying for deletion are only marked as deleted. The records are physically deleted in a rebalance phase that avoids visiting subtrees in which all records qualify for deletion, thus saving considerably on the number of rebalancing operations.

We develop new algorithms for the management of transactions in a page-shipping client-server database system in which the physical database is organized as a sparse B-tree index. Our starvation-free fine-grained locking protocol combines adaptive callbacks with key-range locking and guarantees repeatable-read-level isolation (i.e., serializability) for transactions containing any number of record insertions, record deletions, and key-range scans. Partial and total rollbacks of client transactions are performed by the client. Each structure modification such as a page split or merge is defined as an atomic action that affects only two levels of the B-tree and is logged using a single redo-only log record, so that the modification never needs to be undone during transaction rollback or restart recovery. The steal-and-no-force buffering policy is applied by the server when flushing updated pages onto disk and by the clients when shipping updated data pages to the server, while pages involved in a structure modification are forced to the server when the modification is finished. The server performs the restart recovery from client and system failures using an ARIES/CSA-based recovery protocol. Our algorithms avoid accessing stale data but allow a data page to be updated by one client transaction and read by many other client transactions simultaneously, and updates may migrate from a data page to another in structure modifications caused by other transactions while the updating transaction is still active.

We analyze the optimization effect of the “magic sets” rewriting technique for datalog queries and present some supplementary or alternative techniques that avoid many shortcomings of the basic technique. Given a magic sets rewritten query, the set of facts generated for the original, nonmagic predicates by the seminaive bottom-up evaluation is characterized precisely. It is shown that—because of the additional magic facts—magic sets processing may result in generating an order of magnitude more facts than the straightforward naive evaluation. A refinement of magic sets infactorized magic setsis defined. These magic sets retain most of the efficiency of original magic sets in regards to the number of nonmagic facts generated and have the property that a linear-time bound with respect to seminaive evaluation is guaranteed in all cases. An alternative technique for magic sets, calledenvelopes, which has several desirable properties over magic sets, is introduced. Envelope predicates are never recursive with the original predicates; thus, envelopes can be computed as a preprocessing task. Envelopes also allow the utilization of multiple sideways information passing strategies (sips) for a rule. An envelope-transformed program may be “readorned” according to another choice of sips and reoptimized by magic sets (or envelopes), thus making possible an optimization effect that cannot be achieved by magic sets based on a particular choice of sips.

Considers the optimization of recursive database queries expressed in Datalog (function-free Horn clause programs). The authors present a general strategy for rewriting a Datalog program to cut down the number of database facts consulted in the bottom-up evaluation of queries containing bound arguments. The strategy can be interpreted as a preprocessing task in which an 'envelope' containing the facts relevant to the query is determined by computing an easily evaluable query, and then the original query is applied to facts belonging to this envelope, which usually is only a small subset of all facts. The strategy applies to any Datalog program, and there exists a variant of the basic strategy that always produces 'regular envelopes' that can be determined using a regularly recursive program.>

We augment relational algebra with a generalized transitive closure operator that allows for the efficient evaluation of a subclass of recursive queries. The operator is based on a composition operator which is as general as possible when the operator is required to be associative and when only relational algebra operators are used in its definition. The closure of such a composition can be computed using the well-known efficient algorithms designed for the computation of the usual transitive closure. Besides the case in which complete materialization of recursive relations are required, our strategy also yields an efficient solution in the case in which a selection is applied to the closure.

Abstract Language processor generators are systems that produce various language processors (including compilers) on the basis of a high‐level specification. The design of language processor generators is discussed on the basis of experiments with a traditional compiler writing system (HLP78) employing pore LALR parsing and general attribute grammars. It is argued that these methods are too primitive from the practical point of view. The design of a new language processor generator, HLP84, is based on this view. This system is an attempt to provide high‐level tools for a restricted class of applications (one‐pass analysis). The syntactic facilities include regular expressions on the right‐hand sides of productions, a disambiguating mechanism that is integrated with regular expressions, and a mechanism for using semantic information to aid parsing. The semantic facilities include automatic support for semantic error handling and for symbol tables. Early experiences with the new system show that in spite of the general overhead caused by the higher automation level, the system allows the generation of reasonably efficient processors.

Well-known results on graph traversal are used to develop a practical, efficient algorithm for evaluating regularly and linearly recursive queries in databases that contain only binary relations. Transformations are given that reduce a subset of regular and linear queries involving n-ary relations (n > 2) to queries involving only binary relations.

The problem of testing whether or not a context-free grammar possesses the LALR(k) property is studied.For each fixed integer k -> 1 (i e, only the subject grammar is a problem parameter) the problem ts shown to be complete for polynounal space (PSPACE) For free k (i.e., both the grammar and the integer k are problem parameters) the problem ~s shown to be PSPACE-complete when k is expressed m unary and complete for nondetermuustic one-level exponential tune (NE) when k is expressed in binary.The PSPACE-hardness results are obtained by a reduction from the l'mite automaton nonuniversality problem, whereas the upper bound results are obtained by an economic nondeterministic algorithm that uses only linear space when k is fixed and quadratic space when k is in unary.The lower bound result for fixed k > 1 is in contrast with the complexity of testing the membership in several other easily parsed classes of grammars, such as LR(k), SLK(k), LC(k), LL(k), and strong LL(k) grammars, for which determmlsUc polynomtal-tune tests are known.The upper-bound results for free k m turn demonstrate how the complexity of the membership testing problems is dominated by k: for k in unary LALR(k) testing is no harder (with respect to polynomml-ttme reductions) than LALR(I) testing, and for k in binary no harder than, for example, strong LL(k) testing (which is known to be NE-complete).

A syntax-error-handling technique is defined as an extension of LR parsing.The technique is automatic, and the generation of the error-handling algorithm is based only on the context-free grammar and the lexical description of the language.The heart of the algorithm is a "phrase-lever' error-recovery strategy, which is an improvement upon the basic strategy of Leinius.The notion of phrase-level recovery is further generalized such that "local correction" is included within the basic framework.Special attention is paid to diagnostic aspects, such as the generation of descriptive recovery-independent error messages.The technique has been implemented in the compiler-writing system HLP (Helsinki Language Processor).Promising experimental results have been obtained by testing the technique with erroneous student-written ALGOL and Pascal programs.

An automatic syntax error handling technique applicable to LR parsing is presented and analyzed. The technique includes a "phrase-level" error recovery strategy augmented with certain additional features such as "local correction". Attention has also been paid to diagnostic aspects, i.e. the automatic generation of error message texts. The technique has been implemented in the compiler writing system HLP (Helsinki Language Processor), and some promising experimental results have been obtained by testing the technique with erroneous student-written Algol and Pascal programs.