bluuebunny/crossref_metadata_2025 huggingface dataset:
Ethical norms for technical communication
Authors: Walzer Arthur E.
Published: November 2005

In his "Ethics in Technical Communication: A Rhetorical Perspective," Gregory Clark argues convincingly that academicians and practitioners proceed from diametrically opposed assumptions in discussing ethics in the context of technical communication. Furthermore, Clark offers his essay as an example of an approach that might, were it widely imitated, promote the disciplined, progressive discussion on this topic that to this point has failed to evolve. But while Clark's intentions are admirable and his basic approach sound, the conclusions he reaches -- that an ethics for technical communication must be founded on a principle of cooperation -- cannot be derived from the approach he models. Clark's argument that the rhetorical tradition sanctions an ethics based on the principle of cooperation rests on misreadings of both Plato and Aristotle; and the Challenger case, which he sees as illustrating the need for a cooperative approach to communication, in fact proves just the opposite. A more realistic ethics for technical communication would begin in the acknowledgement that rhetoric more often spurs contention than cooperation and then take up the task of investigating the conditions that promote creative, rather than destructive, debate.
Data replication for mobile computers
Authors: Huang Yixiu , Sistla Prasad , Wolfson Ouri
Published: November 2005

Users of mobile computers will soon have online access to a large number of databases via wireless networks. Because of limited bandwidth, wireless communication is more expensive than wire communication. In this paper we present and analyze various static and dynamic data allocation methods. The objective is to optimize the communication cost between a mobile computer and the stationary computer that stores the online database. Analysis is performed in two cost models. One is connection (or time) based, as in cellular telephones, where the user is charged per minute of connection. The other is message based, as in packet radio networks, where the user is charged per message. Our analysis addresses both, the average case and the worst case for determining the best allocation method.
ASSET
Authors: Biliris A. , Dar S. , Gehani N. , Jagadish H. V. , Ramamritham K.
Published: November 2005

Extended transaction models in databases were motivated by the needs of complex applications such as CAD and software engineering. Transactions in such applications have diverse needs, for example, they may be long lived and they may need to cooperate. We describe ASSET, a system for supporting extended transactions. ASSET consists of a set of transaction primitives that allow users to define custom transaction semantics to match the needs of specific applications. We show how the transaction primitives can be used to specify a variety of transaction models, including nested transactions, split transactions, and sagas. Application-specific transaction models with relaxed correctness criteria, and computations involving workflows, can also be specified using the primitives. We describe the implementation of the ASSET primitives in the context of the Ode database.
Data modeling of time-based media
Authors: Gibbs Simon , Breiteneder Christian , Tsichritzis Dennis
Published: November 2005

Many aspects of time-based media—complex data encoding, compression, “quality factors,” timing—appear problematic from a data modeling standpoint. This paper proposes
timed streams
as the basic abstraction for modeling time-based media. Several media-independent structuring mechanisms are introduced and a data model is presented which, rather than leaving the interpretation of multimedia data to applications, addresses the complex organization and relationships present in multimedia.
Combinatorial pattern discovery for scientific data
Authors: Wang Jason Tsong-Li , Chirn Gung-Wei , Marr Thomas G. , Shapiro Bruce , Shasha Dennis , Zhang Kaizhong
Published: November 2005

Suppose you are given a set of natural entities (e.g., proteins, organisms, weather patterns, etc.) that possess some important common externally observable properties. You also have a structural description of the entities (e.g., sequence, topological, or geometrical data) and a distance metric. Combinatorial pattern discovery is the activity of finding patterns in the structural data that might explain these common properties based on the metric.

This paper presents an example of combinatorial pattern discovery: the discovery of patterns in protein databases. The structural representation we consider are strings and the distance metric is string edit distance permitting variable length don't cares. Our techniques incorporate string matching algorithms and novel heuristics for discovery and optimization, most of which generalize to other combinatorial structures. Experimental results of applying the techniques to both generated data and functionally related protein families obtained from the Cold Spring Harbor Laboratory show the effectiveness of the proposed techniques. When we apply the discovered patterns to perform protein classification, they give information that is complementary to the best protein classifier available today.
On parallel execution of multiple pipelined hash joins
Authors: Hsiao Hui-I , Chen Ming-Syan , Yu Philip S.
Published: November 2005

