bluuebunny/crossref_metadata_2025 huggingface dataset:
An annotated bibliography on active databases (short version)
Authors: Jaeger Ulrike , Freytag Johann Christoph
Published: November 2005

This is a bibliography on active databases and active database systems which reflects the various research activities in this field. We compiled this bibliography for our own use, but hopefully it might be useful to other people as well. All papers that appear in the following list, are generally accessible.We do not claim that the bibliography is exhaustive and covers the complete range of literature that deals with activities. We decided to focus on central approaches, concepts, methods, and systems in the area of active databases. It does not contain entries in the area of "pure" real-time, object-oriented, temporal, and deductive databases. But we did include publications related to those approaches, as long as they discuss active databases.We divided the material into various sections following our own personal perception of the field. The sections provide an overview on different projects in the area of active databases, followed by sections on relevant research topics. Each section contains a few remarks followed by a list of cross references into the annotated bibliography. Papers might appear in more than one section in case they discuss different topics relevant to different sections.Additionally, when relevant we also included unpublished, but publicly available material. For those papers we included information how to obtain them from the authors or from the organizations where the were produced.The beauty of our work is the individual annotation to almost all publications. Due to space limitations we are forced to leave out those annotations in the version published here. For a complete annotated bibliography we refer to the entry in our WWW server.The effort to build up such a bibliography is an endless task. Since we believe it now provides a comprehensive overview on the existing literature in the field, we decided to publish it. However, we invite all readers to add remarks, corrections, updates, additions (including further annotations).Part of this work was done while we were associated with the FORWISS Institute of the Technical University of Munich. We would like to thank our student, Markus Blaschka, who compiled many references during his master's thesis.
ACM Multimedia '94 conference workshop on multimedia database management systems
Authors: Berra Bruce , Nwosu Kingsley , Thuraisingham Bhavani
Published: November 2005

This paper describes the
ACM Multimedia '94 Conference Workshop on Multimedia Database Management Systems
held on 21 October 1994 in San Francisco, California. The workshop consisted of four sessions: designing multimedia database management systems, video and continuous media service, multimedia storage and retrieval management, and miscellaneous topics in multimedia data management. The workshop concluded with a discussion session on directions for multimedia database management. Twenty-eight participants from U.S.A., U.K., Germany, Norway, and Egypt attended the workshop.
Information systems research at RWTH Aachen
Authors: Jarke Matthias
Published: November 2005

With about 8.000 researchers and 40.000 students, RWTH Aachen is the largest technical university in Europe. The science and engineering departments and their industrial collaborators offer a lot of challenges for database research.The chair Informatik V (Information Systems) focuses on the theoretical analysis, prototypical development, and practical evaluation of
meta information systems.
Meta information systems, also called repositories, document and coordinate the distributed processes of producing, integrating, operating, and evolving database-intensive applications.Our research approaches these problems from a technological and from an application perspective.On the one hand, we pursue theory and system aspects of the integration of deductive and object-oriented technologies. One outcome of this work is a deductive object manager called ConceptBase which has been developed over the past eight years and is currently used by many research groups and industrial teams throughout the world.On the other hand, a wide range of application-driven projects aims at building a sound basis of empirical knowledge about the demands on meta information systems, and about the quality of proposed solutions. They address application domains as diverse as requirements engineering, telecommunications, cooperative engineering, organization-wide quality management, evolution of chemical production processes, and medical knowledge management. They share the vision of supporting wide-area distributed cooperation not just by low-level interoperation technology but by exploiting conceptual product and process modeling.Under the direction of M. Jarke, Informatik V comprises three research groups with a total of twenty senior researchers and doctoral students: distributed information systems (leader: Dr. Manfred Jeusfeld), process information systems (Dr. Klaus Pohl), and knowledge-based systems (Prof. Wolfgang Nejdl). Database-related activities also exist in the Software Engineering and Applied Mathematics groups.
A comparison of three user interfaces to relational microcomputer data bases
Authors: Medsker Carl , Christensen Margaret , Song Il-Yeol
Published: November 2005

PAYOFF IDEA. Different styles of user interfaces can dramatically affect data base capabilities. In an environment comprising many different data bases, the goal is to select one data base management system (DBMS) that provides the best selection of design tools, minimizes development times, and enforces relational rules. This article presents a case study performed at the Hospital of the University of Pennsylvania, in which a test data base was developed for implementation with three DBMSs, each with a distinctly different user and programmer interface.
Two-level client caching and disconnected operation of notebook computers in distributed systems
Authors: Huizinga Dorota M. , Heflinger Ken A.
Published: November 2005

