bluuebunny/crossref_metadata_2025 huggingface dataset:
A survey on usage of SQL
Authors: Lu Hongjun , Chan Hock Chuan , Wei Kwok Kee
Published: November 2005

Relational database systems have been on market for more than a decade. SQL has been accepted as the standard query language of relational systems. To further understand the usage of relational systems and relational query language SQL, we conducted a survey recently that covers various aspects of the usage of SQL in industrial organizations. In this paper, we present those results that may interest DBMS researcher and developers, including the profiles of SQL users, the application areas where SQL is used, the usage of different features of SQL and difficulties encountered by SQL users.
An amateur's introduction to recursive query processing strategies
Authors: Bancilhon Francois , Ramakrishnan Raghu
Published: November 2005

This paper surveys and compares various strategies for processing logic queries in relational databases. The survey and comparison is limited to the case of Horn Clauses with evaluable predicates but without function symbols. The paper is organized in three parts. In the first part, we introduce the main concepts and definitions. In the second, we describe the various strategies. For each strategy, we give its main characteristics, its application range and a detailed description. We also give an example of a query evaluation. The third part of the paper compares the strategies on performance grounds. We first present a set of sample rules and queries which are used for the performance comparisons, and then we characterize the data. Finally, we give an analytical solution for each query/rule system. Cost curves are plotted for specific configurations of the data.
Performance evaluation of a temporal database management system
Authors: Ahn Ilsoo , Snodgrass Richard
Published: November 2005

A prototype of a temporal database management system was built by extending Ingres. It supports the temporal query language TQuel, a superset of Quel, handling four types of database static, rollback, historical and temporal. A benchmark set of queries was run to study the performance of the prototype on the four types of databases. We analyze the results of the benchmark, and identify major factors that have the greatest impact on the performance of the system. We also discuss several mechanisms to address the performance bottlenecks we encountered.
Neptune: a hypertext system for CAD applications
Authors: Delisle Norman , Schwartz Mayer
Published: November 2005

Even though many of the essential notions of hypertext were first contained in the description of a “memex,” written by Vannevar Bush in 1945 [Bus45], there are today only a few scattered implementations of hypertext, let alone any serious use of it in a CAD environment. In what follows, we describe what hypertext is all about. We describe a prototype hypertext system, named Neptune, that we have built. We show how it is useful, especially its broad applicability to CAD.
Prefetching in realtime database applications
Authors: Wedekind H. , Zoerntlein George
Published: November 2005

In this paper a method is proposed how to achieve response times of main memory database systems without keeping the whole database in main memory. The method was originally developed for real-time systems in manufacturing automation, but it is applicable in environments where canned transactions interact with databases rather than people performing free transactions. The main idea is to preanalyse canned transactions in order to extract knowledge about their local access behaviour. This knowledge is used by the runtime system of the database when the transaction is started. Concepts for modules doing the preanalysis and the runtime tasks are described in detail. Furthermore a database architecture is developed incorporating these new components.
Query processing in main memory database management systems
Authors: Lehman Tobin J. , Carey Michael J.
Published: November 2005

Most previous work in the area of main memory database systems has focused on the problem of developing query processing techniques that work well with a very large buffer pool. In this paper, we address query processing issues for
memory resident
relational databases, an environment with a very different set of costs and priorities. We present an architecture for a main memory DBMS, discussing the ways in which a memory resident database differs from a disk-based database. We then address the problem of processing relational queries in this architecture, considering alternative algorithms for selection, projection, and join operations and studying their performance. We show that a new index structure, the T Tree, works well for selection and join processing in memory resident databases. We also show that hashing methods work well for processing projections and joins, and that an old join method, sort-merge, still has a place in main memory.
Rule base management using meta knowledge
Authors: Harandi Mehdi T. , Schang Thierry , Cohen Seth
Published: November 2005

This paper describes the rule base management strategy of an expert system environment. The environment includes a set of integrated tools which facilitate acquisition, manipulation and maintenance of knowledge. The rule base management component of the system, called RBM, assists these tasks by organizing global semantic information within the rule base. RBM extracts this semantic information from the texts included in “rule structures” and builds a semantic network of the concepts found in the rule base. The rule base is then divided into rulesets which are clusters of rules that refer to the same atomic concept. Construction of this meta knowledge is achieved through a keyword matching mechanism. The paper includes a brief description of the RBM system, the dictionary it uses for building meta-level knowledge, and its keyword matching technique.
The multimedia object presentation manager of MINOS: a symmetric approach
Authors: Christodoulakis S. , Ho F. , Theodoridou M.
Published: November 2005