In this paper we study parallel execution of multiple pipelined hash joins. Specifically, we deal with two issues, processor allocation and the use of hash filters, to improve parallel execution of hash joins. We first present a scheme to transform a bushy execution tree to an allocation tree, where each node denotes a pipeline. Then, processors are allocated to the nodes in the allocation tree based on the concept of synchronous execution time such that inner relations (i.e., hash tables) in a pipeline can be made available approximately the same time. In addition, the approach of hash filtering is investigated to further improve the overall performance. Performance studies are conducted via simulation to demonstrate the importance of processor allocation and to evaluate various schemes using hash filters. Simulation results indicate that processor allocation based on the allocation tree significantly outperforms that based on the original bushy tree, and that the effect of hash filtering becomes prominent as the number of relations in a query increases.
Distributing a search tree among a growing number of processors
Authors: Kröll Brigitte , Widmayer Peter
Published: November 2005

Databases are growing steadily, and distributed computer systems are more and more easily available. This provides an opportunity to satisfy the increasingly tighter efficiency requirements by means of distributed data structures. The design and analysis of these structures under efficiency aspects, however, has not yet been studied sufficiently. To our knowledge, a single scalable, distributed data structure has been proposed so far. It is a distributed variant of linear hashing with uncontrolled splits, and, as a consequence, performs efficiently for data distributions that are close to uniform, but not necessarily for others. In addition, it does not support queries that refer to the linear order of keys, such as nearest neighbor or range queries. We propose a distributed search tree that avoids these problems, since it inherits desirable properties from non-distributed trees. Our experiments show that our structure does indeed combine a guarantee for good storage space utilization with high query efficiency. Nevertheless, we feel that further research in the area of scalable, distributed data structures is dearly needed; it should eventually lead to a body of knowledge that is comparable with the non-distributed, classical data structures field.
From structured documents to novel query facilities
Authors: Christophides V. , Abiteboul S. , Cluet S. , Scholl M.
Published: November 2005

Structured documents (e.g., SGML) can benefit a lot from database support and more specifically from object-oriented database (OODB) management systems. This paper describes a natural mapping from SGML documents into OODB's and a formal extension of two OODB query languages (one SQL-like and the other calculus) in order to deal with SGML document retrieval.

Although motivated by structured documents, the extensions of query languages that we present are general and useful for a variety of other OODB applications. A key element is the introduction of paths as first class citizens. The new features allow to query data (and to some extent schema) without exact knowledge of the schema in a simple and homogeneous fashion.
Shoring up persistent applications
Authors: Carey Michael J. , DeWitt David J. , Franklin Michael J. , Hall Nancy E. , McAuliffe Mark L. , Naughton Jeffrey F. , Schuh Daniel T. , Solomon Marvin H. , Tan C. K. , Tsatalos Odysseas G. , White Seth J. , Zwilling Michael J.
Published: November 2005

SHORE (Scalable Heterogeneous Object REpository) is a persistent object system under development at the University of Wisconsin. SHORE represents a merger of object-oriented database and file system technologies. In this paper we give the goals and motivation for SHORE, and describe how SHORE provides features of both technologies. We also describe some novel aspects of the SHORE architecture, including a symmetric peer-to-peer server architecture, server customization through an extensible
value-added server
facility, and support for scalability on multiprocessor systems. An initial version of SHORE is already operational, and we expect a release of Version 1 in mid-1994.
XSB as an efficient deductive database engine
Authors: Sagonas Konstantinos , Swift Terrance , Warren David S.
Published: November 2005

This paper describes the XSB system, and its use as an in-memory deductive database engine. XSB began from a Prolog foundation, and traditional Prolog systems are known to have serious deficiencies when used as database systems. Accordingly, XSB has a fundamental bottom-up extension, introduced through tabling (or memoing)[4], which makes it appropriate as an underlying query engine for deductive database systems. Because it eliminates redundant computation, the tabling extension makes XSB able to compute all modularly stratified datalog programs finitely and with polynomial data complexity. For non-stratified programs, a meta-interpreter with the same properties is provided. In addition XSB significantly extends and improves the indexing capabilities over those of standard Prolog. Finally, its syntactic basis in HiLog [2], lends it flexibility for data modelling.

The implementation of XSB derives from the WAM [25], the most common Prolog engine. XSB inherits the WAM's efficiency and can take advantage of extensive compiler technology developed for Prolog. As a result, performance comparisons indicate that XSB is significantly faster than other deductive database systems for a wide range of queries and stratified rule sets. XSB is under continuous development, and version 1.3 is available through anonymous ftp.
Enterprise information architectures—they're finally changing
Authors: Melling Wesley P.
Published: November 2005

Substantive changes in the business environment—and aggressive initiatives in business process reengineering—are driving corresponding changes in the information technology architectures of large enterprises. Those changes are enabled by the convergence of a long list of maturing new technologies. As one of its many implications, the new IT architecture demands revised assumptions about the design and deployment of databases. This paper reviews the components of the architectural shift now in process, and offers strategic planning assumptions for database professionals.
Diagrams and design tools in context
Authors: Allmendinger Leif
Published: November 2005