Data caching
in distributed file systems has been studied with regard to performance and availability [7,9,14,15]. The most common place for the cached data is the server's main memory. This type of caching is referred to as server caching, as opposed to client caching when the cached data is stored on the client (remote workstation) site. Although server caching improves performance considerably since it eliminates disk transfer time for each access, it has two drawbacks: it still suffers from a network transfer delay and is very vulnerable to server's failures. Server's failure renders the whole system virtually inoperable.
Performance analysis of small FDDI networks
Authors: Smith Jesse , Payne L. Donnell , Nute Tom
Published: November 2005

Fiber Distributed Data Interface (FDDI) networks offer a standardized, high-speed interconnection between components in a distributed computer system. Extensive research has been conducted on the performance of FDDI networks consisting of hundreds of stations distributed over an area of several hundred square meters. This paper extends the prior work to the case of small networks; for example 10 stations distributed around a single room laboratory. The characteristics for these smaller networks differ in some instances from the behavior of larger networks - these differences can be significant in applications where high performance is demanded from a small FDDI based network.
A digital conference like software tool for PDP programs
Authors: Tarng James J. , Yu Qiongsen , Reilly Kevin D.
Published: November 2005

Digital Conference is a software package, which allows people at different locations to exchange information and simultaneously share a running program through a network. It motivates us to create a digital conference like software for parallel and distributed processing programs. The DC-like PDP allows a group to discuss and operate the same PDP model without having all members present at the same computer site. The software has potential to facilitate teaching and research in our institution. This paper presents a complete methodology to develop the DC-like PDP. Two solution models using client/server computing are presented. A decision table approach is proposed to facilitate system analysis and design. The table is ultimately encoded as macro rules in source programs. The approach improves program readability, reduces the size of source codes, and enforces consistent maintenance.
Optimizing Jan Jannink's Implementation of B
+
-tree deletion
Authors: Maelbrancke R. , Olivié H.
Published: November 2005

In this note we propose optimization strategies for the B
+
-tree deletion algorithm. The optimizations are focused on even order B
+
-trees and on the reduction of the number of block accesses.
Design and user testing of a multi-paradigm query interface to an object-oriented database
Authors: Doan Dac Khoa , Paton Norman W. , Kilgour Alistair
Published: November 2005

This paper reports on experience obtained during the design, implementation and use of a multi-paradigm query interface to an object-oriented database. The specific system which has been developed allows equivalent data retrieval tasks to be expressed using textual, form-based and graph-based notations, and supports automatic translation of queries between these three paradigms. The motivation behind the development of such an interface is presented, as is the software architecture which supports the multi-paradigm functionality. Feedback from initial user trials with a dual-paradigm version of the system indicates that users can use it to perform complex query tasks without difficulty, that given the choice users overwhelmingly prefer the graph- based to the text-based interaction style, and that graphical visualisation of textual queries appears to aid users in query construction.
Normalization in OODB design
Authors: Lee Byung S.
Published: November 2005

When we design an object-oriented database schema, we need to normalize object classes as we do for relations when designing a relational database schema. However, the normalization process for an object class cannot be the same as that of a relation, because of the distinct characteristics of an object-oriented data model such as complex attributes, collection data types, and the usage of object identifiers in place of relational key attributes. We need only one kind of dependency proposed here -- the object functional dependency -- which specifies the dependency of object attributes with respect to the object identifier. We also propose the object normal form of an object class, for which all determinants of object functional dependencies are object identifiers. There is no risk of update anomalies as long as all object classes are in the object normal form.
Addressing techniques used in database object managers O
2
and ORION
Authors: Gamache André , Sahraoui Nadjiba
Published: November 2005

Addressing mechanisms used by the new generation of Data Base Management Systems (DBMS) differ significantly from traditional ones. Such changes are the direct result of new applications requirements such as office information systems (OIS) and computer aided design (CAD). In this context, object format requires different representations on disk and in main memory, and this is often valid for interobject references. It is evident that these mechanisms are closely linked to the mode of object-identity implementation, as well as clustering strategies. All of these functions are controlled by the object manager.This article describes these mechanisms through the implementation of two object managers for object-oriented DBMS: O
2
and ORION. We show how the performance of these systems depends on their memory management and addressing scheme. The two managers to be discussed merges techniques proposed by both data base field and object-oriented programming field. Their own mechanism differs, according to the way it handles distribution. ORION-1SX and O
2
have a Client/Server architecture, but each one uses a different approach for distributing of functionalities. ORION-1SX implements an object-server, whereas O
2
uses a page-server approach. An analysis of the two systems shows that they both use a two-level addressing mechanism. buffer management for objects in memory is diffent and more complex in ORION. On the other hand, the clustering strategies in O
2
have the advantage of being more dynamic and can be specified outside the schema.
METU interoperable database system
Authors: Dogac A. , Dengi C. , Kilic E. , Ozhan G. , Ozcan F. , Nural S. , Evrendilek C. , Halici U. , Arpinar B. , Koksal P. , Kesim N. , Mancuhan S.
Published: November 2005