Large multimedia data bases become feasible due to recent advances in hardware technology. A very important component of multimedia data base management systems will be the presentation manager which will be responsible for effective multimedia presentation and browsing on the screen of workstations.

In this paper we present the functions provided for multimedia presentation and browsing in MINOS, a multimedia information system. The presentation and browsing capabilities provided make effective use of the capabilities of a modern workstation to increase the man-machine communication bandwidth. We regard voice as an important means of communication. Symmetric capabilities for text and voice browsing are provided.
The design of POSTGRES
Authors: Stonebraker Michael , Rowe Lawrence A.
Published: November 2005

This paper presents the preliminary design of a new database management system, called POSTGRES, that is the successor to the INGRES relational database system. The main design goals of the new system are to

provide better support for complex objects,

provide user extendibility for data types, operators and access methods,

provide facilities for active databases (i.e., alerters and triggers) and inferencing including forward- and backward-chaining,

simplify the DBMS code for crash recovery,

produce a design that can take advantage of optical disks, workstations composed of multiple tightly-coupled processors, and custom designed VLSI chips, and

make as few changes as possible (preferably none) to the relational model.

The paper describes the query language, programming language interface, system architecture, query processing strategy, and storage system for the new system.
Stepwise specification of dynamic database behaviour
Authors: Lipeck Udo W.
Published: November 2005

This paper presents a methodology for the stepwise specification of dynamic database behaviour. A conceptual schema is described in three levels: data, objects and transactions. To determine which sequences of database states are “admissible”, integrity constraints on objects are given in temporal logic. Transactions are specified by pre/postconditions to produce “executable” state sequences. In order to guarantee that executable state sequences already become admissible, integrity constraints are completely transformed into additional pre/postconditions. We introduce general rules for these transformations. Thus, schema specifications can be refined and simplified systematically.
A modeling study of the TPC-C benchmark
Authors: Leutenegger Scott T. , Dias Daniel
Published: November 2005

The TPC-C benchmark is a new benchmark approved by the TPC council intended for comparing database platforms running a medium complexity transaction processing workload. Some key aspects in which this new benchmark differs from the TPC-A benchmark are in having several transaction types, some of which are more complex than that in TPC-A, and in having data access skew. In this paper we present results from a modelling study of the TPC-C benchmark for both single node and distributed database management systems. We simulate the TPC-C workload to determine expected buffer miss rates assuming an LRU buffer management policy. These miss rates are then used as inputs to a throughput model. From these models we show the following: (i) We quantify the data access skew as specified in the benchmark and show what fraction of the accesses go to what fraction of the data. (ii) We quantify the resulting buffer hit ratios for each relation as a function of buffer size. (iii) We show that close to linear scale-up (about 3% from the ideal) can be achieved in a distributed system, assuming replication of a read-only table. (iv) We examine the effect of packing hot tuples into pages and show that significant price/performance benefit can be thus achieved. (v) Finally, by coupling the buffer simulations with the throughput model, we examine typical disk/memory configurations that maximize the overall price/performance.
Index support for rule activation
Authors: Brant David A. , Miranker Daniel P.
Published: November 2005

Integrated rule and database systems are quickly moving from the research laboratory into commercial systems. However, the current generation of prototypes are designed to work with small rule sets involving limited inferencing. The problem of supporting large complex rule programs within database management systems still presents significant challenges. The basis for many of these challenges is providing support for rule activation. Rule activation is defined as the process of determining which rules are satisfied and what data satisfies them. In this paper we present performance results for the DATEX database rule system and its novel indexing technique for supporting rule activation. Our approach assumes that both the rule program and the database must be optimized synergistically. However, as an experimental result we have determined that DATEX requires very few changes to a standard DBMS environment, and we argue that these changes are reasonable for the problems being solved. Based on the performance of DATEX we believe we have demonstrated a satisfactory solution to the rule activation problem for complex rule programs operating within a database system.
An instant and accurate size estimation method for joins and selections in a retrieval-intensive environment
Authors: Sun Wei , Ling Yibei , Rishe Naphtali , Deng Yi
Published: November 2005