This commentary examines a number issues raised in Professor Brasseur's study. It considers the cognitive and cultural design issues of simple, presentation diagrams. Designer concerns and major design approaches are reviewed, with the conclusion that understandability, while important, is not the sole design consideration. This commentary examines how technology affordances, constraints, and in-the-world knowledge might account for Professor Brasseur's results. It discusses ways to improve the human-computer interface of diagramming software. Quality is examined from user, implementation, and cultural standpoints, and current poor graphical quality is explained from a market perspective. A final section reviews recent research and technological developments with the goal of predicting future trends in diagrams design.
Knowledge acquisition and representation techniques in scholarly communication
Authors: Gaines Brian R. , Shaw Mildred L. G.
Published: November 2005

Paper journals, conferences and workshops have been the major media for scholarly discourse for 300 years. However, in the 1990s access to low-cost personal computing and Internet communications is leading to radical changes in the operation of scholarly communities. Electronic publication and conferencing is becoming common in all disciplines using commonly available Internet facilities such as ftp archives, list servers, gopher and world-wide web. Some scholarly communities that had not previously achieved a critical mass have done so through the net, others have launched major collaborative projects managed through the net, and others are questioning the value of conventional conferences that are limited by being localized in space and time compared with the flexibility of continuous international electronic conferencing through the web. However, the majority of current electronic scholarly discourse emulates paper-based media in relying primarily on text and diagrams for knowledge communication. It is beginning to take advantage of some of the multimedia capabilities of electronic publishing for color diagrams, pictures, movies and sound. Hypertext and hypermedia capabilities are being used to develop webs of linked material. Concept maps and formal knowledge structures are being used to provide a framework for knowledge expression, interchange and collaborative development. This article focuses on the extension of current documentation technologies to provide knowledge-level support for scholarly communities.
Structural analysis of science prose
Authors: Mayer Richard E.
Published: November 2005

This chapter explores techniques for analyzing the structure and improving the understandability of science prose. Structure refers to a distinction between idea units that explain the mechanisms underlying a rule (explanative information) and idea units that do not (non-explanative information). Understandability is measured by tests of creative problem solving based on information in the passage. Science prose refers to a passage that contains a functional rule among two or more variables and an explanation of the underlying mechanisms. Three techniques are described for distinguishing explanative and non-explanative information: structural method, logical method, and empirical method. Then, research is provided concerning techniques that increase the subject's recall of explanative information, and thus the subject's problem-solving performance. These techniques include manipulating the reading strategy, such as by encouraging reflective or elaborative processing, and manipulating the text design, such as by organizing the text around key ideas or including a concrete model. Finally, some recommendations are suggested for improving science textbooks, with hopes that such recommendations will stimulate further research.
A process perspective on Mayer
Authors: Smith Catherine F.
Published: November 2005

Mayer's idea of reading is not robust enough to account for complex processes of learning from text. Nevertheless, his rough guesses about comprehensible text design are useful for scientific and technical communicators.
Books without pages
Authors: Negroponte Nicholas
Published: November 2005

Computer Graphics has been a vector oriented high technology for interaction and its images have been those of a silent movie. Current trends toward raster scan in general are bringing together the previously disjoint communities of image processing, broadcast television and computer graphics. Present implementations in video format are making computer graphics ubiquitous. Jointly, these events are leading to broader definitions of man-machine interaction and more generalized applications of computer resources. The user community is growing to include people like: presidents of companies, housewives, six year old children.In this light, this paper is about not throwing away the message with the medium while offering new technological opportunities for communication. In many regards the old fashioned book remains the best random access information resource we have, but new opportunities include: personalization, sound synchronization, spatial data access.
On-line reorganization of sparsely-populated B+-trees
Authors: Zou Chendong , Salzberg Betty
Published: November 2005

In this paper, we present an efficient method to do online reorganization of sparsely-populated B
+
-trees. It reorganizes the leaves first, compacting in short operations groups of leaves with the same parent. After compacting, optionally, the new leaves may swap locations or be moved into empty pages so that they are in key order on the disk. After the leaves are reorganized, the method shrinks the tree by making a copy of the upper part of the tree while leaving the leaves in place. A new concurrency method is introduced so that only a minimum number of pages are locked during reorganization. During leaf reorganization,
Forward Recovery
is used to save
all
work already done while maintaining consistency after system crashes. A heuristic algorithm is developed to reduce the number of swaps needed during leaf reorganization, so that better concurrency and easier recovery can be achieved. A detailed description of switching from the old B
+
-tree to the new B
+
-tree is described for the first time.
Data access for the masses through OLE DB
Authors: Blakeley José A.
Published: November 2005