METU INteroperable Database System (MIND) is a multidatabase system that aims at achieving interoperability among heterogeneous, federated DBMSs. MIND architecture if based on OMG distributed object management model. It is implemented on top of a CORBA compliant ORB, namely, ObjectBroker. MIND provides users a single ODMG-93 compliant common data model, and a single global query language based on SQL. This makes it possible to incorporate both relational and object oriented databases into the system. Currently Oracle 7, Sybase and METU OODBMS (MOOD) have been incorporated into MIND. The main components of MIND are a global query processor, a global transaction manager, a schema integrator, interfaces to supported database systems and a user graphical interface.In MIND all local databases are encapsulated in a generic database object with a well defined single interface. This approach hides the differences between local databases from the rest of the system. The integration of export schemas is currently performed manually by using an object definition language (ODL) which is based on OMG's interface definition language. The DBA builds the integrated schema as a view over export schemas. the functionalities of ODL allow selection and restructuring of schema elements from existing local schemas.MIND global query optimizer aims at maximizing the parallel execution of the intersite joins of the global subqueries. Through MIND global transaction manager, the serializable execution of the global transactions are provided.
A research status report on adaptation for mobile data access
Authors: Noble Brian D. , Satyanarayanan M.
Published: November 2005

Mobility demands the systems be
adaptive
. One approach is to make adaptation transparent to applications, allowing them to remain unchanged. An alternative approach views adaptation as a collaborative partnership between applications and the system. This paper is a status report on our research on both fronts. We report on our considerable experience with
application-transparent adaptation
in the Coda File System. We also describe our ongoing work on
application-aware adaptation
in Odyssey.
Temporal database system implementations
Authors: Böhlen Michael H.
Published: November 2005

Although research on temporal database systems has been active for about 20 years, implementations have not appeared until recently. This is one reason why current commercial database systems provide only limited temporal functionality. This paper summarizes extant state of the art of temporal database implementations. Rather than being very specific about each system we have attempted to provide an indication of the functionality together with pointers to additional information. It is hoped that this leads to more efforts pushing the implementation of temporal database systems in the near future.
Parallelism and its price
Authors: Englert Susanne , Glasstone Ray , Hasan Waqar
Published: November 2005

We describe the use of parallel execution techniques and measure the price of parallel execution in NonStop SQL/MP, a commercial parallel database system from Tandem Computers. Non-Stop SQL uses intra-operator parallelism to parallelize joins, groupings and scans. Parallel execution consists of starting up several processes and communicating data between them. Our measurements show (a) Startup costs are negligible when processes are reused rather than created afresh (b) Communication costs are significant — they may exceed the costs of operators such as scan, grouping or join. We also show two counter-examples to the common intuition that parallel execution reduces response time at the expense of increased work — parallel execution may reduce work or may increase response time depending on communication costs.
Establishing a web site
Authors: Warkentin Merrill E. , Sayeed Lutfus
Published: November 2005

The World Wide Web may become an important business tool to thousands of firms this year as it grows in size and capabilities. Many other firms wish to enter the age of cyberbusiness, but are unsure how to proceed. This paper addresses managerial and technical considerations when initiating a WWW project, with a focus on issues related to cost and control considerations, technical factors, security, web page design guidelines, standards, and trademark. This paper may serve as a guide to managers who choose to set up shop along the information superhighway.
On the cost of monitoring and reorganization of object bases for clustering
Authors: Gerlhof Carsten A. , Kemper Alfons , Moerkotte Guido
Published: November 2005

Clustering is one of the most effective means to enhance the performance of object base applications. Consequently, many proposals exist for algorithms computing good object placements depending on the application profile. However, in an effective object base reorganization tool the clustering algorithm is only one constituent. In this paper, we report on our object base reorganization tool that covers all stages of reorganizing the objects: the application profile is determined by a monitoring tool, the object placement is computed from the monitored access statistics utilizing a variety of clustering algorithms and, finally, the reorganization tool restructures the object base accordingly. The costs as well as the effectiveness of these tools is quantitatively evaluated on the basis of the OO1-benchmark.
Scientists called upon to take actions
Authors: Qian Xiaolei
Published: November 2005

Once again, scientists were called upon to take greater role in the political process. And this time, they did! We report on the continuous debate on the nation's R&D policy. We also cover funding opportunities from DoD and NSF.
Mining quantitative association rules in large relational tables
Authors: Srikant Ramakrishnan , Agrawal Rakesh
Published: November 2005

