bluuebunny/crossref_metadata_2025 huggingface dataset:
WOODSS and the Web
Authors: Medeiros C. B. , Perez-Alcazar J. , Digiampietri L. , Pastorello G. Z. , Santanche A. , Torres R. S. , Madeira E. , Bacarin E.
Published: November 2005

This paper discusses ongoing research on scientific workflows at the Institute of Computing, University of Campinas (IC - UNICAMP) Brazil. Our projects with bio-scientists have led us to develop a scientific workflow infrastructure named WOODSS. This framework has two main objectives in mind: to help scientists to specify and annotate their models and experiments; and to document collaborative efforts in scientific activities. In both contexts, workflows are annotated and stored in a database. This "annotated scientific workflow" database is treated as a repository of (sometimes incomplete) approaches to solving scientific problems. Thus, it serves two purposes: allows comparison of distinct solutions to a problem, and their designs; and provides reusable and executable building blocks to construct new scientific workflows, to meet specific needs. Annotations, moreover, allow further insight into methodology, success rates, underlying hypotheses and other issues in experimental activities.The many research challenges faced by us at the moment include: the extension of this framework to the Web, following Semantic Web standards; providing means of discovering workflow components on the Web for reuse; and taking advantage of planning in Artificial Intelligence to support composition mechanisms. This paper describes our efforts in these directions, tested over two domains - agro-environmental planning and bioinformatics.
Scheduling of scientific workflows in the ASKALON grid environment
Authors: Wieczorek Marek , Prodan Radu , Fahringer Thomas
Published: November 2005

Scheduling is a key concern for the execution of performance-driven Grid applications. In this paper we comparatively examine different existing approaches for scheduling of scientific workflow applications in a Grid environment. We evaluate three algorithms namely genetic, HEFT, and simple "myopic" and compare incremental workflow partitioning against the full-graph scheduling strategy. We demonstrate experiments using real-world scientific applications covering both balanced (symmetric) and unbalanced (asymmetric) workflows. Our results demonstrate that full-graph scheduling with the HEFT algorithm performs best compared to the other strategies examined in this paper.
Efficient calendar based temporal association rule
Authors: Verma Keshri , Vyas O. P.
Published: November 2005

Associationship is an important component of data mining. In real world data the knowledge used for mining rule is almost time varying. The item have the dynamic characteristic in terms of transaction, which have seasonal selling rate and it hold time-based associationship with another item. It is also important that in database, some items which are infrequent in whole dataset but those may be frequent in a particular time period. If these items are ignored then associationship WVW200R3100221-398 result will no longer be accurate. To restrict the time based associationship calendar based pattern can be used [YPXS03]. A calendar unit such as months and days, clock units, such as hours and seconds & specialized units, such as business days and academic years, play a major role in a wide range of information system applications[BX00].Most of the popular associationship rule mining methods are having performance bottleneck for database with different characteristics. Some of the methods are efficient for sparse dataset where as some are good for a dense dataset. Our focus is to find effective time sensitive algorithm using H-struct called temporal H-mine, which takes the advantage of this data structure and dynamically adjusts links in the mining process [PHNTY01]. It is faster in traversing & advantage of precisely predictable spaces overhead. It can be scaled up to large database by database partitioning, end when dataset becomes dense, conditionally temporal FP-tree. can be constructed dynamically as part of mining.
Report on the workshop on wrapper techniques for legacy data systems
Authors: Thiran Ph. , Risch T. , Costilla C. , Henrard J. , Kabisch Th. , Petrini J. , van den Heuvel W-J. , Hainaut J-L.
Published: November 2005

This report summarizes the presentations and discussions of the first workshop on Wrapper Techniques for Legacy Data Systems which was held in Delft on November 12 2004. This workshop was co-located with the 2004 WCRE conference. This workshop entails to our best knowledge the first in its kind, concentrating on challenging research issues regarding the development of wrappers for legacy data systems.
Exchange, integration, and consistency of data
Authors: Bertossi Leopoldo , Chomicki Jan , Godfrey Parke , Kolaitis Phokion G. , Thomo Alex , Zuzarte Calisto
Published: November 2005

The "ARISE/NISR Workshop on Exchange and Integration of Data" was held at the IBM Center for Advanced Studies, Toronto Lab., between October 7-9, 2004.
John Wilkes speaks out
Authors: Winslett Marianne
Published: November 2005

