Abstract The aim of this work was to develop a technique to speed up complex joins in an incremental visual query system. When designing a visual, highly interactive interface for ad-hoc (read-only) queries, fast response times are of paramount importance. While a column-oriented DBMS reduces the inherent latency found in relational DBMS, there is still the question of how to index the data, especially so as to support complex joins. Equi-joins that involve a many-to-many relationship are an example of complex joins that arise frequently and whose efficient processing is essential for fast query processing. We present OVI-3, a NoSQL visual query system based on incremental querying that uses a simple directory-based indexing scheme for faster processing of such complex joins. The system has been piloted using real data from a student database at Aalto University. The results demonstrated that for certain complex joins the presented indexing scheme outperforms SQL queries from a data server, especially for queries involving anti-joins (negation), where OVI-3 provided an orders of magnitude speed improvement.

Since its inception in 1984, the IEEE International Conference on Data Engineering (ICDE) has become a premier forum for the exchange and dissemination of data management research results among researchers, users, practitioners, and developers. Continuing this long-standing tradition, the 32nd ICDE will be hosted this year in Helsinki, Finland, from May 16 to May 20, 2016. It is our great pleasure to welcome you to ICDE 2016 and to present its proceedings to you.

We use cache-sensitive memory layouts to improve search performance in ordinary binary search trees, without increasing the time complexity of insertion or deletion. Our approach does not require changes to the structure of the nodes or the rebalancing strategy of the tree. Cache-sensitivity is maintained with a memory-layout invariant that keeps a given number of neighboring nodes in the tree stored in the same cache block. We show how to preserve it using worst-case constant-time operations executed when the tree changes. In our extensive experiments, the invariant consistently improved the search performance of large AVL and red–black trees by 26–32%, on synthetic data as well as realistic search tree operations extracted from a database benchmark. We also compare binary search trees with several cache-sensitive B-trees, and non-dynamic approaches for laying out tree nodes in a multi-level memory hierarchy.

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 present an indexing system where a database index is divided into two parts: the main index located on disk and the differential index in the main memory. Both indices are implemented as B-trees. All updates performed by active transactions are written in the differential index. Periodically, writes of committed transactions are transferred from differential index to the main index as a batch-update operation. Thus, updates falling into the same leaf of the tree can be performed simultaneously. In addition, the system offers a simple recovery scheme. After a system crash, no undo operations are needed and redo operations need only write to the main memory.

Article Group updates for relaxed height-balanced trees Share on Authors: Lauri Malmi Laboratory of Information Processing Science, Helsinki University of Technology, P.O. Box 5400, 02015 HUT, Espoo, Finland Laboratory of Information Processing Science, Helsinki University of Technology, P.O. Box 5400, 02015 HUT, Espoo, FinlandView Profile , Eljas Soisalon-Soininen Laboratory of Information Processing Science, Helsinki University of Technology, P.O. Box 5400, 02015 HUT, Espoo, Finland Laboratory of Information Processing Science, Helsinki University of Technology, P.O. Box 5400, 02015 HUT, Espoo, FinlandView Profile Authors Info & Claims PODS '99: Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsMay 1999 Pages 358–367https://doi.org/10.1145/303976.304011Online:01 May 1999Publication History 13citation341DownloadsMetricsTotal Citations13Total Downloads341Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

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.

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.

In order to gain maximal efficiency of the concurrent use of search trees the number of nodes to be locked at a time should be as small aa possible, and the locks should be released aa soon aa possible.We propose a new rebalancing method for binary search treea that allows rebalancing to be uncoupled from updating, so as to make updating faster.The trees we use are obtained by relaxing the balance conditions of red-black trees.When not involved with updating, the rebalancing task can be performed as a shadow process being active all the time, or it can be performed outside rush hours, at night, for example.1.

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.

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.

We consider the separation of rebalancing from updates in several database structures, such as B-trees for external and AVL-trees for internal structures. We show how this separation can be implemented such that rebalancing is performed by local background processes. Our solution implies that even simple locking schemes (without additional links and copies of certain nodes) for concurrency control are efficient in the sense that at any time only a small constant number of nodes must be locked.

The purpose of a database concurrency control mechanism is to control a transaction system in such a way that only serializable executions of transactions are possible; that is, safety is enforced. Locking is an appropriate means to achieve safety. In this paper the following problem is considered:Can the set of all serializable schedules (in the sense of conflict-preserving serializability) of a transaction system be defined by locking, i.e., can maximal concurrency be achieved by locking?An efficient algorithm exists for the problem in the case of two-transaction systems, but in general the problem is NP-complete. In the case in which maximal concurrency indeed is achievable by locking a locking policy realizing maximal concurrency can be constructed efficiently. Finally, an easy-to-test sufficient condition under which maximal concurrency is achieved by locking is discussed.

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.

Various notions are introduced for the closure of a set of rectilinearly oriented rectangles on the plane. Optimal algorithms are presented for computing the closures. These algorithms imply optimal solutions to several problems related to database concurrency control.

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.

The use of "default reductions" in implementing LR parsers is considered in conjunction with the desire to decrease the number of states of the parser by making use of "don't-care" (also called "inessential" ) error entries.Default reductions are those which are performed independently of the lookahead string when other operations do not apply, and their use can lead to substantial savings in space and time.Don't-care error entries of an LR parser are those which are never consulted, and thus they can be arbitrarily replaced by nonerror entries in order to make a state compatible with another one.Determining don't-care error entries is most important in avoiding the growth of the size of the parser when eliminating reductions by single productions, that is, productions for which the right-hand side is a single symbol.The use of default reductions diminishes don't-care error entries.This effect is analyzed by giving a necessary and sufficient condition for an error entry to be don't-care when default reductions are used.As an application, elimination of reductions by single productions in conjunction with the use of default reductions is considered.

The problem of testing whether or not an arbitrary context-free grammar is LALR(k) for a fixed integer k ≥ 1 (i.e. only the subject grammar is a problem parameter) is shown to be PSPACE-complete. The result is in contrast with testing the membership in several other easily parsed classes of grammars, such as LR(k), SLR(k), LC(k) and LL(k) grammars, for which deterministic polynomial time membership tests are known. The PSPACE-hardness of the problem is proved using a transformation from the finite state automaton non-universality problem. A nondeterministic algorithm for constructing sets of LR(k) items leads to a polynomially space bounded algorithm for LALR(k) testing.

One of the most attractive techniques in optimizing LR parsers is to eliminate reductions by semantically insignificant productions of the form A → X (single productions), where X is a nonterminal or a terminal; such a modification can lead to substantial savings in both space and time. Therefore, much effort has been devoted to the development of methods for eliminating reductions by single productions from LR parsers (Aho and Ullman [1973a,1973b], Anderson, Eve and Horning[1973], Pager[1973a,1974], Demers[1974,1975], Backhouse [1976], Joliat[1976], Koskimies[1976], LaLonde [1976], Soisalon-Soininen[1976]).