We introduce the problem of mining association rules in large relational tables containing both quantitative and categorical attributes. An example of such an association might be "10% of married people between age 50 and 60 have at least 2 cars". We deal with quantitative attributes by fine-partitioning the values of the attribute and then combining adjacent partitions as necessary. We introduce measures of partial completeness which quantify the information lost due to partitioning. A direct application of this technique can generate too many similar rules. We tackle this problem by using a "greater-than-expected-value" interest measure to identify the interesting rules in the output. We give an algorithm for mining such quantitative association rules. Finally, we describe the results of using this approach on a real-life dataset.
Data mining using two-dimensional optimized association rules
Authors: Fukuda Takeshi , Morimoto Yasukiko , Morishita Shinichi , Tokuyama Takeshi
Published: November 2005

We discuss data mining based on association rules for two numeric attributes and one Boolean attribute. For example, in a database of bank customers, "Age" and "Balance" are two numeric attributes, and "CardLoan" is a Boolean attribute. Taking the pair (Age, Balance) as a point in two-dimensional space, we consider an association rule of the form((
Age, Balance
) ∈
P
) ⇒ (
CardLoan
=
Yes
),which implies that bank customers whose ages and balances fall in a planar region
P
tend to use card loan with a high probability. We consider two classes of regions, rectangles and
admissible
(i.e. connected and
x
-monotone) regions. For each class, we propose efficient algorithms for computing the regions that give optimal association rules for
gain, support,
and
confidence,
respectively. We have implemented the algorithms for admissible regions, and constructed a system for visualizing the rules.
IDEA
Authors: Selfridge Peter G. , Srivastava Divesh , Wilson Lynn O.
Published: November 2005

The analysis of business data is often an ill-defined task characterized by large amounts of noisy data. Because of this, business data analysis must combine two kinds of intertwined tasks:
exploration
and
analysis.
Exploration is the process of finding the appropriate subset of data to analyze, and analysis is the process of measuring the data to provide the business answer. While there are many tools available both for exploration and for analysis, a single tool or set of tools may not provide full support for these intertwined tasks. We report here on a project that set out to understand a specific business data analysis problem and build an environment to support it. The results of this understanding are, first of all, a detailed list of requirements of this task; second, a set of capabilities that meet these requirements; and third, an implemented client-server solution that addresses many of these requirements and identifies others for future work. Our solution incorporates several novel perspectives on data analysis and combines a history mechanism with a graphical, re-usable representation of the analysis and exploration process. Our approach emphasizes using the database itself to represent as many of these functions as possible.
A Teradata content-based multimedia object manager for massively parallel architectures
Authors: O'Connell W. , Ieong I. T. , Schrader D. , Watson C. , Au G. , Biliris A. , Choo S. , Colin P. , Linderman G. , Panagos E. , Wang J. , Walter T.
Published: November 2005

The Teradata Multimedia Object Manager is a general-purpose content analysis multimedia server designed for symmetric multiprocessing and massively parallel processing environments. The Multimedia Object Manager defines and manipulates user-defined functions (UDFs), which are invoked in parallel to analyze or manipulate the contents of multimedia objects. Several computationally intensive applications of this technology, which use large persistent datasets, include fingerprint matching, signature verification, face recognition, and speech recognition/translation.
Fault-tolerant architectures for continuous media servers
Authors: Özden Banu , Rastogi Rajeev , Shenoy Prashant , Silberschatz Avi
Published: November 2005

Continuous media servers that provide support for the storage and retrieval of continuous media data (e.g., video, audio) at guaranteed rates are becoming increasingly important. Such servers, typically, rely on several disks to service a large number of clients, and are thus highly susceptible to disk failures. We have developed two fault-tolerant approaches that rely on admission control in order to meet rate guarantees for continuous media requests. The schemes enable data to be retrieved from disks at the required rate even if a certain disk were to fail. For both approaches, we present data placement strategies and admission control algorithms. We also present design techniques for maximizing the number of clients that can be supported by a continuous media server. Finally, through extensive simulations, we demonstrate the effectiveness of our schemes.
Two techniques for on-line index modification in shared nothing parallel databases
Authors: Achyutuni Kiran J. , Omiecinski Edward , Navathe Shamkant B.
Published: November 2005