Welcome to this installment of ACM SIGMOD Record's series of interviews with distinguished members of the database community. I'm Marianne Winslett, and today [February 2004] we are at the Department of Computer Science at the University of Illinois at Urbana-Champaign. I have here with me John Wilkes, who is an HP Fellow in the Internet Systems and Storage Laboratory at Hewlett Packard Laboratories in Palo Alto, California, where his research focuses on the design and management of storage systems. John is a member of the editorial board of ACM Transactions on Computer Systems, and until recently he was a member of the Technical Council of the Storage Network Industry Association. John is an ACM Fellow, and his PhD is from the University of Cambridge. So, John, welcome!
A functional model for macro-databases
Authors: Rafanelli M. , Ricci F. L.
Published: November 2005

Recently there have been numerous proposals aimed at correcting the deficiency in existing database models to manipulate macro data (such as summary tables). The authors propose a new functional model, Mefisto, based on the definition of a new data structure, the “statistical entity”, and on a set of operations capable of manipulating this data structure by operating at metadata level.
Database systems
Authors: Silberschatz Avi , Stonebraker Michael , Ullman Jeffrey D.
Published: November 2005

The history of database system research in the U.S. is one of exceptional productivity and startling economic impact. Barely twenty years old as a basic science research field, database research conducted with Federal support in the nation's universities and in its industrial research laboratories has fueled an information services industry estimated at $10 billion per year in the U.S. alone. This industry has grown at an average rate of 20 percent per year since 1965 and is continuing to expand at this rate. Achievements in database research underpin fundamental advances in communications systems, transportation and logistics, financial management, knowledge-based systems, accessibility to scientific literature, and a host of other civilian and defense applications. They also serve as the foundation for considerable progress in basic science in various fields ranging from computing to biology.
Summary of the final report of the NSF workshop on scientific database management
Authors: French James C. , Jones Anita K. , Pfaltz John L.
Published: November 2005

The National Science Foundation sponsored a two day workshop hosted by the University of Virginia on March 12-13, 1990 at which representatives from the earth, life, and space sciences met with computer scientists to discuss the issues facing the scientific community in the area of database management. The workshop
1
participants concluded that initiatives by the National Science Foundation and other funding agencies, as well as specific discipline professional societies are urgently needed to address the problems facing scientists with respect to data management. This article presents a condensed version of the workshop final report emphasizing the technical research issues.
New hope on data models and types
Authors: Abiteboul Serge , Buneman Peter , Delobel Claude , Hull Richard , Kanellakis Paris , Vianu Victor
Published: November 2005

In May, 1990, a small workshop was held in New Hope, Pennsylvania, to discuss the fundamental issues raised by continuing work on the interface between databases and programming languages. Four topics were addressed: new directions stemming from object-oriented data models, contributions of type theory to database programming languages (DBPLs), applications of logic to DBPL issues, and DBPL implementations.

This workshop was organized under the auspices of the INRIA-NSF program,
Languages for Databases and Knowledge Bases
.
Deductive databases
Authors: Ullman Jeffrey D. , Zaniolo Carlo
Published: November 2005

In the recent years, Deductive Databases have been the focus of intense research, which has brought dramatic advances in theory, systems and applications. A salient feature of deductive databases is their capability of supporting a declarative, rule-based style of expressing queries and applications on databases. As such, they find applications in disparate areas, such as knowledge mining from databases, and computer-aided design and manufacturing systems.

In this paper, we briefly review the key concepts behind deductive databases and their newly developed enabling technology. Then, we describe current research on extending the functionality and usability of deductive databases and on providing a synthesis of deductive databases with procedural and object-oriented approaches.
Parallel database systems
Authors: DeWitt David J. , Gray Jim
Published: November 2005

The concept of parallel database machines consisting of exotic hardware has been replaced by a fairly conventional shared-nothing hardware base along with a highly parallel dataflow software architecture. Such a design provides speedup and scaleup in processing relational database queries. This paper reviews the techniques used by such systems, and surveys current commercial and research systems.
Selected database research at Stanford
Authors: Keller Arthur , Rathmann Peter , Ullman Jeff , Wiederhold Gio
Published: November 2005

This report describes seven projects at the Computer Science Department of Stanford University that may be relevant to SIGMOD community.
Handling missing data by using stored truth values
Authors: Gessert G. H.
Published: November 2005

This paper proposes a method for handling inapplicable and unknown missing data. The method is based on: (1) storing default values (instead of null values) in place of missing data, (2) storing truth values that describe the logical status of the default values in corresponding fields of corresponding tables. Four valued logic is used so that the logical status of the default data values can be described as, not just true or false, but also as inapplicable or unknown. This method, in contrast to the “hidden byte” approach, has two important advantages: (1) Because the logical status of all data is represented explicitly in tables, all 4-valued operations can be handled via a 2-valued data manipulation language, such as SQL. Language extensions for handling missing data (e.g., “IS NULL”) are not necessary. (2) Because data fields always contain a default value (as opposed to a null value or mark), it is possible to do arithmetic across missing data and to interpret the logical status of the result by means of logical operations on the corresponding stored truth values.
Practitioner problems in need of database research
Authors: Thomas Gomer , Kawagoe K. , Krishnamurthy R. , Imielinski T. , Reiner D. , Wolski A.
Published: November 2005