This paper proposes a novel strategy for estimating the size of the resulting relation after an equi-join and selection using a regression model. An approximating series representing the underlying data distribution and dependency is derived from the actual data. The proposed method provides an instant and accurate size estimation by performing an evaluation of the series, with no run-time overheads in page faults and space, and with negligible CPU overhead. In contrast, the popular sampling methods incur run-time overheads in page faults (for sampling), CPU time and space. These overheads of sampling methods increase the response time of processing a query. The results of a comprehensive experimental study are also reported, which demonstrate that the estimation accuracy by the proposed method is comparable with that of the sampling methods which are believed to provide the most accurate estimation. The proposed method seems ideal for retrieval-intensive database and information systems. Since the overheads involved in deriving the approximating series are fairly moderate, we believe that this method is also an extremely competent method when moderate or periodical updates are present.
Using shared virtual memory for parallel join processing
Authors: Shatdal Ambuj , Naughton Jeffrey F.
Published: November 2005

In this paper, we show that shared virtual memory, in a shared-nothing multiprocessor, facilitates the design and implementation of parallel join processing algorithms that perform significantly better in the presence of skew than previously proposed parallel join processing algorithms. We propose two variants of an algorithm for parallel join processing using shared virtual memory, and perform a detailed simulation to investigate their performance. The algorithm is unique in that it employs both the shared virtual memory paradigm and the message-passing paradigm used by current shared-nothing parallel database systems. The implementation of the algorithm requires few modifications to existing shared-nothing parallel database systems.
Caching and database scaling in distributed shared-nothing information retrieval systems
Authors: Tomasic Anthony , Garcia-Molina Hector
Published: November 2005

A common class of existing information retrieval system provides access to abstracts. For example Stanford University, through its FOLIO system, provides access to the INSPECT database of abstracts of the literature on physics, computer science, electrical engineering, etc. In this paper this database is studied by using a trace-driven simulation. We focus on physical index design, inverted index caching, and database scaling in a distributed shared-nothing system. All three issues are shown to have a strong effect on response time and throughput. Database scaling is explored in two ways. One way assumes an “optimal” configuration for a single host and then linearly scales the database by duplicating the host architecture as needed. The second way determines the optimal number of hosts given a fixed database size.
An efficient and flexible method for archiving a data base
Authors: Mohan C. , Narang Inderpal
Published: November 2005

We describe an efficient method for supporting incremental and full archiving of data bases (e.g., individual files). Customers archive their data bases quite frequently to minimize the duration of data outage. Because of the growing sizes of data bases and the ever increasing need for high availability of data, the efficiency of the archive copy utility is very important. The method presented here minimizes interferences with concurrent transactions by not acquiring any locks on the data being copied. It significantly reduces disk I/Os by not keeping on data pages any extra tracking information in connection with archiving. These features make the archive copy operation be more efficient in terms of resource consumption compared to other methods. The method is also flexible in that it optionally supports direct copying of data from disks, bypassing the DBMS's buffer pool. This reduces buffer pool pollution and processing overheads, and allows the utility to take advantage of device geometries for efficiently retrieving data. We also describe extensions to the method to accommodate the multisystem shared disks transaction environment. The method tolerates gracefully system failures during the archive copy operation.
Real-time transaction scheduling
Authors: Hong D. , Johnson T. , Chakravarthy S.
Published: November 2005

Real-time databases are an important component of embedded real-time systems. In a real-time database context, transactions must not only maintain the consistency constraints of the database but must also satisfy the timing constraints specified for each transaction. Although several approaches have been proposed to integrate real-time scheduling and database concurrency control methods, none of them take into account the dynamic cost of scheduling a transaction. In this paper, we propose a new cost conscious real-time transaction scheduling algorithm which considers dynamic costs associated with a transaction. Our dynamic priority assignment algorithm adapts to changes in the system load without causing excessive numbers of transaction restarts. Our simulations show its superiority over EDF-HP algorithm.
Loading data into description reasoners
Authors: Borgida Alex , Brachman Ronald J.
Published: November 2005

Knowledge-base management systems (KBMS) based on description logics are being used in a variety of situations where access is needed to large amounts of data stored in existing relational databases. We present the architecture and algorithms of a system that converts most of the inferences made by the KBMS into a collection of SQL queries, thereby relying on the optimization facilities of existing DBMS to gain efficiency, while maintaining an object-centered view of the world with a substantive semantics and significantly different reasoning facilities than those provided by Relational DBMS and their deductive extensions. We address a number of optimization issues that arise in the translation process due to the fact that SQL queries with different syntax (but identical semantics) are not treated uniformly by current database management systems.
Temporal modules
Authors: Wang X. Sean , Jajodia Sushil , Subrahmanian V. S.
Published: November 2005