This paper presents an overview of OLE DB, a set of interfaces being developed at Microsoft whose goal is to enable applications to have uniform access to data stored in DBMS and non-DBMS information containers. Applications will be able to take advantage of the benefits of database technology without having to transfer data from its place of origin to a DBMS. Our approach consists of defining an open, extensible Collection of interfaces that factor and encapsulate orthogonal, reusable portions of DBMS functionality. These interfaces define the boundaries of DBMS components such as record containers, query processors, and transaction coordinators that enable uniform, transactional access to data among such components. The proposed interfaces extend Microsoft's OLE/COM object services framework with database functionality, hence these interfaces are collectively referred to as OLE DB. The OLE DB functional areas include data access and updates (rowsets), query processing, schema information, notifications, transactions, security, and access to remote data. In a sense, OLE DB represents an effort to bring database technology to the masses. This paper presents an overview of the OLE DB approach and its areas of componentization.
Hot mirroring
Authors: Mogi Kazuhiko , Kitsuregawa Masaru
Published: November 2005

This paper proposes a storage management scheme for disk arrays, named hot mirroring. In this scheme, storage space is partitioned into two regions. One is the mirrored region, which is characterized by high performance and low storage efficiency. The other is the RAID5 region, which is characterized by low performance and high storage efficiency. Hot data blocks are stored in the former area, while cold blocks are stored in the latter. In addition, mirrored pairs and RAID5 stripes are orthogonally laid out, through which the performance degradation during rebuilding is minimized. Hot block clustering in hot mirroring achieves higher performance than conventional RAID5 arrays. The potential of hot mirroring is examined through extensive simulation.
A query language for multidimensional arrays
Authors: Libkin Leonid , Machlin Rona , Wong Limsoon
Published: November 2005

While much recent research has focussed on extending databases beyond the traditional relational model, relatively little has been done to develop database tools for querying data organized in (multidimensional) arrays. The scientific computing community has made little use of available database technology. Instead, multidimensional scientific data is typically stored in local files conforming to various data exchange formats and queried via specialized access libraries tied in to general purpose programming languages.To allow such data to be queried using known database techniques, we design and implement a query language for multidimensional arrays. Our main design decision is to treat arrays as functions from index sets to values rather than as collection types. This leads to clean syntax and semantics as well as simple but powerful optimization rules.We present a calculus for arrays that extends standard calculi for complex objects. We derive a higher-level comprehension style query language based on this calculus and describe its implementation, including a data driver for the NetCDF data exchange format. Next, we explore some optimization rules obtained from the equational laws of our core calculus. Finally, we study the expressiveness of our calculus and prove that it essentially corresponds to adding ranking to a query language for complex objects.
Towards effective and efficient free space management
Authors: McAuliffe Mark L. , Carey Michael J. , Solomon Marvin H.
Published: November 2005

An important problem faced by many database management systems is the "online object placement problem"--the problem of choosing a disk page to hold a newly allocated object. In the absence of clustering criteria, the goal is to maximize storage utilization. For main-memory based systems, simple heuristics exist that provide reasonable space utilization in the worst case and excellent utilization in typical cases. However, the storage management problem for databases includes significant additional challenges, such as minimizing I/O traffic, coping with crash recovery, and gracefully integrating space management with locking and logging.We survey several object placement algorithms, including techniques that can be found in commercial and research database systems. We then present a new object placement algorithm that we have designed for use in Shore, an object-oriented database system under development at the University of Wisconsin--Madison. Finally, we present results from a series of experiments involving actual Shore implementations of some of these algorithms. Our results show that while current object placement algorithms have serious performance deficiencies, including excessive CPU or main memory overhead, I/O traffic, or poor disk utilization, our new algorithm consistently excellent performance in all of these areas.
Query execution techniques for caching expensive methods
Authors: Hellerstein Joseph M. , Naughton Jeffrey F.
Published: November 2005

Object-Relational and Object-Oriented DBMSs allow users to invoke time-consuming ("expensive") methods in their queries. When queries containing these expensive methods are run on data with duplicate values, time is wasted redundantly computing methods on the same value. This problem has been studied in the context of programming languages, where "memoization" is the standard solution. In the database literature, sorting has been proposed to deal with this problem. We compare these approaches along with a third solution, a variant of unary hybrid hashing which we call
Hybrid Cache.
We demonstrate that Hybrid Cache always dominates memoization, and significantly outperforms sorting in many instances. This provides new insights into the tradeoff between hashing and sorting for unary operations. Additionally, our Hybrid Cache algorithm includes some new optimization for unary hybrid hashing, which can be used for other applications such as grouping and duplicate elimination. We conclude with a discussion of techniques for caching multiple expensive methods in a single query, and raise some new optimization problems in choosing caching techniques.
Accessing relational databases from the World Wide Web
Authors: Nguyen Tam , Srinivasan V.
Published: November 2005