The bottlenecks between research and product development are well known. It typically takes a very long time for ideas coming out of research labs to make their way into products, and developers often face practical problems which do not seem to be addressed by currently available research results. The term “technology transfer” is often used to describe the process of overcoming these bottlenecks.
Temporal relations in geographic information systems
Authors: Barrera Renato , Frank Andrew , Al-Taha Khaled
Published: November 2005

A workshop on temporal relations in Geographic Information Systems (GIS) was held on October 12-13, 1990, at the University of Maine. The meeting, sponsored by the National Center for Geographic Information and Analysis (NCGIA), gathered specialists on Geography, GIS, and Computer Science to discuss users' requirements of temporal GIS and to identify the corresponding research issues.
A retrospective on database application development frameworks
Authors: Rowe Lawrence A.
Published: November 2005

Four application framework models developed by the author for database application development systems are described. The key feature of these systems is to provide a model for the definition of high level objects that represent interface abstraction that can be used to build an application. Structuring application code around interface objects reduces the conceptual distance between the executing program and its specification. At the same time, good programming practices must be supported (e.g., code modularity, reusable components, and information hiding).
An overview of GOOD
Authors: Paredaens Jan , Van den Bussche Jan , Andries Marc , Gemis Marc , Gyssens Marc , Thyssens Inge , Van Gucht Dirk , Sarathy Vijay , Saxton Lawrence
Published: November 2005

GOOD is an acronym, standing for
Graph-Oriented Object Database
. GOOD is being developed as a joint research effort of Indiana University and the University of Antwerp. The main thrust behind the project is to indicate general concepts that are fundamental to any graph-oriented database user-interface. GOOD does not restrict its attention to well-considered topics such as ad-hoc query facilities, but wants to cover the full spectrum of database manipulations. The idea of graph-pattern matching as a uniform object manipulation primitive offers a uniform framework in which this can be accomplished.
Graphical user interfaces for the management of scientific experiments and data
Authors: Ioannidis Yannis E. , Livny Miron , Haber Eben M.
Published: November 2005

It is often stated that the three most important factors that determine the success or failure of a database system are performance, performance, performance! The experience of the last twenty years with relational systems has shown that at least one of these three references to performance implies that of end-users when interacting with the system to access data, i.e., user productivity. Although declarative query languages like SQL and QUEL represent major improvements over procedural programming languages like COBOL, the overall consensus is that they are too complex for many users. The need for more intuitive and easier to learn and use interfaces to database systems is always current.
Annotating answers with their properties
Authors: Motro Amihai
Published: November 2005

When responding to queries, humans often volunteer additional information
about
their answers. Among other things, they may
qualify
the answer as to its reliability, and they may provide some
abstract
characterization of the answer. This paper describes a user interface to relational databases that similarly annotates its answers with their properties. The process assumes that various assertions about properties of the data have been stored in the database (meta-information). These assertions are then used to infer properties of each answer provided by the system (meta-answers). Meta-answers are offered to users along with each answer issued, and help them to assess the value and meaning of the information that they receive.
An annotated bibliography on object-orientation and deduction
Authors: Conrad Stefan , Gogolla Martin
Published: November 2005

This note tries to briefly survey research activities and results on the integration of object-oriented concepts and deductive database languages.
Database research at IPSI
Authors: Neuhold Erich , Turau Volker
Published: November 2005

At the Integrated Publication and Information Systems Institute (IPSI) of the GMD (Gesellschaft für Mathematik und Datenverarbeitung) database research is focused towards distributed database management systems to support the integration of heterogeneous multi-media information bases needed in an integrated publishing environment. The objective is to investigate advanced object-oriented and active data modelling concepts together with the principles of distributed data stores and data management. The unifying basis for the database research is the object-oriented data model VML developed in the project VODAK over the last four years. The data model is based on recursively defined meta classes, classes and instance hierarchies paired with a strict separation of structural and operational definitions in a polymorphic type system.

This report describes the highlights of the work on the VODAK database system, the research efforts in heterogeneous database integration and the research plans of the multimedia database project as well as applications of our system in different environments such as hypertext and office automation.
Semantic heterogeneity as a result of domain evolution
Authors: Ventrone Vincent
Published: November 2005