In a federated database environment, different constituents of the federation may use different temporal models or physical representations for temporal information. This paper introduces a new concept, called a
temporal module
, to resolve these differences, or mismatches, among the constituents. Intuitively, a temporal module hides the implementation details of a temporal relation by exposing its information only through two
windowing functions
: The first function associates each time point with a set of tuples and the second function links each tuple to a set of time points. A calculus-style language is given to form queries on temporal modules.

Temporal modules are then extended to resolve another type of mismatch among the constituents of a federation, namely, the mismatch involving different time units (e.g.,
month
,
week
and
day
) used to record temporal information. Our solution relies on “information conversions” provided by each constituent. Specifically, each temporal module is extended to provide several “windows” to its information, each in terms of a different time unit. The first step to process a query addressed to the federation is to select suitable windows to the underlying temporal modules. In order to facilitate such a process, time units are formally defined and studied. A federated temporal database model and its query language are proposed. The query language is an extension of the above calculus-style language.
Practical prefetching via data compression
Authors: Curewitz Kenneth M. , Krishnan P. , Vitter Jeffrey Scott
Published: November 2005

An important issue that affects response time performance in current OODB and hypertext systems is the I/O involved in moving objects from slow memory to cache. A promising way to tackle this problem is to use
prefetching
, in which we predict the user's next page requests and get those pages into cache in the background. Current databases perform limited prefetching using techniques derived from older virtual memory systems. A novel idea of using data compression techniques for prefetching was recently advocated in [KrV, ViK], in which prefetchers based on the Lempel-Ziv data compressor (the UNIX
compress
command) were shown theoretically to be optimal in the limit. In this paper we analyze the
practical
aspects of using data compression techniques for prefetching. We adapt three well-known data compressors to get three simple, deterministic, and universal prefetchers. We simulate our prefetchers on sequences of page accesses derived from the OO1 and OO7 benchmarks and from CAD applications, and demonstrate significant reductions in fault-rate. We examine the important issues of cache replacement, size of the data structure used by the prefetcher, and problems arising from bursts of “fast” page requests (that leave virtually no time between adjacent requests for prefetching and book keeping). We conclude that prediction for prefetching based on data compression techniques holds great promise.
The LRU-K page replacement algorithm for database disk buffering
Authors: O'Neil Elizabeth J. , O'Neil Patrick E. , Weikum Gerhard
Published: November 2005

This paper introduces a new approach to database disk buffering, called the LRU-K method. The basic idea of LRU-K is to keep track of the times of the last
K
references to popular database pages, using this information to statistically estimate the interarrival times of references on a page by page basis. Although the LRU-K approach performs optimal statistical inference under relatively standard assumptions, it is fairly simple and incurs little bookkeeping overhead. As we demonstrate with simulation experiments, the LRU-K algorithm surpasses conventional buffering algorithms in discriminating between frequently and infrequently referenced pages. In fact, LRU-K can approach the behavior of buffering algorithms in which page sets with known access frequencies are manually assigned to different buffer pools of specifically tuned sizes. Unlike such customized buffering algorithms however, the LRU-K method is self-tuning, and does not rely on external hints about workload characteristics. Furthermore, the LRU-K algorithm adapts in real time to changing patterns of access.
Doubly distorted mirrors
Authors: Orji Cyril U. , Solworth Jon A.
Published: November 2005

Traditional mirrored disk systems provide high reliability by multiplexing disks. Performance is improved with parallel reads and shorter read seeks. However, writes must be performed by both disks, limiting performance.

Doubly distorted mirrors
increase the number of physical writes per logical write from 2 to 3, but performs logical writes more efficiently. This reduces the cost of a random logical write to 1/3 of the cost of a read. Moreover, much of the write cost can be absorbed in the rotational latency of the reads, performing under certain conditions all the writes for free. Doubly distorted mirrors achieves a 135% performance improvement over traditional mirrors in the TP1 benchmark. Although these techniques require a disk cache for writes, the cache need not be safe nor is recovery time impacted very much.
On the power of algebras with recursion
Authors: Beeri Catriel , Milo Tova
Published: November 2005

We consider the relationship between the deductive and the functional/algebraic query language paradigms. Previous works considered this subject for a non-recursive algebra, or an algebra with a fixed point operation, and the corresponding class of deductive queries is that defined by stratified programs. We consider here algebraic languages extended by general recursive definitions. We also consider languages that allow non-restricted use of negation. It turns out that recursion and negation in the algebraic paradigm need to be studied together. The semantics used for the comparison is the valid semantics, although other well-known declarative semantics can also be used to derive similar results. We show that the class of queries expressed by general deduction with negation can be captured using algebra with recursive definitions.
Open DECdtm
Authors: Klein Johannes , Upton Francis
Published: November 2005