Whenever data is moved across nodes in the parallel database system, the indexes need to be modified too. Index modification overhead can be quite severe because there can be a large number of indexes on a relation. In this paper, we study two alternatives to index modification, namely OAT (One-At-a-Time page movement) and BULK (bulk page movement). OAT and BULK are two extremes on the spectrum of the granularity of data movement. OAT and BULK differ in two respects: first, OAT uses very little additional disk space (at most one extra page), whereas BULK uses a large amount of disk space. Second, BULK uses sequential prefetch I/O to optimize on the number of I/Os during index modification, while OAT does not. Using an experimental testbed, we show that BULK is an order of magnitude faster than OAT. In terms of the impact on transaction performance during reorganization, BULK and OAT perform differently: when the number of indexes to be modified is either one or two, OAT has a lesser impact on the transaction performance degradation. However, when the number of indexes is greater than two, both techniques have the same impact on transaction performance.
Providing better support for a class of decision support queries
Authors: Rao Sudhir G. , Badia Antonio , van Gucht Dirk
Published: November 2005

Relational database systems do not effectively support complex queries containing quantifiers (
quantified queries
) that are increasingly becoming important in decision support applications.
Generalized quantifiers
provide an effective way of expressing such queries naturally. In this paper, we consider the problem of processing quantified queries within the generalized quantifier framework. We demonstrate that current relational systems are ill-equipped, both at the language and at the query processing level, to deal with such queries. We also provide insights into the intrinsic difficulties associated with processing such queries. We then describe the implementation of a quantified query processor, Q
2
P, that is based on multidimensional and boolean matrix structures. We provide results of performance experiments run on Q
2
P that demonstrate superior performance on quantified queries. Our results indicate that it is feasible to augment relational systems with query subsystems like Q
2
P for significant performance benefits for quantified queries in decision support applications.
A super scalar sort algorithm for RISC processors
Authors: Agarwal Ramesh C.
Published: November 2005

The compare and branch sequences required in a traditional sort algorithm can not efficiently exploit multiple execution units present in currently available high performance RISC processors. This is because of the long latency of the compare instructions and the sequential algorithm used in sorting. With the increased level of integration on a chip, this trend is expected to continue. We have developed new sort algorithms which eliminate almost all the compares, provide functional parallelism which can be exploited by multiple execution units, significantly reduce the number of passes through keys, and improve data locality. These new algorithms outperform traditional sort algorithms by a large factor.For the Datamation disk to disk sort benchmark (one million 100-byte records), at SIGMOD'94, Chris Nyberg et al presented several new performance records using DEC alpha processor based systems.We have implemented the Datamation sort benchmark using our new sort algorithm on a desktop IBM RS/6000 model 39H (66.6 MHz) with 8 IBM SSA 7133 disk drives (total cost $73K). The total elapsed time for the 100 MB sort was 5.1 seconds (vs the old uni-processor record of 9.1 seconds). We have also established a new price performance record (0.2¢ vs the old record of 0.9¢, as the cost of the sort). The entire sort processing was overlapped with I/O. During the read phase, we achieved a sustained BW of 47 MB/sec and during the write phase, we achieved a sustained BW of 39 MB/sec. Key extraction and sorting of one million 10-byte keys took only 0.6 second of CPU time. The rest of the CPU time was used in moving records, servicing I/O, and other overheads.Algorithmic details leading to this level of performance are described in this paper. A detailed analysis of the CPU time spent during various phases of the sort algorithm and I/O is also provided.
Spatial hash-joins
Authors: Lo Ming-Ling , Ravishankar Chinya V.
Published: November 2005

We examine how to apply the hash-join paradigm to spatial joins, and define a new framework for spatial hash-joins. Our spatial partition functions have two components: a set of bucket extents and an assignment function, which may map a data item into multiple buckets. Furthermore, the partition functions for the two input datasets may be different.We have designed and tested a spatial hash-join method based on this framework. The partition function for the inner dataset is initialized by sampling the dataset, and evolves as data are inserted. The partition function for the outer dataset is immutable, but may replicate a data item from the outer dataset into multiple buckets. The method mirrors relational hash-joins in other aspects. Our method needs no pre-computed indices. It is therefore applicable to a wide range of spatial joins.Our experiments show that our method outperforms current spatial join algorithms based on tree matching by a wide margin. Further, its performance is superior even when the tree-based methods have pre-computed indices. This makes the spatial hash-join method highly competitive both when the input datasets are dynamically generated and when the datasets have pre-computed indices.
Structures for manipulating proposed updates in object-oriented databases
Authors: Doherty Michael , Hull Richard , Rupawalla Mohammed
Published: November 2005