We describe examples of problems of semantic heterogeneity in databases due to “domain evolution”, as it occurs in both single- and multidatabase systems. These problems occur when the semantics of values of a particular domain change over time in ways that are not amenable to applying simple mappings between “old” and “new” values. The paper also proposes facilities and strategies for solving such problems.
An anatomy of the information resource semantic abstraction
Authors: Kalinichenko Leonid
Published: November 2005

Semantic abstraction mapping establishing a correspondence between an information resource and an application is considered to be a basic notion providing for the study of semantic interoperability of heterogeneous information resources. The structure and necessary properties of a resource class application abstraction are considered. Intensional model-based properties of the abstraction mapping are introduced as provable conditions of a class assertion abstraction and an operation concretization
Semantic heterogeneity in distributed geographic databases
Authors: Worboys M. F. , Deen S. M.
Published: November 2005

This paper considers the special problems of semantic heterogeneity in a distributed system of databases containing spatially referenced information. Two forms of semantic heterogeneity are defined.
Generic
semantic heterogeneity arises when nodes are using different generic conceptual models of the spatial information.
Contextual
semantic heterogeneity is caused by the particular local environmental conditions at nodes. It is contextual heterogeneity which is especially the consideration with geographic databases and to which the paper devotes most attention. Two possible solutions are proposed, one founded on transforming processors between models and a second using a canonical model which is a generalization of existing generic spatial models.
On the semantic equivalence of heterogeneous representations in multimodel multidatabase systems
Authors: Gangopadhyay Dipayan
Published: November 2005

We present in this paper an extensible metalevel system, called M(DM), in which the syntax and the semantics of data models, schemas, and databases can be uniformly described. We show with examples how to derive in M(DM) the semantic equivalence (or lack thereof) of symbols across different reresentation systems. We argue that, because of the inherent incompleteness of legacy databases, semantic equivalence must in general be ascertained by additional a posteriori assertions that are external to the representation under consideration.
A note on the strategy space of multiway join query optimization problem in parallel systems
Authors: Tan Kian-Lee , Lu Hongjun
Published: November 2005

In this short note, we estimate the search space of optimizing multiway join queries in multiprocessor computer systems, i.e. the number of possible query execution plans that need to be considered.
Query optimization for parallel execution
Authors: Ganguly Sumit , Hasan Waqar , Krishnamurthy Ravi
Published: November 2005

The decreasing cost of computing makes it economically viable to reduce the response time of decision support queries by using parallel execution to exploit inexpensive resources. This goal poses the following query optimization problem:
Minimize response time subject to constraints on throughput
, which we motivate as the dual of the traditional DBMS problem. We address this novel problem in the context of Select-Project-Join queries by extending the execution space, cost model and search algorithm that are widely used in commercial DBMSs. We incorporate the sources and deterrents of parallelism in the traditional execution space. We show that a cost model can predict response time while accounting for the new aspects due to parallelism. We observe that the response time optimization metric violates a fundamental assumption in the dynamic programming algorithm that is the linchpin in the optimizers of most commercial DBMSs. We extend dynamic programming and show how optimization metrics which correctly predict response time may be designed.
Exploiting inter-operation parallelism in XPRS
Authors: Hong Wei
Published: November 2005

In this paper, we study the scheduling and optimization problems of parallel query processing using interoperation parallelism in a shared-memory environment and propose our solutions for XPRS. We first study the scheduling problem of a set of a continuous sequence of independent tasks that are either from a bushy tree plan of a single query or from the plans of multiple queries, and present a clean and simple scheduling algorithm. Our scheduling algorithm achieves maximum resource utilizations by running an IO-bound task and a CPU-bound task in parallel with carefully calculated degrees of parallelism and maintains the maximum resource utilizations by dynamically adjusting the degrees of parallelism of running tasks whenever necessary. Real performance figures are shown to confirm the effectiveness of our scheduling algorithm. We also revisit the optimization problem of parallel execution plans of a single query and extend our previous results to consider inter-operation parallelism by introducing a new cost estimation method to the query optimizer based on our scheduling algorithm.
A performance analysis of alternative multi-attribute declustering strategies
Authors: Ghandeharizadeh Shahram , DeWitt David J. , Qureshi Waheed
Published: November 2005

During the past decade, parallel database systems have gained increased popularity due to their high performance, scalability and availability characteristics. With the predicted future database sizes and the complexity of queries, the scalability of these systems to hundreds and thousands of processors is essential for satisfying the projected demand. Several studies have repeatedly demonstrated that both the performance and scalability of a paralel database system is contingent on the physical layout of data across the processors of the system. If the data is not declustered properly, the execution of an operator might waste resources, reducing the overall processing capability of the system.