With the growing popularity of the internet and the World Wide Web (Web), there is a fast growing demand for access to database management systems (DBMS) from the Web. We describe here techniques that we invented to bridge the gap between HTML, the standard markup language of the Web, and SQL, the standard query language used to access relational DBMS. We propose a flexible general purpose variable substitution mechanism that provides cross-language variable substitution between HTML input and SQL query strings as well as between SQL result rows and HTML output thus enabling the application developer to use the full capabilities of
HTML
for creation of query forms and reports, and
SQL
for queries and updates. The cross-language variable substitution mechanism has been used in the design and implementation of a system called DB2 WWW Connection that enables quick and easy construction of applications that access relational DBMS data from the Web. An end user of these DB2 WWW applications sees only the forms for his or her requests and resulting reports. A user fills out the forms, points and clicks to navigate the forms and to access the database as determined by the application.
The Garlic project
Authors: Roth M. Tork , Arya M. , Haas L. , Carey M. , Cody W. , Fagin R. , Schwarz P. , Thomas J. , Wimmers E.
Published: November 2005

The goal of the Garlic [1] project is to build a multimedia information system capable of integrating data that resides in different database systems as well as in a variety of non-database data servers. This integration must be enabled while maintaining the independence of the data servers, and without creating copies of their data. "Multimedia" should be interpreted broadly to mean not only images, video, and audio, but also text and application specific data types (e.g., CAD drawings, medical objects, …). Since much of this data is naturally modeled by objects, Garlic provides an object-oriented schema to applications, interprets object queries, creates execution plans for sending pieces of queries to the appropriate data servers, and assembles query results for delivery back to the applications. A significant focus of the project is support for "intelligent" data servers, i.e., servers that provide media-specific indexing and query capabilities [2]. Database optimization technology is being extended to deal with heterogeneous collections of data servers so that efficient data access plans can be employed for multi-repository queries.A prototype of the Garlic system has been operational since January 1995. Queries are expressed in an SQL-like query language that has been extended to include object-oriented features such as reference-valued attributes and nested sets. In addition to a C++ API, Garlic supports a novel query/browser interface called PESTO [3]. This component of Garlic provides end users of the system with a friendly, graphical interface that supports interactive browsing, navigation, and querying of the contents of Garlic databases. Unlike existing interfaces to databases, PESTO allows users to move back and forth seamlessly between querying and browsing activities, using queries to identify interesting subsets of the database, browsing the subset, querying the content of a set-valued attribute of a particularly interesting object in the subset, and so on.
Range queries in OLAP data cubes
Authors: Ho Ching-Tien , Agrawal Rakesh , Megiddo Nimrod , Srikant Ramakrishnan
Published: November 2005

A range query applies an aggregation operation over all selected cells of an OLAP data cube where the selection is specified by providing ranges of values for numeric dimensions. We present fast algorithms for range queries for two types of aggregation operations: SUM and MAX. These two operations cover techniques required for most popular aggregation operations, such as those supported by SQL.

For range-sum queries, the essential idea is to precompute some auxiliary information (prefix sums) that is used to answer ad hoc queries at run-time. By maintaining auxiliary information which is of the same size as the data cube, all range queries for a given cube can be answered in constant time, irrespective of the size of the sub-cube circumscribed by a query. Alternatively, one can keep auxiliary information which is 1/

b
d

of the size of the
d
-dimensional data cube. Response to a range query may now require access to some cells of the data cube in addition to the access to the auxiliary information, but the overall time complexity is typically reduced significantly. We also discuss how the precomputed information is incrementally updated by batching updates to the data cube. Finally, we present algorithms for choosing the subset of the data cube dimensions for which the auxiliary information is computed and the blocking factor to use for each such subset.

Our approach to answering range-max queries is based on precomputed max over balanced hierarchical tree structures. We use a branch-and-bound-like procedure to speed up the finding of max in a region. We also show that with a branch-and-bound procedure, the average-case complexity is much smaller than the worst-case complexity.
The BUCKY object-relational benchmark
Authors: Carey Michael J. , DeWitt David J. , Naughton Jeffrey F. , Asgarian Mohammad , Brown Paul , Gehrke Johannes E. , Shah Dhaval N.
Published: November 2005