Support for virtual states and deltas between them is useful for a variety of database applications, including hypothetical database access, version management, simulation, and active databases. The Heraclitus paradigm elevates delta values to be "first-class citizens" in database programming languages, so that they can be explicitly created, accessed and manipulated.A fundamental issue concerns the trade-off between the "accuracy" or "robustness" of a form of delta representation, and the ease of access and manipulation of that form. At one end of the spectrum, code-blocks could be used to represent delta values, resulting in a more accurate capture of the intended meaning of a proposed update, at the cost of more expensive access and manipulation. In the context of object-oriented databases, another point on the spectrum is "attribute-granularity" deltas which store the net changes to each modified attribute value of modified objects.This paper introduces a comprehensive framework for specifying a broad array of forms for representing deltas for complex value types (tuple, set, bag, list, o-set and dictionary). In general, the granularity of such deltas can be arbitrarily deep within the complex value structure. Applications of this framework in connection with hypothetical access to, and "merging" of, proposed updates are discussed.
Goal-oriented buffer management revisited
Authors: Brown Kurt P. , Carey Michael J. , Livny Miron
Published: November 2005

In this paper we revisit the problem of achieving multi-class workload response time goals by automatically adjusting the buffer memory allocations of each workload class. We discuss the virtues and limitations of previous work with respect to a set of criteria we lay out for judging the success of any goal-oriented resource allocation algorithm. We then introduce the concept of
hit rate concavity
and develop a new goal-oriented buffer allocation algorithm, called
Class Fencing,
that is based on this concept. Exploiting the notion of hit rate concavity results in an algorithm that not only is as accurate and stable as our previous work, but also more responsive, more robust, and simpler to implement.
Semi-automatic, self-adaptive control of garbage collection rates in object databases
Authors: Cook Jonathan E. , Klauser Artur W. , Wolf Alexander L. , Zorn Benjamin G.
Published: November 2005

A fundamental problem in automating object database storage reclamation is determining how often to perform garbage collection. We show that the choice of collection rate can have a significant impact on application performance and that the "best" rate depends on the dynamic behavior of the application, tempered by the particular performance goals of the user. We describe two semi-automatic, self-adaptive policies for controlling collection rate that we have developed to address the problem. Using trace-driven simulations, we evaluate the performance of the policies on a test database application that demonstrates two distinct reclustering behaviors. Our results show that the policies are effective at achieving user-specified levels of I/O operations and database garbage percentage. We also investigate the sensitivity of the policies over a range of object connectivities. The evaluation demonstrates that semi-automatic, self-adaptive policies are a practical means for flexibly controlling garbage collection rate.
Cost-based optimization for magic
Authors: Seshadri Praveen , Hellerstein Joseph M. , Pirahesh Hamid , Leung T. Y. Cliff , Ramakrishnan Raghu , Srivastava Divesh , Stuckey Peter J. , Sudarshan S.
Published: November 2005

Magic sets rewriting is a well-known optimization heuristic for complex decision-support queries. There can be many variants of this rewriting even for a single query, which differ greatly in execution performance. We propose cost-based techniques for selecting an efficient variant from the many choices.Our first contribution is a practical scheme that models magic sets rewriting as a special join method that can be added to any cost-based query optimizer. We derive cost formulas that allow an optimizer to choose the best variant of the rewriting and to decide whether it is beneficial. The order of complexity of the optimization process is preserved by limiting the search space in a reasonable manner. We have implemented this technique in IBM's DB2 C/S V2 database system. Our performance measurements demonstrate that the cost-based magic optimization technique performs well, and that without it, several poor decisions could be made.Our second contribution is a formal algebraic model of magic sets rewriting, based on an extension of the multiset relational algebra, which cleanly defines the search space and can be used in a rule-based optimizer. We introduce the multiset
θ
-semijoin operator, and derive equivalence rules involving this operator. We demonstrate that magic sets rewriting for non-recursive SQL queries can be modeled as a sequential composition of these equivalence rules.
Materialized view maintenance and integrity constraint checking
Authors: Ross Kenneth A. , Srivastava Divesh , Sudarshan S.
Published: November 2005

We investigate the problem of incremental maintenance of an SQL view in the face of database updates, and show that it is possible to reduce the total time cost of view maintenance by materializing (and maintaining) additional views. We formulate the problem of determining the optimal set of additional views to materialize as an optimization problem over the space of possible view sets (which includes the empty set). The optimization problem is harder than query optimization since it has to deal with multiple view sets, updates of multiple relations, and multiple ways of maintaining each view set for each updated relation.We develop a memoing solution for the problem; the solution can be implemented using the expression DAG representation used in rule-based optimizers such as Volcano. We demonstrate that global optimization cannot, in general, be achieved by locally optimizing each materialized subview, because common subexpressions between different materialized subviews can allow nonoptimal local plans to be combined into an optimal global plan. We identify conditions on materialized subviews in the expression DAG when local optimization is possible. Finally, we suggest heuristics that can be used to efficiently determine a useful set of additional views to materialize.Our results are particularly important for the efficient checking of assertions (complex integrity constraints) in the SQL-92 standard, since the incremental checking of such integrity constraints is known to be essentially equivalent to the view maintenance problem.
Is GUI programming a database research problem?
Authors: Goyal Nita , Hoch Charles , Krishnamurthy Ravi , Meckler Brian , Suckow Michael
Published: November 2005