With earlier, single attribute declustering strategies, such as those found in Tandem, Teradata, Gamma, and Bubba parallel database systems, a selection query including a range predicate on any attribute other than the partitioning attribute must be sent to all processors containing tuples of the relation. By directing a query with minimal resource requirements to processors that contain no relevant tuples, the system wastes CPU cycles, communication bandwidth, and I/O bandwidth, reducing its overall processing capability. As a solution, several multi-attribute declustering strategies have been proposed. However, the performance of these declustering techniques have not previously been compared to one another nor with a single attribute partitioning strategy. This paper, compares the performance of Multi-Attribute GrId deClustering (MAGIC) strategy and Bubba's Extended Range Declustering (BERD) strategy with one another and with the range partitioning strategy. Our results indicate that MAGIC outperforms both range and BERD in all experiments conducted in this study.
Using delayed commitment in locking protocols for real-time databases
Authors: Agrawal D. , El Abbadi A. , Jeffers R.
Published: November 2005

In this paper, we propose locking protocols that are useful for real-time databases. Our approach is motivated from two main observations. First, locking protocols are widely accepted and used in most database systems. Second, in real-time databases it has been shown that the blocking behavior of transactions in locking protocols results in performance degradation. We use a new relationship between locks called ordered sharing to eliminate blocking that arises in the traditional locking protocols. Ordered sharing eliminates blocking of read and write operations but may result in delayed commitment. Since in real-time databases, timeliness and not response time is the crucial factor, or protocols exploit this delay to allow transactions to execute within the slacks of delayed transactions. We compare the performance of the proposed protocols with the two phase locking protocol for real-time databases. Our experiments indicate that the propose protocols significantly reduce the percentage of missed deadlines in the system for a variety of workloads.
Performance analysis of coherency control policies through lock retention
Authors: Dan Asit , Yu Philip S.
Published: November 2005

Buffer coherency control can be achieved through retaining a lock (shared, exclusive, etc.) on each page in the buffer, even after the requesting transaction has committed. Depending upon the lock mode held for retention and the compatibility of lock modes specified, different retention policies can be devised. In addition to tracking the validity of the buffered data granules, additional capabilities can be provided such as deferred writes to support no-force policy on commit, (node) location identification of valid granules to support remote memory accesses, and shared/exclusive lock retention to reduce the number of global lock requests for concurrency control. However, these can have serious implications not only on the performance but also on the recovery complexity. In this paper, five different integrated coherency policies are considered. We classify these policies into three different categories according to their recovery requirements. A performance study based on analytic models is provided to understand the trade-offs on both maximum throughputs and response times of the policies with a similar level of recovery complexity and the performance gain achievable through increasing the level of recovery complexity.
Efficient and flexible methods for transient versioning of records to avoid locking by read-only transactions
Authors: Mohan C. , Pirahesh Hamid , Lorie Raymond
Published: November 2005

We present efficient and flexible methods which permit read-only transactions that do not mind reading a possibly slightly old, but still consistent, version of the data base to execute without acquiring locks. This approach avoids the undesirable interferences between such queries and the typically shorter update transactions that cause unnecessary and costly delays. Indexed access by such queries is also supported, unlike by the earlier methods. Old versions of records are maintained only in a
transient
fashion. Our methods are characterized by their flexibility (number of versions maintained and the timing of version switches, supporting partial rollbacks, and different recovery and buffering methods) and their efficiency (logging, garbage collection, version selection, and incremental, record-level versioning). Distributed data base environments are also supported, including commit protocols with the read-only optimization. We also describe efficient methods for garbage collecting unneeded older versions.
Analysis of recovery in a database system using a write-ahead log protocol
Authors: Jhingran Anant , Khedkar Pratap
Published: November 2005

In this paper we examine the recovery time in a database system using a Write-Ahead Log protocol, such as ARIES [9], under the assumption that the buffer replacement policy is strict LRU. In particular, analytical equations for log read time, data I/O, log application, and undo processing time are presented. Our initial model assumes a read/write ratio of one, and a uniform access pattern. This is later generalized to include different read/write ratios, as well as a “hot set” model (i.e. x% of the accesses go to y% of the data). We show that in the uniform access model, recovery is dominated by data I/O costs, but under extreme hot-set conditions, this may no longer be true. Furthermore, since we derive anaytical equations, recovery can be analyzed for any set of parameter conditions not discussed here.
A qualitative comparison study of data structures for large line segment databases
Authors: Hoel Erik G. , Samet Hanan
Published: November 2005