According to various trade journals and corporate marketing machines, we are now on the verge of a revolution—the object-relational database revolution. Since we believe that no one should face a revolution without appropriate armaments, this paper presents BUCKY, a new benchmark for object-relational database systems. BUCKY is a query-oriented benchmark that tests many of the key features offered by object-relational systems, including row types and inheritance, references and path expressions, sets of atomic values and of references, methods and late binding, and user-defined abstract data types and their methods. To test the maturity of object-relational technology relative to relational technology, we provide both an object-relational version of BUCKY and a relational equivalent thereof (i.e., a relational BUCKY simulation). Finally, we briefly discuss the initial performance results and lessons that resulted from applying BUCKY to one of the early object-relational database system products.
Balancing push and pull for data broadcast
Authors: Acharya Swarup , Franklin Michael , Zdonik Stanley
Published: November 2005

The increasing ability to interconnect computers through internet-working, wireless networks, high-bandwidth satellite, and cable networks has spawned a new class of information-centered applications based on
data dissemination
. These applications employ broadcast to deliver data to very large client populations. We have proposed the Broadcast Disks paradigm [Zdon94, Acha95b] for organizing the contents of a data broadcast program and for managing client resources in response to such a program. Our previous work on Broadcast Disks focused exclusively on the “push-based” approach, where data is sent out on the broadcast channel according to a periodic schedule, in anticipation of client requests. In this paper, we study how to augment the push-only model with a “pull-based” approach of using a backchannel to allow clients to send explicit requests for data to the server. We analyze the scalability and performance of a broadcast-based system that integrates push and pull and study the impact of this integration on both the steady state and warm-up performance of clients. Our results show that a client backchannel can provide significant performance improvement in the broadcast environment, but that unconstrained use of the backchannel can result in scalability problems due to server saturation. We propose and investigate a set of three techniques that can delay the onset of saturation and thus, enhance the performance and scalability of the system.
InfoSleuth
Authors: Bayardo R. J. , Bohrer W. , Brice R. , Cichocki A. , Fowler J. , Helal A. , Kashyap V. , Ksiezyk T. , Martin G. , Nodine M. , Rashid M. , Rusinkiewicz M. , Shea R. , Unnikrishnan C. , Unruh A. , Woelk D.
Published: November 2005

The goal of the InfoSleuth project at MCC is to exploit and synthesize new technologies into a unified system that retrieves and processes information in an ever-changing network of information sources. InfoSleuth has its roots in the Carnot project at MCC, which specialized in integrating heterogeneous information bases. However, recent emerging technologies such as internetworking and the World Wide Web have significantly expanded the types, availability, and volume of data available to an information management system. Furthermore, in these new environments, there is no formal control over the registration of new information sources, and applications tend to be developed without complete knowledge of the resources that will be available when they are run. Federated database projects such as Carnot that do static data integration do not scale up and do not cope well with this ever-changing environment. On the other hand, recent Web technologies, based on keyword search engines, are scalable but, unlike federated databases, are incapable of accessing information based on concepts. In this experience paper, we describe the architecture, design, and implementation of a working version of InfoSleuth. We show how InfoSleuth integrates new technological developments such as agent technology, domain ontologies, brokerage, and internet computing, in support of mediated interoperation of data and services in a dynamic and open environment. We demonstrate the use of information brokering and domain ontologies as key elements for scalability.
A framework for implementing hypothetical queries
Authors: Griffin Timothy , Hull Richard
Published: November 2005

Previous approaches to supporting hypothetical queries have been “eager”: some representation of the hypothetical state (or the corresponding delta) is materialized, and query evaluation is filtered through that representation. This paper develops a framework for evaluating hypothetical queries using a “lazy” approach, or using a hybrid of eager and lazy approaches.

We focus on queries having the form “
Q
when {{
U
}}” where
Q
is a relational algebra query and
U
is an update expression. The value assigned to this query in state
DB
is the value that
Q
would return in the state resulting from executing
U
on
DB
. Nesting of the keyword when is permitted, and
U
may involve a sequence of several atomic updates.

We present an equational theory for queries involving when that can be used as a basis for optimization. This theory is very different from traditional rules for the relational algebra, because the semantics of when is unlike the semantics of the algebra operators. Our theory is based on the observation that hypothetical states can be represented as substitutions, similar to those arising in functional and logic programming. Furthermore, hypothetical queries of the form
Q
when {{
U
}} can be thought of as representing the
suspended
application of a substitution. Using the equational theory we develop an approach to optimizing the evaluation of hypothetical queries that uses deltas in the sense of Heraclitus, and permits a range of evaluation strategies from lazy to eager.
Wave-indices
Authors: Shivakumar Narayanan , García-Molina Héctor
Published: November 2005