Programming nontrivial GUI applications is currently an arduous task. Just as the use of a declarative language simplified the programming of database applications, we ask whether we can do the same for GUI programming? Can we then import a large body of knowledge from database research? We answer these questions by describing our experience in building nontrivial GUI applications initially using C++ programming and subsequently using Logic++, a higher order Horn clause logic language on complex objects with object-oriented features. We abstract a GUI application as a set of event handlers. Each event handler can be conceptualized as a transition from the old screen/program state to a new screen/program state. We use a data centric view of the screen/program state (
i.e.,
every entity on the screen corresponds to proxy datum in the program) and express each event handler as a query dependent update, albeit a complicated one. To express such complicated updates we use Logic++. The proxy data are expressed as derived views that are materialized on the screen. Therefore, the system must be active in maintaining these materialized views. Consequently, each event handler is conceptually an update followed by a fixpoint computation of the proxy data. Based on our experience in building the GUI system, we observe that many database techniques such as view maintenance, active DB, concurrency control, recovery, optimization as well as language concepts such as higher order logic are useful in the context of GUI programming.
prospector
Authors: Choo S. , O'Connell W. , Linerman G. , Chen H. , Ganapathy K. , Biliris A. , Panagos E. , Schrader D.
Published: November 2005

The Prospector Multimedia Object Manager prototype is a general-purpose content analysis multimedia server designed for massively parallel processor environments. Prospector defines and manipulates user defined functions which are invoked in parallel to analyze/manipulate the contents of multimedia objects. Several computationally intensive applications of this technology based on large persistent datasets include: fingerprint matching, signature verification, face recognition, and speech recognition/translation [OIS96].
Incremental data structures and algorithms for dynamic query interfaces
Authors: Tanin Egemen , Beigel Richard , Shneiderman Ben
Published: November 2005

Dynamic query interfaces
(DQIs) form a recently developed method of database access that provides continuous realtime feedback to the user during the query formulation process. Previous work shows that DQIs are elegant and powerful interfaces to small databases. Unfortunately, when applied to large databases, previous DQI algorithms slow to a crawl. We present a new approach to DQI algorithms that works well with large databases.
Report from the NSF workshop on workflow and process automation in information systems
Authors: Sheth Amit , Georgakopoulos Dimitrios , Joosten Stef M. M. , Rusinkiewicz Marek , Scacchi Walt , Wileden Jack , Wolf Alexander L.
Published: November 2005

An interdisciplinary research community needs to address challenging issues raised by applying workflow management technology in information systems. This conclusion results from the NSF workshop on Workflow and Process Automation in Information Systems which was held at the State Botanical Garden of Georgia during May 8-10, 1996. The workshop brought together active researchers and practitioners from several communities, with significant representation from database and distributed systems, software process and software engineering, and computer supported cooperative work. The presentations given at the workshop are available in the form of an electronic proceedings of this workshop at http://lsdis.cs.uga.edu/activities/). This report is the joint work of selected representatives from the workshop and it documents the results of significant group discussions and exchange of ideas.
TPC-D—the challenges, issues and results
Authors: Bhashyam Ramesh
Published: November 2005

This paper covers what we at NCR have learned about the TPC-D benchmark as we executed and published our first set of volume points for the Teradata Database. Areas where customers should read the Full Disclosure Report carefully are pointed out as well as the weaknesses in the benchmark relative to real customer applications. The key execution and optimization elements of the Teradata Database and the 5100 WorldMark platform that contribute to our published results are discussed.
Min-max compression methods for medical image databases
Authors: Karadimitriou Kosmas , Tyler John M.
Published: November 2005

The volume of medical imaging data produced per year is rapidly increasing, overtaxing the capabilities of Picture Archival and Communication (PACS) systems. Image compression methods can lessen the problem by encoding digital images into more space-efficient forms. Image compression is achieved by reducing redundancy in the imaging data. Existing methods reduce redundancy in
individual
images. However, these methods ignore an additional source of redundancy, which is based on the common information stored in more than one image in a
set of similar images.
We use the term
"set redundancy"
to describe this type of redundancy. Medical image databases contain large sets of similar images, therefore they also contain significant amounts of set redundancy.This paper presents two methods that extract set redundancy from medical imaging data: the Min-Max Differential (MMD), and the Min-Max Predictive (MMP) methods. These methods can improve compression of standard image compression techniques for sets of medical images. Our tests compressing CT brain scans have shown an average of as much as 129% improvement for Huffman encoding, 93% for Arithmetic Coding, and 37% for Lempel-Ziv compression when they are combined with Min-Max methods. Both MMD and MMP are based on reversible operations, hence they provide
lossless
compression.
Similarity-based queries for time series data
Authors: Rafiei Davood , Mendelzon Alberto
Published: November 2005