A qualitative comparative study is performed of the performance of three popular spatial indexing methods - the R-tree, R
+
-tree, and the PMR quadtree-in the context of processing spatial queries in large line segment databases. The data is drawn from the TIGER/Line files used by the Bureau of the Census to deal with the road networks in the US. The goal is not to find the best data structure as this is not generally possible. Instead, their comparability is demonstrated and an indication is given as to when and why their performance differs. Tests are conducted with a number of large datasets and performance is tabulated in terms of the complexity of the disk activity in building them, their storage requirements, and the complexity of the disk activity for a number of tasks that include point and window queries, as well as finding the nearest line segment to a given point and an enclosing polygon.
Evaluation of remote backup algorithms for transaction processing systems
Authors: Polyzois Christos A. , Garcia-Molina Hector
Published: November 2005

A remote backup is a copy of a primary database maintained at a geographically separate location and is used to increase data availability. Remote backup systems are typically log-based and can be classified into 2-safe and 1-safe, depending on whether transactions commit at both sites simultaneously or they first commit at the primary and are later propagated to the backup. We have built an experimental database system on which we evaluated the performance of the epoch algorithm, a 1-safe algorithm we have developed, and compared it with the 2-safe approach under various conditions. We also report on the use of multiple log streams to propagate information from the primary to the backup.
Realizing a temporal complex-object data model
Authors: Käfer Wolfgang , Schöning Harald
Published: November 2005

Support for temporal data continues to be a requirement posed by many applications such as VLSI design and CAD, but also in conventional applications like banking and sales. Furthermore, the strong demand for complex-object support is known as an inherent fact in design applications, and also emerges for advance “conventional” applications. Thus, new advanced database management systems should include both features, i.e. should support
temporal complex-objects
. In this paper, we present such a temporal complex-object data model. The central notion of our temporal complex-object data model is a
time slice
, representing one state of a complex object. We explain the mapping of time slices onto the complex objects supported by the MAD model (which we use for an example of a
non-temporal
complex-object data model) as well as the transformation process of operations on temporal complex-objects into MAD model operations. Thereby, the basic properties of the MAD model are a prerequisite for our approach. For example, time slices can only be directly stored, if non-disjunct (i.e. over-lapping) complex objects are easily handled in the underlying complex-object data model.
Compensation-based on-line query processing
Authors: Srinivasan V. , Carey Michael J.
Published: November 2005

It is well known that using conventional concurrency control techniques for obtaining serializable answers to long-running queries leads to an unacceptable drop in system performance. As a result, most current DBMSs execute such queries under a reduced degree of consistency, thus providing non-serializable answers. In this paper, we present a new and highly concurrent approach for processing large decision support queries in relational databases. In this new approach, called compensation-based query processing, concurrent updates to any data participating in a query are communicated to the query's on-line query processor, which then compensates for these updates so that the final answer reflects changes caused by the updates. Very high concurrency is achieved by locking data only briefly, while still delivering transaction-consistent answers to queries.
ARIES/IM: an efficient and high concurrency index management method using write-ahead logging
Authors: Mohan C. , Levine Frank
Published: November 2005

This paper provides a comprehensive treatment of index management in transaction systems. We present a method, called
ARIESIIM (Algorithm for Recovery and Isolation Exploiting Semantics for Index Management)
, for concurrency control and recovery of B
+
-trees. ARIES/IM guarantees serializability and uses write-ahead logging for recovery. It supports very high concurrency and good performance by (1) treating as the lock of a key the same lock as the one on the corresponding record data in a data page (e.g., at the record level), (2) not acquiring, in the interest of permitting very high concurrency, commit duration locks on index pages even during index structure modification operations (SMOs) like page splits and page deletions, and (3) allowing retrievals, inserts, and deletes to go on concurrently with SMOs. During restart recovery, any necessary
redos
of index changes are always performed in a page-oriented fashion (i.e., without traversing the index tree) and, during normal processing and restart recovery, whenever possible
undos
are performed in a page-oriented fashion. ARIES/IM permits different granularities of locking to be supported in a flexible manner. A subset of ARIES/IM has been implemented in the OS/2 Extended Edition Database Manager. Since the locking ideas of ARIES/IM have general applicability, some of them have also been implemented in SQL/DS and the VM Shared File System, even though those systems use the shadow-page technique for recovery.
A supplement to sampling-based methods for query size estimation in a database system
Authors: Ling Yibei , Sun Wei
Published: November 2005