Open DECdtm offers portable transaction management services layered on OSF DCE which support the application (TX), resource manager (XA), and transactional DCE RPC (TxRPC) interfaces specified by X/Open. Open DECdtm also provides interoperability with OSI Transaction Processing (OSI TP) and OpenVMS systems using the DECdtm OpenVMS protocol. Protocols executed by Open DECdtm are specified by constraints. This simplifies the development of transactional gateways between different data transfer protocols and transaction models.
DDB
Authors: Singhal Anoop , Arlein Robert M. , Lo Chi-Yuan
Published: November 2005

In this paper we present an object oriented data model for VLSI/CAD data. A design data manager (DDB) based on such a model has been implemented under the UNIX/C++ environment. It has been used by a set of diverse VLSI/CAD applications of our organization. Benchmarks have shown it to perform better as compared to commercial object oriented database systems. In conjunction with the ease of data access, the data manger served to improve software productivity and a modular program architecture for our CAD system.
NAUDA
Authors: Küpper D. , Storbel M. , Rösner D.
Published: November 2005

The NAUDA
1
System is a cooperative natural (German) language database interface for relational databases. The project is carried out at FAW
2
- funded by the state of Baden-Württemberg and IBM Germany. This paper describes the extension of a natural language interface to relational databases with respect to its cooperative behavior. We argue that cooperative support of users is especially important for a complex domain such as environmental protection. In order to enrich traditional database reports our system provides dialog-oriented features such as over-answering (providing more information than explicitly requested) and handling of presupposition failure, as well as presentation-oriented features such as natural language responses and geographical maps. Additional information by the system includes (meta-) information
about
the domain.
A hypertext query language for images
Authors: Yang Li
Published: November 2005

HYPERQUERY is a hypertext query language for object-oriented pictorial database systems. First, we discuss object calculus based on term rewriting. Then, example queries are used to illustrate language facilities. This query language has been designed with a flavor similar to QBE as the highly nonprocedural and conversational language for object-oriented pictorial database management system OISDBS.
Comprehension syntax
Authors: Buneman Peter , Libkin Leonid , Suciu Dan , Tannen Val , Wong Limsoon
Published: November 2005

The syntax of comprehensions is very close to the syntax of a number of practical database query languages and is, we believe, a better starting point than first-order logic for the development of database languages. We give an informal account of a language based on comprehension syntax that deals uniformly with a variety of collection types; it also includes pattern matching, variant types and function definition. We show, again informally, how comprehension syntax is a natural fragment of structural recursion, a much more powerful programming paradigm for collection types. We also show that a very small "abstract syntax language" can serve as a basis for the implementation and optimization of comprehension syntax.
Influencing database language standards
Authors: Gallagher Leonard
Published: November 2005

In this first article of the regular column on data base standardization activities, I give an overview of topic areas under active development in the formal national and international standardization bodies. I solicit contributions on these active topics so that standardizers and researchers can cooperate in the near term, before irreversible decisions are made, to produce the most useful and highest quality database standards.
The ripple effect
Authors: Harris Geoff , Forster John , Rankin Richard
Published: November 2005

A brief overview of research to date on word games in general, and crossword puzzle solution algorithms in particular, is presented. An algorithm which is easy to implement and is highly suited for PC work-stations is presented. An implementation of this algorithm is demonstrated to produce dramatic reductions of the size of the search trees traversed by specific crossword puzzle implementations.
A family of genetic algorithm packages on a workstation for solving combinatorial optimization problems
Authors: Wainwright Roger L.
Published: November 2005

LibGA, HYPERGEN and GATutor represent a trio of in-house developed genetic algorithm software packages for conducting research in combinatorial optimization problems. For a variety of reasons, these packages were developed using the C programming language on a Unix platform, specifically a Sun workstation. We used these packages successfully in developing sequential and parallel genetic algorithms for solving numerous combinatorial optimization problems. Several of these combinatorial optimization research projects and their results are described.
Performance evaluation of a new distributed deadlock detection algorithm
Authors: Yeung Chim-fu , Hung Sheung-lun , Lam Kam-yiu
Published: November 2005

