A method for transforming grammars into LL(k) form

Summary A new method for transforming grammars into equivalent LL(k) grammars is studied. The applicability of the transformation is characterized by defining a subclass of LR(k) grammars, called predictive LR(k) grammars, with the property that a grammar is predictive LR(k) if and only if the corresponding transformed grammar is LL(k). Furthermore, it is shown that deterministic bottom-up parsing of a predictive LR(k) grammar can be done by the LL(k) parser of the transformed grammar. This parsing method is possible since the transformed grammar always left-to-right covers the original grammar. The class of predictive LR(k) grammars strictly includes the class of LC(k) grammars (the grammars that can be parsed deterministically in the left-corner manner). Thus our transformation is more powerful than the one previously available, which transforms LC(k) grammars into LL(k) form.     

Chromatic binary search trees

We propose a new rebalancing method for binary search trees that allows rebalancing and updating to be uncoupled. In this way we obtain fast updates and, whenever the search tree is accessed by multiple users, a high degree of concurrency. The trees we use are obtained by relaxing the balance conditions of red-black trees. The relaxed red-black trees, called chromatic trees, contain information of possible imbalance such that the rebalancing can be done gradually as a shadow process, or it can be performed separately when no urgent operations are present. Received December 5, 1991 / May 2, 1995     

On the definition and computation of rectilinear convex hulls

Recently the computation of the rectilinear convex hull of a collection of rectilinear polygons has been studied by a number of authors. From these studies three distinct definitions of rectilinear convex hulls have emerged. We examine these three definitions for point sets in general, pointing out some of their consequences, and we give optimal algorithms to compute the corresponding rectilinear convex hulls of a finite set of points in the plane.     

Concurrency control and recovery for balanced B-link trees

In this paper we present new concurrent and recoverable B-link-tree algorithms. Unlike previous algorithms, ours maintain the balance of the B-link tree at all times, so that a logarithmic time bound for a search or an update operation is guaranteed under arbitrary sequences of record insertions and deletions. A database transaction can contain any number of operations of the form fetch the first (or next) matching record, insert a record, or delete a record, where database records are identified by their primary keys. Repeatable-read-level isolation for transactions is guaranteed by key-range locking. The algorithms apply the write-ahead logging (WAL) protocol and the steal and no-force buffering policies for index and data pages. Record inserts and deletes on leaf pages of a B-link tree are logged using physiological redo-undo log records. Each structure modification such as a page split or merge is made an atomic action by keeping the pages involved in the modification latched for the (short) duration of the modification and the logging of that modification; at most two B-link-tree pages are kept X-latched at a time. Each structure modification brings the B-link tree into a structurally consistent and balanced state whenever the tree was structurally consistent and balanced initially. Each structure modification is logged using a single physiological redo-only log record. Thus, a structure modification will never be undone even if the transaction that gave rise to it eventually aborts. In restart recovery, the redo pass of our ARIES-based recovery protocol will always produce a structurally consistent and balanced B-link tree, on which the database updates by backward-rolling transactions can always be undone logically, when a physical (page-oriented) undo is no longer possible.Received: 8 October 2003, Accepted: 19 February 2004, Published online: 14 September 2004Edited by: B. Seeger     

Concurrency control in B-trees with batch updates

In many applications it is important to be able to insert (or delete) keys into a B-tree as a batch, instead of inserting them one by one. Moreover, it may be necessary to search the B-tree concurrently with the batch update. An example of this is a text database system supporting a newspaper house: all words (keys) of each article obtained from a news agency should be inserted at once, and, at the same time, searches for documents containing certain words should be allowed as efficiently as possible. We have designed two solutions to the problem of concurrent batch update. The first solution-implemented in our commercial text database system-optimizes the speed of the batch update, and the second solution optimizes the average search time during the batch update     

On comparingLL(k) andLR(k) grammars

A new and rigorous proof of the well-known fact thatLL(k) grammars areLR(k) grammars is provided. The proof is elementary in the sense that it is directly based on relations defining leftmost and rightmost derivations and no additional formalism is needed.     

Relaxed Balance Using Standard Rotations

Abstract. In search trees with relaxed balance, rebalancing transformations need not be connected with updates, but may be delayed. For standard AVL tree rebalancing, we prove that even though the rebalancing operations are uncoupled from updates, their total number is bounded by O(M log (M+N)) , where M is the number of updates to an AVL tree of initial size N . Hence, relaxed balancing of AVL trees comes at no extra cost asymptotically. Furthermore, our scheme differs from most other relaxed balancing schemes in an important aspect: No rebalancing transformation can be done in the wrong direction, i.e., no performed rotation can make the tree less balanced. Moreover, each performed rotation indeed corresponds to a real imbalance situation in the tree. Finally, and perhaps most importantly, our structure is capable of forgetting registered imbalance if later updates happen to improve the situation. Our results are of theoretical interest and have possible sequential and parallel applications.     

Relaxed Balance Using Standard Rotations

Abstract. In search trees with relaxed balance, rebalancing transformations need not be connected with updates, but may be delayed. For standard AVL tree rebalancing, we prove that even though the rebalancing operations are uncoupled from updates, their total number is bounded by O(M log (M+N)) , where M is the number of updates to an AVL tree of initial size N . Hence, relaxed balancing of AVL trees comes at no extra cost asymptotically. Furthermore, our scheme differs from most other relaxed balancing schemes in an important aspect: No rebalancing transformation can be done in the wrong direction, i.e., no performed rotation can make the tree less balanced. Moreover, each performed rotation indeed corresponds to a real imbalance situation in the tree. Finally, and perhaps most importantly, our structure is capable of forgetting registered imbalance if later updates happen to improve the situation. Our results are of theoretical interest and have possible sequential and parallel applications.     

On a covering relation for context-free grammars

Summary Given a grammar for translation or compiling purposes, the structure of the grammar reflects the semantics of the language rather than good properties for parsing the language. Thus the language is often parsed with respect to another grammar which satisfies the property that the derivation trees in the original grammar can be recovered from those of the parsing grammar. Undercover is introduced as a new concept for the formal treatment of such grammatical relations and properties of this relation are explored with an emphasis on decidability results and the relationship to existing concepts such as cover and Reynolds cover. Some decidability questions can be related to language theoretic results on inclusion problems for simple deterministic languages.This work was carried out when the first author was visiting the Unit for Computer Science, McMaster University, Hamilton, Ontario, Canada. The work of both authors was supported in part under a Natural Sciences and Engineering Research Council of Canada Grant No. A-7700     

Relaxed balance for search trees with local rebalancing

Search trees with relaxed balance were introduced with the aim of facilitating fast updating on shared-memory asynchronous parallel architectures. To obtain this, rebalancing has been uncoupled from the updating, so extensive locking in connection with updates is avoided. Rebalancing is taken care of by background processes, which do only a constant amount of work at a time before they release locks. Thus, the rebalancing and the associated locks are very localized in time as well as in space. In particular, there is no exclusive locking of whole paths. This means that the amount of parallelism possible is not limited by the height of the tree. Search trees with relaxed balance have been obtained by adapting standard sequential search trees to this new paradigm; clearly using similar techniques in each case, but no general result has been obtained. We show how any search tree with local bottom-up rebalancing can be used in a relaxed variant, preserving the complexity of the rebalancing from the sequential case. Additionally, we single out the one high level locking mechanism that a parallel implementation must provide in order to guarantee cons istency. Though the ideas have come from search trees, the result presented here applies to tree structures in general, where operations initiated at the leaves progress towards the root in constant-sized steps. Received: 10 September 1999 / 9 April 2001