Sampling-based methods for estimating relation sizes after relational operators such as selections, joins and projections have been intensively studied in recent years. Methods of this type can achieve high estimation accuracy and efficiency. Since the dominating overhead involved in a sampling-based method is the sampling cost, different variants of sampling methods are proposed so as to minimize the sampling percentage (thus reducing the sampling cost) while maintaining the estimation accuracy in terms of the
confidence level
and
relative error
(to be precisely defined later in
Section 2
). In order to determine the minimal sampling percentage, the overall characteristics of the data such as the mean and variance are needed. Currently, the representative sampling-based methods in literature are based on the assumption that overall characteristics of data are unavailable, and thus a significant amount of effort is dedicated to estimating these characteristics so as to approach the optimal (minimal) sampling percentage. The estimation for these characteristics incurs cost as well as suffers the estimation error. In this short essay, we point out that the exact values of these characteristics of data can be kept track of in a database system at a negligible overhead. As a result, the minimal sampling percentage while ensuring the specified relative error and confidence level can be precisely determined.
A complex benchmark for logic programming and deductive databases, or who can beat the N-queens?
Authors: Kießling Werner
Published: November 2005

The N-queens problem with its long history and inherent complexity is a challenging benchmark target. We present our solution and performance results, hoping that this will stimulate a sort of benchmark competition for tough problems.
Schema evolution in database systems
Authors: Roddick John F.
Published: November 2005

Schema Evolution is the ability of a database system to respond to changes in the real world by allowing the schema to evolve. In many systems this property also implies a retaining of past states of the schema. This latter property is necessary if data recorded during the lifetime of one version of the schema is not to be made obsolete as the schema changes. This annotated bibliography investigates current published research with respect to the handling of changing schemas in database systems.
Parametric databases
Authors: Gadia Shashi K.
Published: November 2005

Our model, algebra and SQL-like query language for temporal databases extend naturally to parametric data, of which spatial, temporal, spatio-temporal, belief and ordinary data are special cases.
Schema transformation without database reorganization
Authors: Tresch Markus , Scholl Marc H.
Published: November 2005

We argue for avoiding database reorganizations due to schema modification in object-oriented systems, since these are expensive operations and they conflict with reusing existing software components. We show that data independence, which is a neglected concept in object databases, helps to avoid reorganizations in case of capacity preserving and reducing schema transformations. We informally present a couple of examples to illustrate the idea of a schema transformation methodology that avoids database reorganization.
Workshop report
Authors: Özsu M. Tamer , Dayal Umeshwar , Valduriez Patrick
Published: November 2005

The International Workshop on Distributed Object Management (IWDOM) was organized in Edmonton, Canada on the University of Alberta campus between August 19-21, 1992. The Workshop addressed the theory and practice of developing distributed object-oriented database management systems (OODBMS). The objective was to take note of the state-of-the-art in distributed object management technology and to identify the issues that need to be resolved. The recent developments in standards-related activities, notably the release of the CORBA specifications by the Object Management Group, contributed to the timeliness and importance of the Workshop.
Response to “Remarks on two new theorems of Date and Fagin”
Authors: Date C. J. , Fagin Ronald
Published: November 2005

In [DF92], we present simple conditions, which we now describe, for guaranteeing higher normal forms for relational databases. A key is
simple
if it consists of a single attribute. We show in [DF92] that if a relation schema is in third normal form (3NF) and every key is simple, then it is in projection-join normal form (sometimes called fifth normal form), the ultimate normal form with respect to projections and joins. We also show in [DF92] that if a relation schema is in Boyce-Codd normal form (BCNF) and
some
key is simple, then it is in fourth normal form (4NF). These results give the database designer simple sufficient conditions, defined in terms of functional dependencies alone, that guarantee that the schema being designed is automatically in higher normal forms.
Change at ONR, and many funding announcements elsewhere
Authors: Winslett Marianne
Published: November 2005

In this issue, we describe recent changes at the US Office of Naval Research, and then cover a dozen recent announcements of funding in the US for postdocs, sabbaticals, summer jobs, equipment, and research grants—just about anything you might need—from DARPA, the Army, the Air Force, NSF, NIST, and the National Center for Automated Information Research. We also list the newly funded NSF Grand Challenge proposals.
Schema evolution in OODBs using class versioning
Authors: Monk Simon , Sommerville Ian
Published: November 2005

This paper describes work carried out on a model for the versioning of class definitions in an object-oriented database. By defining update and backdate functions on attributes of the previous and current version of a class definition, instances of any version of the class can be converted to instances of any other version. This allows programs written to access an old version of the schema to still use data created in the format of the changed schema.
Database compression
Authors: Roth Mark A. , Van Horn Scott J.
Published: November 2005

Despite the fact that computer memory costs have decreased dramatically over the past few years, data storage still remains, and will probably always remain, an important cost factor for many large scale database applications. Compressing data in a database system is attractive for two reasons: data storage reduction and performance improvement. Storage reduction is a direct and obvious benefit, while performance improves because smaller amounts of physical data need to be moved for any particular operation on the database.