We study a set of linear transformations on the Fourier series representation of a sequence that can be used as the basis for similarity queries on time-series data. We show that our set of transformations is rich enough to formulate operations such as moving average and time warping. We present a query processing algorithm that uses the underlying R-tree index of a multidimensional data set to answer similarity queries efficiently. Our experiments show that the performance of this algorithm is competitive to that of processing ordinary (exact match) queries using the index, and much faster than sequential scanning. We relate our transformations to the general framework for similarity queries of Jagadish et al.
Meaningful change detection in structured data
Authors: Chawathe Sudarshan S. , Garcia-Molina Hector
Published: November 2005

Detecting changes by comparing data snapshots is an important requirement for difference queries, active databases, and version and configuration management. In this paper we focus on detecting meaningful changes in hierarchically structured data, such as nested-object data. This problem is much more challenging than the corresponding one for relational or flat-file data. In order to describe changes better, we base our work not just on the traditional “atomic” insert, delete, update operations, but also on operations that move an entire sub-tree of nodes, and that copy an entire sub-tree. These operations allows us to describe changes in a semantically more meaningful way. Since this change detection problem is
NP
-hard, in this paper we present a heuristic change detection algorithm that yields close to “minimal” descriptions of the changes, and that has fewer restrictions than previous algorithms. Our algorithm is based on transforming the change detection problem to a problem of computing a minimum-cost edge cover of a bipartite graph. We study the quality of the solution produced by our algorithm, as well as the running time, both analytically and experimentally.
Improved query performance with variant indexes
Authors: O'Neil Patrick , Quass Dallan
Published: November 2005

The read-mostly environment of data warehousing makes it possible to use more complex indexes to speed up queries than in situations where concurrent updates are present. The current paper presents a short review of current indexing technology, including row-set representation by Bitmaps, and then introduces two approaches we call Bit-Sliced indexing and Projection indexing. A Projection index materializes all values of a column in RID order, and a Bit-Sliced index essentially takes an orthogonal bit-by-bit view of the same data. While some of these concepts started with the MODEL 204 product, and both Bit-Sliced and Projection indexing are now fully realized in Sybase IQ, this is the first rigorous examination of such indexing capabilities in the literature. We compare algorithms that become feasible with these variant index types against algorithms using more conventional indexes. The analysis demonstrates important performance advantages for variant indexes in some types of SQL aggregation, predicate evaluation, and grouping. The paper concludes by introducing a new method whereby multi-dimensional group-by queries, reminiscent of OLAP/Datacube queries but with more flexibility, can be very efficiently performed.
Highly concurrent cache consistency for indices in client-server database systems
Authors: Zaharioudakis Markos , Carey Michael J.
Published: November 2005

In this paper, we present four approaches to providing highly concurrent
B
+
-tree indices in the context of a data-shipping, client-server OODBMS architecture. The first performs all index operations at the server, while the other approaches support varying degrees of client caching and usage of index pages. We have implemented the four approaches, as well as the 2PL approach, in the context of the SHORE OODB system at Wisconsin, and we present experimental results from a performance study based on running SHORE on an IBM SP2 multicomputer. Our results emphasize the need for non-2PL approaches and demonstrate the tradeoffs between 2PL, no-caching, and the three caching alternatives.
Database buffer size investigation for OLTP workloads
Authors: Tsuei Thin-Fong , Packer Allan N. , Ko Keng-Tai
Published: November 2005

It is generally accepted that On-Line Transaction Processing (OLTP) systems benefit from large database memory buffers. As enterprise database systems become larger and more complex, hardware vendors are building increasingly large systems capable of supporting huge memory configurations. Database vendors in turn are developing buffer schemes to exploit this physical memory.

How much will these developments benefit OLTP workloads? Through empirical studies on databases sized comparably to those seen in the real-world, this paper presents the characteristics of an industry-standard OLTP benchmark as memory buffer size changes. We design the experiments to investigate how the database size, the buffer size and the number of CPUs impact performance, in particular the throughput and the buffer hit rate on Symmetric Multiprocessor Systems. The relationships of these major database attributes are plotted and key observations are summarized. We discuss how these relationships change as the number of CPUs changes. We further quantify the relationships: 1) between database buffer data hit rate, buffer size and database size, 2) between throughput, buffer data hit rate and database size and 3) between throughput and number of CPUs. Algorithms, rules-of-thumb and examples are presented for predicting performance, sizing memory and making trade-offs between adding more memory and increasing the number of CPUs.