In many applications, new data is being generated every day. Often an index of the data of a past window of days is required to answer queries efficiently. For example, in a warehouse one may need an index on the sales records of the last week for efficient data mining, or in a Web service one may provide an index of Netnews articles of the past month. In this paper, we propose a variety of
wave indices
where the data of a new day can be efficiently added, and old data can be quickly expired, to maintain the required window. We compare these schemes based on several system performance measures, such as storage, query response time, and maintenance work, as well as on their simplicity and ease of coding.
On-line warehouse view maintenance
Authors: Quass Dallan , Widom Jennifer
Published: November 2005

Data warehouses store materialized views over base data from external sources. Clients typically perform complex read-only queries on the views. The views are refreshed periodically by
maintenance transactions
, which propagate large batch updates from the base tables. In current warehousing systems, maintenance transactions usually are isolated from client read activity, limiting availability and/or size of the warehouse. We describe an algorithm called
2VNL
that allows warehouse maintenance transactions to run concurrently with readers. By logically maintaining two versions of the database, no locking is required and serializability is guaranteed. We present our algorithm, explain its relationship to other multi-version concurrency control algorithms, and describe how it can be implemented on top of a conventional relational DBMS using a query rewrite approach.
Supporting multiple view maintenance policies
Authors: Colby Latha S. , Kawaguchi Akira , Lieuwen Daniel F. , Mumick Inderpal Singh , Ross Kenneth A.
Published: November 2005

Materialized views and view maintenance are becoming increasingly important in practice. In order to satisfy different data currency and performance requirements, a number of view maintenance policies have been proposed. Immediate maintenance involves a potential refresh of the view after every update to the deriving tables. When staleness of views can be tolerated, a view may be refreshed periodically or (on-demand) when it is queried. The maintenance policies that are chosen for views have implications on the validity of the results of queries and affect the performance of queries and updates. In this paper, we investigate a number of issues related to supporting multiple views with different maintenance policies.

We develop formal notions of consistency for views with different maintenance policies. We then introduce a model based on view groupings for view maintenance policy assignment, and provide algorithms, based on the viewgroup model, that allow consistency of views to be guaranteed. Next, we conduct a detailed study of the performance aspects of view maintenance policies based on an actual implementation of our model. The performance study investigates the trade-offs between different maintenance policy assignments. Our analysis of both the consistency and performance aspects of various view maintenance policies are important in making correct maintenance policy assignments.
Delaunay
Authors: Cruz Isabel F. , Averbuch M. , Lucas Wendy T. , Radzyminski Melissa , Zhang Kirby
Published: November 2005

Visual query systems have traditionally supported a set of pre-defined visual displays. We describe the
Delaunay
system, which supports visualizations of object-oriented databases specified by the user with a visual constraint-based query language. The highlights of our approach are the expressiveness of the visual query language, the efficiency of the query engine, and the overall flexibility and extensibility of the framework. The user interface is implemented using Java and is available on the WWW.
Reusing invariants
Authors: Rao Jun , Ross Kenneth A.
Published: November 2005

Correlated queries are very common and important in decision support systems. Traditional nested iteration evaluation methods for such queries can be very time consuming. When they apply, query rewriting techniques have been shown to be much more efficient. But query rewriting is not always possible. When query rewriting does not apply, can we do something better than the traditional nested iteration methods? In this paper, we propose a new invariant technique to evaluate correlated queries efficiently. The basic idea is to recognize the part of the subquery that is not related to the outer references and cache the result of that part after its first execution. Later, we can reuse the result and combine it with the result of the rest of the subquery that is changing for each iteration. Our technique applies to arbitrary correlated subqueries.

This paper introduces algorithms to recognize the invariant part of a data flow tree, and to restructure the evaluation plan to reuse the stored intermediate result. We also propose an efficient method to teach an existing join optimizer to understand the invariant feature and thus allow it to be able to generate better join plans in the new context. Some other related optimization techniques are also discussed. The proposed techniques were implemented within three months on an existing real commercial database system.

We also experimentally evaluate our proposed technique. Our evaluation indicates that, when query rewriting is not possible, the invariant technique is significantly better than the traditional nested iteration method. Even when query rewriting applies, the invariant technique is sometimes better than the query rewriting technique. Our conclusion is that the invariant technique should be considered as one of the alternatives in evaluating correlated queries since it fills the gap left by rewriting techniques.
CURE
Authors: Guha Sudipto , Rastogi Rajeev , Shim Kyuseok
Published: November 2005