We address several aspects of reversible data compression and compression techniques:

general concepts of data compression;

a number of compression techniques;

a comparison of the effects of compression on common data types;

advantages and disadvantages of compressing data; and

future research needs.
Report of the Workshop on Semantic Heterogeneity and Interpolation in multidatabase Systems
Authors: Drew Pam , King Roger , McLeod Dennis , Rusinkiewicz Marek , Silberschatz Avi
Published: November 2005

This report presents a review of the problems that were discussed during the Workshop on Semantic Heterogeneity and Interoperability in Multidatabase Systems. The workshop participants discussed the importance of interoperation in the U S WEST information processing environment and the progress that has been achieved in three major research areas: resolution of semantic heterogeneity among cooperating heterogeneous systems, transaction management in such environments, and software architecture for interoperation. The workshop provided researchers with necessary feedback from the industrial perspective and helped in identifying the major issues that need further research. The following problems concerning the applicability of the methods proposed for data processing in the heterogeneous, autonomous information systems have been identified: (i) many of the assumptions made in the research community are too restrictive to make the results directly applicable to existing environments; (ii) performance ramifications of various heterogeneous architectures need to be understood; (iii) the prototype systems need to be put to the test with real data, schemas, and transaction streams to verify their utility.
Options in physical database design
Authors: Graefe Goetz
Published: November 2005

A cornerstone of modern database systems is physical data independence, i.e., the separation of a type and its associated operations from its physical representation in memory and on storage media. Users manipulate and query data at the logical level; the DBMS translates these logical operations to operations on files, indices, records, and disks. The efficiency of these physical operations depends very much on the choice of data representations.

Choosing a physical representation for a logical database is called physical database design. The number of possible choices in physical database design is very large; moreover, they very often interact with each other. We attempt to list and classify these choices and to explore their interactions. The purpose of this paper is to provide an overview of possible options to the DBMS developer and some guidance to the DBMS administrator and user.

While much of our discussion will draw on the relational data model, physical database design is of even more importance for object-oriented and extensible systems. The reasons are simple: First, the number of logical data types and their operations is larger, requiring and permitting more choices for their representation. Second, the state of the art in query optimization for these systems is much less developed than for relational systems, making careful physical database design even more imperative for object-oriented database systems.
MoodView
Authors: Arpinar İsmailcem Budak , Doğaç Asuman , Evrendilek Cem
Published: November 2005

OODBMSs need more than declarative query languages and programming languages as their interfaces since they are designed and implemented for complex applications requiring more advanced and easy to use visual interfaces. We have developed a complete programming environment for this purpose, called MoodView. MoodView translates all the user actions performed through its graphical interface to SQL statements and therefore it can be ported onto any object-oriented database systems using SQL.

MoodView provides the database programmer with tools and functionalities for every phase of object oriented database application development. Current version of MoodView allows a database user to design, browse, and modify database schema interactively and to display class inheritance hierarchy as a directed acyclic graph. MoodView can automatically generate graphical displays for complex and multimedia database objects which can be updated through the object browser. Furthermore, a database administration tool, a full screen text-editor, a SQL based query manager, and a graphical indexing tool for the spatial data, i.e., R Trees are also implemented.
Parallel query processing in shared disk database systems
Authors: Rahm Erhard
Published: November 2005

System developments and research on parallel query processing have concentrated either on “Shared Everything” or “Shared Nothing” architectures so far. While there are several commercial DBMS based on the “Shared Disk” alternative, this architecture has received very little attention with respect to parallel query processing. A comparison between Shared Disk and Shared Nothing reveals many potential benefits for Shared Disk with respect to parallel query processing. In particular, Shared Disk supports more flexible control over the communication overhead for intra-transaction parallelism, and a higher potential for dynamic load balancing and efficient processing of mixed OLTP/query workloads. We also sketch necessary extensions for transaction management (concurrency/coherency control, logging/recovery) to support intra-transaction parallelism in the Shared Disk environment.
Role-based security, object oriented databases and separation of duty
Authors: Nyanchama Matunda , Osborn Sylvia
Published: November 2005

In this paper we combined concepts of role-based protection and object oriented (O-O) databases to specify and enforce separation of duty as required for commercial database integrity [5, 23, 24]. Roles essentially
partition
database information into access contexts. Methods (from the O-O world) associated with a database object, also partition the object interface to provide
windowed
access to object information. By specifying that all database information is held in database objects and authorizing methods to roles, we achieve object
interface distribution
across roles. For processing in the commercial world we can design objects and distribute their associated methods to different roles. By authorizing different users to the different roles, we can enforce both the order of execution on the objects and separation of duty constraints on method execution.