In this paper, a new probe-based distributed deadlock detection algorithm is proposed. It is an enhanced version of the algorithm originally proposed by Chandy's et al. [5,6]. The new algorithm has proven to be error free and suffers very little performance degradation from the additional deadlock detection overhead. The algorithm has been compared with the modified probe-based and timeout methods. It is found that under high data contention, it has the best performance. Results also indicate that the rate of probe initiation is significantly reduced in the new algorithm.
Research issues in active database systems
Authors: Widom Jennifer
Published: November 2005

The discussions during the panel stayed largely but not entirely focused on the question of active database research issues from the application perspective. There were nine panelists. Each panelist was asked to prepare brief answers to a set of questions. The sets of answers were discussed by all participants, and finally a number of more general issues were discussed.

The questions asked of the panelists were:

Name an application that will certainly be supported by active database systems in the not-too-distant future.

Name an application that will certainly not be supported by active database systems in the near future.

Name an area of active database systems in which you are not working but that is crucial to meet the needs of applications.

Name an area of active database systems that is not on the critical path to supporting applications.

Name an area of active database systems that should have been discussed in the course of the workshop but was not.
Medical information systems
Authors: Ramirez Jorge C. G. , Smith Lon A. , Peterson Lynn L.
Published: November 2005

This paper examines the characteristics and challenges presented by medical databases and medical information systems. It begins with a survey of medical databases/information systems. This is followed by a list of challenges for database management systems generated by the needs of these systems. It concludes with a look at some systems which address these challenges. In the context of this background information, the database community is asked to consider whether the results of database research are reaching those who are making day-to-day decisions regarding design and implementation of medical information systems.
Jumping on the NII bandwagon
Authors: Qian Xiaolei
Published: November 2005

Many requests for proposals have been issued since the last issue of this column appeared six months ago. We first briefly touch upon some recent developments along the policy/legislation front concerning NSF, ARPA, and HPCC. We then recap the recent requests for proposals from ARPA, NSF, Air Force, NASA, and Army.
Are the terms “version” and “variant” orthogonal to one another?
Authors: Wedekind Hartmut
Published: November 2005

Versions and variants are an important issue in industrial DB-applications like CAD/CAM. It is argued that a clean distinction between both terms is of great importance.
Metadata in video databases
Authors: Jain Ramesh , Hampapur Arun
Published: November 2005

Video is composed of audio-visual information. Providing content based access to video data is essential for the sucessful integration of video into computers. Organizing video for content based access requires the use of video metadata. This paper explores the nature video metadata. A data model for video databases is presented based on a study of the applications of video, the nature of video retrieval requests, and the features of video. The data model is used in the architectural framework of a video database. The current state of technology in video databases is summarized and research issues are highlighted.
Loading databases using dataflow parallelism
Authors: Barclay Tom , Barnes Robert , Gray Jim , Sundaresan Prakash
Published: November 2005

This paper describes a parallel database load prototype for Digital's Rdb database product. The prototype takes a dataflow approach to database parallelism. It includes an
explorer
that discovers and records the cluster configuration in a database, a
client
CUI interface that gathers the load job description from the user and from the Rdb catalogs, and an
optimizer
that picks the best parallel execution plan and records it in a
web
data structure. The web describes the data
operators
, the
dataflow rivers
among them, the binding of operators to processes, processes to processors, and files to discs and tapes. This paper describes the optimizer's cost-based hierarchical optimization strategy in some detail. The prototype executes the web's plan by spawning a
web manager
process at each node of the cluster. The managers create the local
executor
processes, and orchestrate startup, phasing, checkpoint, and shutdown. The execution processes perform one or more operators. Data flows among the operators are via
memory-to-memory streams
within a node, and via web-manager multiplexed tcp/ip streams among nodes. The design of the
transaction
and
checkpoint/restart
mechanisms are also described. Preliminary measurements indicate that this design will give excellent scaleups.
ARIES/CSA
Authors: Mohan C. , Narang Inderpal
Published: November 2005

This paper presents an algorithm, called ARIES/CSA (
Algorithm for Recovery and Isolation Exploiting Semantics for Client-Server Architectures
), for performing recovery correctly in client-server (CS) architectures. In CS, the server manages the disk version of the database. The clients, after obtaining database pages from the server, cache them in their buffer pools. Clients perform their updates on the cached pages and produce log records. The log records are buffered locally in virtual storage and later sent to the single log at the server. ARIES/CSA supports a write-ahead logging (WAL), fine-granularity (e.g., record) locking, partial rollbacks and flexible buffer management policies like
steal
and
no-force
. It does not require that the clocks on the clients and the server be synchronized. Checkpointing by the server and the clients allows for flexible and easier recovery.
Ensuring relaxed atomicity for flexible transactions in multidatabase systems
Authors: Zhang Aidong , Nodine Marian , Bhargava Bharat , Bukhres Omran
Published: November 2005