Clustering, in data mining, is useful for discovering groups and identifying interesting distributions in the underlying data. Traditional clustering algorithms either favor clusters with spherical shapes and similar sizes, or are very fragile in the presence of outliers. We propose a new clustering algorithm called CURE that is more robust to outliers, and identifies clusters having non-spherical shapes and wide variances in size. CURE achieves this by representing each cluster by a certain fixed number of points that are generated by selecting
well scattered
points from the cluster and then shrinking them toward the center of the cluster by a specified fraction. Having more than one representative point per cluster allows CURE to adjust well to the geometry of non-spherical shapes and the shrinking helps to dampen the effects of outliers. To handle large databases, CURE employs a combination of
random sampling
and
partitioning
. A random sample drawn from the data set is first partitioned and each partition is
partially
clustered. The partial clusters are then clustered in a second pass to yield the desired clusters. Our experimental results confirm that the quality of clusters produced by CURE is much better than those found by existing algorithms. Furthermore, they demonstrate that random sampling and partitioning enable CURE to not only outperform existing algorithms but also to scale well for large databases without sacrificing clustering quality.
Optimal multi-step k-nearest neighbor search
Authors: Seidl Thomas , Kriegel Hans-Peter
Published: November 2005

For an increasing number of modern database applications, efficient support of similarity search becomes an important task. Along with the complexity of the objects such as images, molecules and mechanical parts, also the complexity of the similarity models increases more and more. Whereas algorithms that are directly based on indexes work well for simple medium-dimensional similarity distance functions, they do not meet the efficiency requirements of complex high-dimensional and adaptable distance functions. The use of a multi-step query processing strategy is recommended in these cases, and our investigations substantiate that the number of candidates which are produced in the filter step and exactly evaluated in the refinement step is a fundamental efficiency parameter. After revealing the strong performance shortcomings of the state-of-the-art algorithm for
k
-nearest neighbor search [Korn et al. 1996], we present a novel multi-step algorithm which is guaranteed to produce the minimum number of candidates. Experimental evaluations demonstrate the significant performance gain over the previous solution, and we observed average improvement factors of up to 120 for the number of candidates and up to 48 for the total runtime.
Your mediators need data conversion!
Authors: Cluet Sophie , Delobel Claude , Siméon Jérǒme , Smaga Katarzyna
Published: November 2005

Due to the development of the World Wide Web, the integration of heterogeneous data sources has become a major concern of the database community. Appropriate architectures and query languages have been proposed. Yet, the problem of data conversion which is essential for the development of mediators/wrappers architectures has remained largely unexplored.

In this paper, we present the YAT system for data conversion. This system provides tools for the specification and the implementation of data conversions among heterogeneous data sources. It relies on a middleware model, a declarative language, a customization mechanism and a graphical interface.

The model is based on named trees with ordered and labeled nodes. Like semistructured data models, it is simple enough to facilitate the representation of any data. Its main originality is that it allows to reason at various levels of representation. The YAT conversion language (called YATL) is declarative, rule-based and features enhanced pattern matching facilities and powerful restructuring primitives. It allows to preserve or reconstruct the order of collections. The customization mechanism relies on program instantiations: an existing program may be instantiated into a more specific one, and then easily modified. We also present the architecture, implementation and practical use of the YAT prototype, currently under evaluation within the OPAL
*
project.
Cost-based optimization of decision support queries using transient-views
Authors: Subramanian Subbu N. , Venkataraman Shivakumar
Published: November 2005

Next generation decision support applications, besides being capable of processing huge amounts of data, require the ability to integrate and reason over data from multiple, heterogeneous data sources. Often, these data sources differ in a variety of aspects such as their data models, the query languages they support, and their network protocols. Also, typically they are spread over a wide geographical area. The cost of processing decision support queries in such a setting is quite high. However, processing these queries often involves redundancies such as repeated access of same data source and multiple execution of similar processing sequences. Minimizing these redundancies would significantly reduce the query processing cost. In this paper, we (1) propose an architecture for processing complex decision support queries involving multiple, heterogeneous data sources; (2) introduce the notion of
transient-views
— materialized views that exist only in the context of execution of a query — that is useful for minimizing the redundancies involved in the execution of these queries; (3) develop a
cost-based
algorithm that takes a query plan as input and generates an optimal “covering plan”, by minimizing redundancies in the original plan; (4) validate our approach by means of an implementation of the algorithms and a detailed performance study based on TPC-D benchmark queries on a commercial database system; and finally, (5) compare and contrast our approach with work in related areas, in particular, the areas of answering queries using views and optimization using common sub-expressions. Our experiments demonstrate the practicality and usefulness of transient-views in significantly improving the performance of decision support queries.