Global transaction management requires cooperation from local sites to ensure the consistent and reliable execution of global transactions in a distributed database system. In a heterogeneous distributed database (or multidatabase) environment, various local sites make conflicting assertions of autonomy over the execution of global transactions. A flexible transaction model for the specification of global transactions makes it possible to deal robustly with these conflicting requirements. This paper presents an approach that preserves the
semi-atomicity
(a weaker form of atomicity) of flexible transactions, allowing local sites to autonomously maintain serializability and recoverability. We offer a fundamental characterization of the flexible transaction model and precisely define the semi-atomicity. We investigate the commit dependencies among the subtransactions of a flexible transaction. These dependencies are used to control the commitment order of the subtransactions. We next identify those restrictions that must be placed upon a flexible transaction to ensure the maintenance of its semi-atomicity. As atomicity is a restrictive criterion, semi-atomicity enhances the class of executable global transactions.
Implementation of magic-sets in a relational database system
Authors: Mumick Inderpal Singh , Pirahesh Hamid
Published: November 2005

We describe the implementation of the magic-sets transformation in the Starburst extensible relational database system. To our knowledge this is the first implementation of the magic-sets transformation in a relational database system. The Starburst implementation has many novel features that make our implementation especially interesting to database practitioners (in addition to database researchers). (1) We use a cost-based heuristic for
determining join orders
(sips) before applying magic. (2) We push all equality and
non-equality
predicates using magic, replacing traditional predicate pushdown optimizations. (3) We apply magic to
full SQL
with duplicates, aggregation, null values, and subqueries. (4) We
integrate
magic with other relational optimization techniques. (5) The implementation is
extensible
.

Our implementation demonstrates the feasibility of the magic-sets transformation for commercial relational systems, and provides a mechanism to implement magic as an integral part of a new database system, or as an add-on to an existing database system.
The effectiveness of GIOSS for the text database discovery problem
Authors: Gravano Luis , García-Molina Héctor , Tomasic Anthony
Published: November 2005

The popularity of on-line document databases has led to a new problem: finding which text databases (out of many candidate choices) are the most relevant to a user. Identifying the relevant databases for a given query is the
text database discovery problem
. The first part of this paper presents a practical solution based on estimating the result size of a query and a database. The method is termed
GlOSS—Glossary of Servers Server
. The second part of this paper evaluates the effectiveness of
GlOSS
based on a trace of real user queries. In addition, we analyze the storage cost of our approach.
AlphaSort
Authors: Nyberg Chris , Barclay Tom , Cvetanovic Zarka , Gray Jim , Lomet Dave
Published: November 2005

A new sort algorithm, called AlphaSort, demonstrates that commodity processors and disks can handle commercial batch workloads. Using Alpha AXP processors, commodity memory, and arrays of SCSI disks, AlphaSort runs the industry-standard sort benchmark in seven seconds. This beats the best published record on a 32-cpu 32-disk Hypercube by 8:1. On another benchmark, AlphaSort sorted more than a gigabyte in a minute.

AlphaSort is a cache-sensitive memory-intensive sort algorithm. It uses file striping to get high disk bandwidth. It uses QuickSort to generate runs and uses replacement-selection to merge the runs. It uses shared memory multiprocessors to break the sort into subsort chores.

Because startup times are becoming a significant part of the total time, we propose two new benchmarks: (1) Minutesort: how much can you sort in a minute, and (2) DollarSort: how much can you sort for a dollar.
Distributed file organization with scalable cost/performance
Authors: Vingralek Radek , Breitbart Yuri , Weikum Gerhard
Published: November 2005

This paper presents a distributed file organization for record-structured, disk-resident files with key-based exact-match access. The file is organized into buckets that are spread across multiple servers, where a server may hold multiple buckets. Client requests are serviced by mapping keys onto buckets and looking up the corresponding server in an address table. Dynamic growth in terms of file size and access load is supported by bucket splits and migration onto other existing or newly acquired servers.

The significant and challenging problem addressed here is how to achieve scalability so that both the file size and the client throughput can be scaled up by linearly increasing the number of servers and dynamically redistributing data. Unlike previous work with similar objectives, our data redistribution considers explicitly the cost/performance ratio of the system by aiming to minimize the number of servers that are acquired to provide the required performance. A new server is acquired only if the overall server utilization in the system does not drop below a specified threshold. Preliminary simulation results show that the goal of scalability with controlled cost/performance is indeed achieved to a large extent.
Incremental updates of inverted lists for text document retrieval
Authors: Tomasic Anthony , García-Molina Héctor , Shoens Kurt
Published: November 2005

With the proliferation of the world's “information highways” a renewed interest in efficient document indexing techniques has come about. In this paper, the problem of incremental updates of inverted lists is addressed using a new dual-structure index. The index dynamically separates long and short inverted lists and optimizes retrieval, update, and storage of each type of list. To study the behavior of the index, a space of engineering trade-offs which range from optimizing update time to optimizing query performance is described. We quantitatively explore this space by using actual data and hardware in combination with a simulation of an information retrieval system. We then describe the best algorithm for a variety of criteria.
Optimizing queries on files
Authors: Consens Mariano P. , Milo Tova
Published: November 2005

We present a framework which allows the user to access and manipulate data uniformly, regardless of whether it resides in a database or in the file system (or in both). A key issue is the performance of the system. We show that text indexing, combined with newly developed optimization techniques, can be used to provide an efficient high level interface to information stored in files. Furthermore, using these techniques, some queries can be evaluated significantly faster than in standard database implementations. We also study the tradeoff between efficiency and the amount of indexing.
Fine-grained sharing in a page server OODBMS
Authors: Carey Michael J. , Franklin Michael J. , Zaharioudakis Markos
Published: November 2005

For reasons of simplicity and communication efficiency, a number of existing object-oriented database management systems are based on page server architectures; data pages are their minimum unit of transfer and client caching. Despite their efficiency, page servers are often criticized as being too restrictive when it comes to concurrency, as existing systems use pages as the minimum locking unit as well. In this paper we show how to support object-level locking in a page server context. Several approaches are described, including an adaptive granularity approach that uses page-level locking for most pages but switches to object-level locking when finer-grained sharing is demanded. We study the performance of these approaches, comparing them to both a pure page server and a pure object server. For the range of workloads that we have examined, our results indicate that a page server is clearly preferable to an object server. Moreover, the adaptive page server is shown to provide very good performance, generally outperforming the pure page server, the pure object server, and the other alternatives as well.
Application of OODB and SGML techniques in text database
Authors: Zhang Jian
Published: November 2005

An electronic dictionary system (EDS) is developed with object-oriented database techniques based on ObjectStore. The EDS is composed of two parts: the Database Building Program (DBP), and the Database Querying Program (DQP). DBP reads in a dictionary encoded in SGML tags, and builds a database composed of a collection of trees which holds dictionary entries, and several lists which contain items of various lexical categories. With text exchangeability introduced by the SGML, DBP is able to accommodate dictionaries of different languages with different structures, after easy modification of a configuration file. The tree model, the Category Lists, and an optimization procedure enables DQP to quickly accomplish complicated queries, including context requirements, via simple SQL-like syntax and straightforward search methods. Results show that compared with relational database, DQP enjoys much higher speed and flexibility. With EDS this paper demonstrates how to apply OODBMS's to systems that handle text information with strong yet varied intrinsic hierarchies.
HODFA
Authors: Karlapalem Kamalakar , Li Qing , Shum Chung-Dak
Published: November 2005

One of the main difficulties in supporting global applications over a number of localized databases and migrating legacy information systems to modern computing environment is to cope with the heterogeneities of these systems. In this paper, we present a
novel flexible architecture
(called HODFA) to dynamically connect such localized heterogeneous databases in forming a
homogenized federated database system
and to support the process of transforming a collection of heterogeneous information systems onto a homogeneous environment. We further develop an incremental methodology of homogenization in the context of our HODFA framework, which can facilitate different degrees of homogenization in a stepwise manner, so that existing applications will not be affected during the process of homogenization.
Implementing deletion in B+-trees
Authors: Jannink Jan
Published: November 2005

This paper describes algorithms for key deletion in B
+
-trees. There are published algorithms and pseudocode for searching and inserting keys, but deletion, due to its greater complexity and perceived lesser importance, is glossed over completely or left as an exercise to the reader. To remedy this situation, we provide a well documented flowchart, algorithm, and pseudo-code for deletion, their relation to search and insertion algorithms, and a reference to a freely available, complete B
+
-tree library written in the C programming language.