bluuebunny/crossref_metadata_2025 huggingface dataset:
Bitmap index design and evaluation
Authors: Chan Chee-Yong , Ioannidis Yannis E.
Published: November 2005

Bitmap indexing has been touted as a promising approach for processing complex adhoc queries in read-mostly environments, like those of decision support systems. Nevertheless, only few possible bitmap schemes have been proposed in the past and very little is known about the space-time tradeoff that they offer. In this paper, we present a general framework to study the design space of bitmap indexes for selection queries and examine the disk-space and time characteristics that the various alternative index choices offer. In particular, we draw a parallel between bitmap indexing and number representation in different number systems, and define a space of two orthogonal dimensions that captures a wide array of bitmap indexes, both old and new. Within that space, we identify (analytically or experimentally) the following interesting points: (1) the time-optimal bitmap index; (2) the space-optimal bitmap index; (3) the bitmap index with the optimal space-time tradeoff (knee); and (4) the time-optimal bitmap index under a given disk-space constraint. Finally, we examine the impact of bitmap compression and bitmap buffering on the space-time tradeoffs among those indexes. As part of this work, we also describe a bitmap-index-based evaluation algorithm for selection queries that represents an improvement over earlier proposals. We believe that this study offers a useful first set of guidelines for physical database design using bitmap indexes.
A multi-similarity algebra
Authors: Adali S. , Bonatti P. , Sapino M. L. , Subrahmanian V. S.
Published: November 2005

The need to automatically extract and classify the contents of multimedia data archives such as images, video, and text documents has led to significant work on similarity based retrieval of data. To date, most work in this area has focused on the creation of index structures for similarity based retrieval. There is very little work on developing formalisms for querying multimedia databases that support similarity based computations and optimizing such queries, even though it is well known that feature extraction and identification algorithms in media data are very expensive. We introduce a similarity algebra that brings together relational operators and results of multiple similarity implementations in a uniform language. The algebra can be used to specify complex queries that combine different interpretations of similarity values and multiple algorithms for computing these values. We prove equivalence and containment relationships between similarity algebra expressions and develop query rewriting methods based on these results. We then provide a generic cost model for evaluating cost of query plans in the similarity algebra and query optimization methods based on this model. We supplement the paper with experimental results that illustrate the use of the algebra and the effectiveness of query optimization methods using the Integrated Search Engine (I.SEE) as the testbed.
Enterprise Java platform data access
Authors: White Seth , Cattell Rick , Finkelstein Shel
Published: November 2005

This paper describes alternative methods for data access that are available to developers using the Java™ platform and related technologies to create a new generation of enterprise applications. The paper highlights industry trends and describes Java technologies that are responsible for a new paradigm in data access. Java technology represents a new level of portability, scalability, and ease-of-use for applications that require data access.
SQL open heterogeneous data access
Authors: Reinwald Berthold , Pirahesh Hamid
Published: November 2005

We describe the open, extensible architecture of SQL for accessing data stored in external data sources not managed by the SQL engine. In this scenario, SQL engines act as middleware servers providing access to external data using SQL DML statements and joining external data with SQL tables in heterogeneous queries. We describe the state-of-the art in object-relational systems and their companion products, and provide an outlook on future directions.
A data mining application
Authors: Ng KianSing , Liu Huan , Kwah HweeBong
Published: November 2005

“Customer retention” is an important real-world problem in many sales and services related industries today. This work illustrates how we can integrate the various techniques of data-mining, such as decision-tree induction, deviation analysis and multiple concept-level association rules to form an intuitive and novel approach to gauging customer's loyalty and predicting their likelihood of defection. Immediate action taken against these “early-warnings” is often the key to the eventual retention or loss of the customers involved.
Oracle Rdb's record caching model
Authors: Anderson Richard , Arun Gopalan , Frank Richard
Published: November 2005

In this paper we present a more efficient record based caching model than the conventional page (disk block) based scheme. In a record caching model, individual records are stored together in a section of shared memory to form the cache. Traditional relational database systems have individual pages that are stored together in shared memory to form the cache and records are then extracted from these pages on demand. The record cache model has better memory utilization than the page model and also helps reduce overheads like page fetches/writes, page locks and code path.

In May 1996, Oracle Rdb announced a record breaking number of 14227 tpmC on a Digital AlphaServer 8400. At the time, this was the best TPC-C performance achieved on a single SMP machine. A total of 15 record caches, caching 19.5 million records, consuming almost 7 GB of memory, formed the bulk of the shared memory.
DataSplash
Authors: Olston Chris , Woodruff Allison , Aiken Alexander , Chu Michael , Ercegovac Vuk , Lin Mark , Spalding Mybrid , Stonebraker Michael
Published: November 2005

Database visualization is an area of growing importance as database systems become larger and more accessible. DataSplash is an easy-to-use, integrated environment for navigating, creating, and querying visual representations of data. We will demonstrate the three main components which make up the DataSplash environment: a navigation system, a direct-manipulation interface for creating and modifying visualizations, and a direct-manipulation visual query system.
The IDEA Web lab
Authors: Ceri Stefano , Fraternali Piero , Paraboschi Stefano
Published: November 2005

With the spreading of the World Wide Web as a uniform and ubiquitous interface to computer applications and information, novel opportunities are offered for introducing significant changes in all organizations and their processes. This demo presents the IDEA Web Laboratory (Web Lab), a Web-based software design environment available on the Internet, which demonstrates a novel approach to the software production process on the Web.
Perspectives on and problems with computer-mediated teamwork
Authors: Vick Rita M.
Published: November 2005

The current business environment is characterized by increasing globalization of the workplace and the use of teams working in distributed environments to cope with uncertainty, change, ambiguous problem definitions, and rapidly changing information. The technologies facilitating this virtual workplace include groupware for workflow process management and distributed meeting support. Groupware interventions have not been accepted by the majority of potential users. This paper attempts to determine why there has been resistance to adoption of these seemingly important technologies. Discussions of the author's experiences as facilitator of an electronic meeting room facility, structure and uses of teams in the workplace, computer support for work teams, ways that teams learn, researched variables, and cultural factors to be considered in the design of groupware systems are presented.
Satisfaction, technology adoption, and performance in project teams
Authors: Panko Raymond R. , Kinney Susan T.
Published: November 2005

Rita Vick's paper focuses on technology adoption and performance in teamwork contexts. One way to increase performance, she argues, is to increase information sharing. This commentary argues that adoption, performance, and information sharing may depend on satisfaction with current project work. The paper notes that there is evidence that satisfaction with project work is very high. If this is the case, then the adoption of teamwork technologies should continue to be slow. Furthermore, high satisfaction can have a negative impact on group performance, because it may cause team members not to stress challenging information that could disrupt team harmony. We suggest that the experiments that Vick proposes consider satisfaction and consider not only general information sharing but also classify information shared in terms of potential divisiveness.
LOF
Authors: Breunig Markus M. , Kriegel Hans-Peter , Ng Raymond T. , Sander Jörg
Published: November 2005

For many KDD applications, such as detecting criminal activities in E-commerce, finding the rare instances or the outliers, can be more interesting than finding the common patterns. Existing work in outlier detection regards being an outlier as a binary property. In this paper, we contend that for many scenarios, it is more meaningful to assign to each object a
degree
of being an outlier. This degree is called the
local outlier factor
(LOF) of an object. It is
local
in that the degree depends on how isolated the object is with respect to the surrounding neighborhood. We give a detailed formal analysis showing that LOF enjoys many desirable properties. Using real-world datasets, we demonstrate that LOF can be used to find outliers which appear to be meaningful, but can otherwise not be identified with existing approaches. Finally, a careful performance evaluation of our algorithm confirms we show that our approach of finding local outliers can be practical.
On wrapping query languages and efficient XML integration
Authors: Christophides Vassilis , Cluet Sophie , Simèon Jérǒme
Published: November 2005

Modern applications (Web portals, digital libraries, etc.) require integrated access to various information sources (from traditional DBMS to semistructured Web repositories), fast deployment and low maintenance cost in a rapidly evolving environment. Because of its flexibility, there is an increasing interest in using XML as a middleware model for such applications. XML enables fast wrapping and declarative integration. However, query processing in XML-based integration systems is still penalized by the lack of an algebra with adequate optimization properties and the difficulty to understand source query capabilities. In this paper, we propose an algebraic approach to support efficient XML query evaluation. We define a general purpose algebra suitable for semistructured on XML query languages. We show how this algebra can be used, with appropriate type information, to also wrap more structured query languages such as OQL or SQL. Finally, we develop new optimization techniques for XML-based integration systems.
Influence sets based on reverse nearest neighbor queries
Authors: Korn Flip , Muthukrishnan S.
Published: November 2005

Inherent in the operation of many decision support and continuous referral systems is the notion of the “influence” of a data point on the database. This notion arises in examples such as finding the set of customers affected by the opening of a new store outlet location, notifying the subset of subscribers to a digital library who will find a newly added document most relevant,
etc.
Standard approaches to determining the influence set of a data point involve range searching and nearest neighbor queries.

In this paper, we formalize a novel notion of influence based on reverse neighbor queries and its variants. Since the nearest neighbor relation is not symmetric, the set of points that are closest to a query point (
i.e.
, the nearest neighbors) differs from the set of points that have the query point as their nearest neighbor (called the reverse nearest neighbors). Influence sets based on reverse nearest neighbor (RNN) queries seem to capture the intuitive notion of influence from our motivating examples.

We present a general approach for solving RNN queries and an efficient R-tree based method for large data sets, based on this approach. Although the RNN query appears to be natural, it has not been studied previously. RNN queries are of independent interest, and as such should be part of the suite of available queries for processing spatial and multimedia data. In our experiments with real geographical data, the proposed method appears to scale logarithmically, whereas straightforward sequential scan scales linearly. Our experimental study also shows that approaches based on range searching or nearest neighbors are ineffective at finding influence sets of our interest.
A chase too far?
Authors: Popa Lucian , Deutsch Alin , Sahuguet Arnaud , Tannen Val
Published: November 2005

In a previous paper we proposed a novel method for generating alternative query plans that uses chasing (and back-chasing) with logical constraints. The method brings together use of indexes, use of materialized views, semantic optimization and join elimination (minimization). Each of these techniques is known separately to be beneficial to query optimization. The novelty of our approach is in allowing these techniques to interact systematically, eg. non-trivial use of indexes and materialized views may be enabled only by semantic constraints.

We have implemented our method for a variety of schemas and queries. We examine how far we can push the method in term of complexity of both schemas and queries. We propose a technique for reducing the size of the search space by “stratifying” the sets of constraints used in the (back)chase. The experimental results demonstrate that our method is practical (i.e., feasible
and
worthwhile).
The onion technique
Authors: Chang Yuan-Chi , Bergman Lawrence , Castelli Vittorio , Li Chung-Sheng , Lo Ming-Ling , Smith John R.
Published: November 2005

This paper describes the Onion technique, a special indexing structure for linear optimization queries. Linear optimization queries ask for top-N records subject to the maximization or minimization of linearly weighted sum of record attribute values. Such query appears in many applications employing linear models and is an effective way to summarize representative cases, such as the top-50 ranked colleges. The Onion indexing is based on a geometric property of convex hull, which guarantees that the optimal value can always be found at one or more of its vertices. The Onion indexing makes use of this property to construct convex hulls in layers with outer layers enclosing inner layers geometrically. A data record is indexed by its layer number or equivalently its depth in the layered convex hull. Queries with linear weightings issued at run time are evaluated from the outmost layer inwards. We show experimentally that the Onion indexing achieves orders of magnitude speedup against sequential linear scan when N is small compared to the cardinality of the set. The Onion technique also enables progressive retrieval, which processes and returns ranked results in a progressive manner. Furthermore, the proposed indexing can be extended into a hierarchical organization of data to accommodate both global and local queries.
Online index rebuild
Authors: Ponnekanti Nagavamsi , Kodavalla Hanuma
Published: November 2005

In this paper we present an efficient method to do online rebuild of a B+-tree index. This method has been implemented in Sybase Adaptive Server Enterprise (ASE) Version 12.0. It provides high concurrency, does minimal amount of logging, has good performance and does not deadlock with other index operations. It copies the index rows to newly allocated pages in the key order so that good space utilization and clustering are achieved. The old pages are deallocated during the process. Our algorithm differs from the previously published online index rebuild algorithms in two ways. It rebuilds multiple leaf pages and then propagates the changes to higher levels. Also, while propagating the leaf level changes to higher levels, level 1
1
pages are reorganized, eliminating the need for a separate pass. Our performance study shows that our approach results in significant reduction in logging and CPU time. Also, our approach uses the same concurrency control mechanism as split and shrink operations, which made it attractive for implementation.
Handling very large databases with informix extended parallel server
Authors: Weininger Andreas
Published: November 2005

In this paper, we investigate which problems exist in very large real databases and describe which mechanisms are provided by Informix Extended Parallel Server (XPS) for dealing with these problems. Currently the largest customer XPS database contains 27 TB of data. A database server that has to handle such an amount of data has to provide mechanisms which allow achieving adequate performance and easing the usability. We will present mechanisms which address both of these issues and illustrate them with examples from real customer systems.
From browsing to interacting
Authors: Ramakrishnan Raghu
Published: November 2005

Internet websites increasingly rely on database management systems. There are several reasons for this trend:

As sites grow larger, managing the content becomes impossible without the use of a DBMS to keep track of the nature, origin, authorship, and modification history of each article.

As sites become more interactive, tracking and logging user activity and user contributions creates valuable new data, which again is best managed using a DBMS. The emerging paradigm of
Customer-Centric e-Business
places a premium on engaging users, building a relationship with them across visits, and leveraging their expertise and feed-back. Supporting this paradigm means that we not only have to track what users visit on a site, we also have to enable them to offer opinions and contribute to the content of the website in various ways; naturally, this requires us to use a DBMS.

In order to personalize a user's experience, a site must dynamically construct (or at least fine-tune) each page as it is delivered, taking into account information about the user's past activity and the nature of the content on the current page. In other words, personalization is made possible by utilizing the information (about content and user activity) that we already indicated is best managed using a DBMS.

In summary, as websites go beyond a passive collection of pages to be browsed and seek to present users with a personalized, interactive experience, the role of database management systems becomes central.

In this talk, I will present an overview of these issues, including a discussion of related techniques such as
cookies
and
web server logs
for tracking user activity.
Application architecture (panel session)
Authors: Nori Anil K.
Published: November 2005

Experienced panelist will share their views on application architecture, specially, as it relates to database systems. The discussion will focus on what technologies and mechanisms are necessary for developing web applications, and where these mechanisms should reside.
LDAP directory services- just another database application? (tutorial session)
Authors: Shukla Shridhar , Deshpande Anand
Published: November 2005

The key driving force behind general-purpose enterprise directory services is for providing a central repository for commonly and widely used information such as users, groups, network service access information and profiles, security information, etc. Acceptance of the Lightweight Directory Access Protocol (LDAP) as an access protocol has facilitated widespread integration of these directory services into the network infrastructure and applications.

Both directory and relational databases are data repositories sharing the characteristic that they have mechanisms for dealing with schema and structure of information and are suitable for systematically organized data. This tutorial describes characteristics of directories such as schema information, query language and support, storage mechanisms required, typical requirements imposed by applications, etc. We then explain the differences between a directory and relational database, and show how the two are required to co-exist in a typical enterprise.

An essential characteristic assumed for information stored in directories is that it is relatively static and that the queries are mostly read only. We describe typical directory applications to validate this assumption and project the requirements imposed on them as these applications evolve. We then describe areas of overlap between traditional databases and directories, describe some database and directory integration solutions adopted in the market, and identify areas in which directory deployment can benefit from the experience gathered by the database community.
Bit-sliced index arithmetic
Authors: Rinfret Denis , O'Neil Patrick , O'Neil Elizabeth
Published: November 2005

The bit-sliced index (
BSI
) was originally defined in [ONQ97]. The current paper introduces the concept of BSI arithmetic. For any two BSI's X and Y on a table T, we show how to efficiently generate new BSI's Z, V, and W, such that Z = X + Y, V = X - Y, and W = MIN(X, Y); this means that if a row r in T has a value x represented in BSI X and a value y in BSI Y, the value for r in BSI Z will be x + y, the value in V will be x - y and the value in W will be MIN(x, y). Since a bitmap representing a set of rows is the simplest bit-sliced index, BSI arithmetic is the most straightforward way to determine multisets of rows (with duplicates) resulting from the SQL clauses UNION ALL (addition), EXCEPT ALL (subtraction), and INTERSECT ALL (min) (see [OO00, DB2SQL] for definitions of these clauses). Another contribution of the current paper is to generalize BSI range restrictions from [ONQ97] to a new non-Boolean form: to determine the top k BSI-valued rows, for ally meaningful value k between one and the total number of rows in T. Together with bit-sliced addition, this permits us to solve a common basic problem of text retrieval: given an object-relational table T of rows representing documents, with a collection type column K representing keyword terms, we demonstrate an efficient algorithm to find k documents that share the largest number of terms with some query list Q of terms. A great deal of published work on such problems exists in the Information Retrieval (
IR
) field. The algorithm we introduce, which we call Bit-Sliced Term-Matching, or BSTM, uses an approach comparable in performance to the most efficient known IR algorithm, a major improvement on current DBMS text searching algorithms, with the advantage that it uses only indexing we propose for native database operations.
Probe, count, and classify
Authors: Ipeirotis Panagiotis G. , Gravano Luis , Sahami Mehran
Published: November 2005

The contents of many valuable web-accessible databases are only accessible through search interfaces and are hence invisible to traditional web “crawlers.” Recent studies have estimated the size of this “hidden web” to be 500 billion pages, while the size of the “crawlable” web is only an estimated two billion pages. Recently, commercial web sites have started to manually organize web-accessible databases into Yahoo!-like hierarchical classification schemes. In this paper, we introduce a method for automating this classification process by using a small number of query probes. To classify a database, our algorithm does not retrieve or inspect any documents or pages from the database, but rather just exploits the number of matches that each query probe generates at the database in question. We have conducted an extensive experimental evaluation of our technique over collections of real documents, including over one hundred web-accessible databases. Our experiments show that our system has low overhead and achieves high classification accuracy across a variety of databases.
Efficient evaluation of XML middle-ware queries
Authors: Fernandez Mary , Morishima Atsuyuki , Suciu Dan
Published: November 2005

We address the problem of efficiently constructing materialized XML views of relational databases. In our setting, the XML view is specified by a query in the declarative query language of a middle-ware system, called SilkRoute. The middle-ware system evaluates a query by sending one or more SQL queries to the target relational database, integrating the resulting tuple streams, and adding the XML tags. We focus on how to best choose the SQL queries, without having control over the target RDBMS.
A robust, optimization-based approach for approximate answering of aggregate queries
Authors: Chaudhuri Surajit , Das Gautam , Narasayya Vivek
Published: November 2005

The ability to approximately answer aggregation queries accurately and efficiently is of great benefit for decision support and data mining tools. In contrast to previous sampling-based studies, we treat the problem as an
optimization
problem whose goal is to minimize the error in answering queries in the given workload. A key novelty of our approach is that we can tailor the choice of samples to be robust even for workloads that are “similar” but not necessarily identical to the given workload. Finally, our techniques recognize the importance of taking into account the variance in the data distribution in a principled manner. We show how our solution can be implemented on a database system, and present results of extensive experiments on Microsoft SQL Server 2000 that demonstrate the superior quality of our method compared to previous work.
Generating efficient plans for queries using views
Authors: Afrati Foto N. , Li Chen , Ullman Jeffrey D.
Published: November 2005

We study the problem or generating efficient, equivalent rewritings using views to compute the answer to a query. We take the closed-world assumption, in which views are materialized from base relations, rather than views describing sources in terms of abstract predicates, as is common when the open-world assumption is used. In the closed-world model, there can be an infinite number of different rewritings that compute the same answer, yet have quite different performance. Query optimizers take a logical plan (a rewriting of the query) as an input, and generate efficient physical plans to compute the answer. Thus our goal is to generate a small subset of the possible logical plans without missing an optimal physical plan.

We first consider a cost model that counts the number of subgoals in a physical plan, and show a search space that is guaranteed to include an optimal rewriting, if the query has a rewriting in terms of the views. We also develop an efficient algorithm for finding rewritings with the minimum number of subgoals. We then consider a cost model that counts the sizes of intermediate relations of a physical plan, without dropping any attributes, and give a search space for finding optimal rewritings. Our final cost model allows attributes to be dropped in intermediate relations. We show that, by careful variable renaming, it is possible to do better than the standard “supplementary relation” approach, by dropping attributes that the latter approach would retain. Experiments show that our algorithm of generating optimal rewritings has good efficiency and scalability.
Selectivity estimation using probabilistic models
Authors: Getoor Lise , Taskar Benjamin , Koller Daphne
Published: November 2005

Estimating the result size of complex queries that involve selection on multiple attributes and the join of several relations is a difficult but fundamental task in database query processing. It arises in cost-based query optimization, query profiling, and approximate query answering. In this paper, we show how probabilistic graphical models can be effectively used for this task as an accurate and compact approximation of the joint frequency distribution of multiple attributes across multiple relations.Probabilistic Relational Models (PRMs)are a recent development that extends graphical statistical models such as Bayesian Networks to relational domains. They represent the statistical dependencies between attributes within a table, and between attributes across foreign-key joins. We provide an efficient algorithm for constructing a PRM front a database, and show how a PRM can be used to compute selectivity estimates for a broad class of queries. One of the major contributions of this work is a unified framework for the estimation of queries involving both select and foreign-key join operations. Furthermore, our approach is not limited to answering a small set of predetermined queries; a single model can be used to effectively estimate the sizes of a wide collection of potential queries across multiple tables. We present results for our approach on several real-world databases. For both single-table multi-attribute queries and a general class of select-join queries, our approach produces more accurate estimates than standard approaches to selectivity estimation, using comparable space and time.
Communication-efficient distributed mining of association rules
Authors: Schuster Assaf , Wolff Ran
Published: November 2005

Mining for associations between items in large transactional databases is a central problem in the field of knowledge discovery. When the database is partitioned among several share-nothing machines, the problem can be addressed using distributed data mining algorithms. One such algorithm, called CD, was proposed by Agrawal and Shafer in [1] and was later enhanced by the FDM algorithm of Cheung, Han et al. [5].

The main problem with these algorithms is that they do not scale well with the number of partitions. They are thus impractical for use in modern distributed environments such as peer-to-peer systems, in which hundreds or thousands of computers may interact. In this paper we present a set of new algorithms that solve the Distributed Association Rule Mining problem using far less communication. In addition to being very efficient, the new algorithms are also extremely robust. Unlike existing algorithms, they continue to be efficient even when the data is skewed or the partition sizes are imbalanced. We present both experimental and theoretical results concerning the behavior of these algorithms and explain how they can be implemented in different settings.
Spatial data management for computer aided design
Authors: Kriegel Hans-Peter , Müller Andreas , Pötke Marco , Seidl Thomas
Published: November 2005

This demonstration presents a spatial database integration for novel CAD applications into off-the-shelf database systems. Spatial queries on even large product databases for digital mockup or haptic rendering are performed at interactive response times.
Will database researchers have any role in data security? (panel session)
Authors: Rosenthal Arnon , Dittrich Klaus , Donahue Jim , Maimone Bill
Published: November 2005

Data security issues today go far beyond the traditional questions of grant/revoke in an RDBMS. We will discuss what the new research agenda should be.
The user edit
Authors: Atlas Marshall
Published: November 2005

Possibly the simplest way to make a technical manual easier to use is a "user edit"---that is, having an inexperienced user try to work with a machine, using only its manual as a guide. His errors and hesitations should tell you where the weak points are. This report describes how to set up such tests, what to be careful of, and some of the benefite you can expect.
Document production in the real world
Authors: Cahill Andy
Published: November 2005

Changes in the user base of computer systems have increased the importance of user documentation. Technical writers must assume more responsibility in the development of a software system, and need the proper tools and equipment to accomplish the job. Changes in the technology of documents and document production dictates participation in the design of such systems by technically trained writers. The result is increased use of the system, happier users, and more sales of the system.
Non-deterministic modelling of logical queries in deductive databases
Authors: Aly Hussien , Ozsoyoglu Z. Meral
Published: November 2005

We propose a technique based on Petri Nets formalism to model logic queries in deductive databases. The model is called PNLP (Petri Net model for Logic Programs), and it has a simple formal description and a graphical representation. The PNLP model explicitly represents the relationships between rules and predicates. It is general and flexible enough to demonstrate the flow of control in different algorithms used to evaluate recursive logic queries. In fact the model unifies the level of description of these algorithms, and facilitates identifying similarities and differences between them. The inherent non-determinism in the PNLP model may also be useful in recognizing the parallelism within Horn-clause logic programs. In this paper, the PNLP model is described, and its functionality is demonstrated by modeling several existing algorithms for recursive query evaluation.
The datacycle architecture for very high throughput database systems
Authors: Herman Gary , Lee K. C. , Weinrib Abel
Published: November 2005

The evolutionary trend toward a database-driven public communications network has motivated research into database architectures capable of executing thousands of transactions per second. In this paper we introduce the Datacycle architecture, an attempt to exploit the enormous transmission bandwidth of optical systems to permit the implementation of high throughput multiprocessor database systems. The architecture has the potential for unlimited query throughput, simplified data management, rapid execution of complex queries, and efficient concurrency control. We describe the logical operation of the architecture and discuss implementation issues in the context of a prototype system currently under construction.
Mapping a semantic database model to the relational model
Authors: Lyngbaek Peter , Vianu Victor
Published: November 2005

The connection between semantic database models and the relational model is formally investigated using the Iris Data Model, which has been implemented using relational database techniques. The results focus on properties of relational schemas that are translations of Iris schemas. Two new types of constraints, cross-product constraints and multiplicity constraints are introduced to characterize the relational translations of Iris schemas. The connection established between Iris and relational schemas also yields new, unexpected information about Iris schemas. In particular, a notion of equivalence of Iris schemas is defined using their relational translations, and a result is obtained on simplifying the type structure of Iris schemas.
Concepts for transaction recovery in nested transactions
Authors: Haerder Theo , Rothermel Kurt
Published: November 2005

The concept of nested transactions offers more decomposable execution units and finer grained control over recovery and concurrency as compared to 'flat' transactions. To exploit these advantages, especially transaction recovery has to be refined and adjusted to the requirements of the control structure.

In this paper, we investigate transaction recovery for nested transactions. Therefore, a model for nested transaction is introduced allowing for synchronous and asynchronous transaction invocation as well as single call and conversational interfaces. For the resulting four parameter combinations, the properties and dependencies of transaction recovery are explored if a transaction is 'unit of recovery' and if savepoints within transactions are used to gain finer recovery units.
The 5 minute rule for trading memory for disc accesses and the 10 byte rule for trading memory for CPU time
Authors: Gray Jim , Putzolu Franco
Published: November 2005

If an item is accessed frequently enough, it should be main memory resident. For current technology, “frequently enough” means about every five minutes.

Along a similar vein, one can frequently trade memory space for CPU time. For example, bits can be packed in a byte at the expense of extra instructions to extract the bits. It makes economic sense to spend ten bytes of main memory to save one instruction per second.

These results depend on current price ratios of processors, memory and disc accesses. These ratios are changing and hence the constants in the rules are changing.
Data bases, compound objects, and networked workstations: Beyond distributed computing (Abstract)
Authors: Neff R. K.
Published: November 2005

Requirements for future data base systems are developed from the perspective of the user of a networked workstation who naturally deals with compound objects. Objects considered include full text, diagrams, maps, sound recordings, images from film and video and of art objects, spreadsheets, etc. Searching requirements and strategies over multi-objects are also considered. The context of such data base systems is the library, in its electronic or digital version. Comments are presented with respect to the digital learning environment of the future. Current related projects at Berkeley are described.
Cluster validity methods
Authors: Halkidi Maria , Batistakis Yannis , Vazirgiannis Michalis
Published: November 2005

Clustering is an unsupervised process since there are no predefined classes and no examples that would indicate grouping properties in the data set. The majority of the clustering algorithms behave differently depending on the features of the data set and the initial assumptions for defining groups. Therefore, in most applications the resulting clustering scheme requires some sort of evaluation as regards its validity. Evaluating and assessing the results of a clustering algorithm is the main subject of
cluster validity.
In this paper we present a review of the clustering validity and methods. More specifically, Part I of the paper discusses the cluster validity approaches based on
external
and
internal
criteria.
Efficient optimistic concurrency control using loosely synchronized clocks
Authors: Adya Atul , Gruber Robert , Liskov Barbara , Maheshwari Umesh
Published: November 2005

This paper describes an efficient optimistic concurrency control scheme for use in distributed database systems in which objects are cached and manipulated at client machines while persistent storage and transactional support are provided by servers. The scheme provides both serializability and external consistency for committed transactions; it uses loosely synchronized clocks to achieve global serialization. It stores only a single version of each object, and avoids maintaining any concurrency control information on a per-object basis; instead, it tracks recent invalidations on a per-client basis, an approach that has low in-memory space overhead and no per-object disk overhead. In addition to its low space overheads, the scheme also performs well. The paper presents a simulation study that compares the scheme to adaptive callback locking, the best concurrency control scheme for client-server object-oriented database systems studied to date. The study shows that our scheme outperforms adaptive callback locking for low to moderate contention workloads, and scales better with the number of clients. For high contention workloads, optimism can result in a high abort rate; the scheme presented here is a first step toward a hybrid scheme that we expect to perform well across the full range of workloads.
Towards an effective calculus for object query languages
Authors: Fegaras Leonidas , Maier David
Published: November 2005

We define a standard of
effectiveness
for a database calculus relative to a query language. Effectiveness judges suitability to serve as a processing framework for the query language, and comprises aspects of coverage, manipulability and efficient evaluation. We present the monoid calculus, and argue its effectiveness for object-oriented query languages, exemplified by OQL of ODMG-93. The monoid calculus readily captures such features as multiple collection types, aggregations, arbitrary composition of type constructors and nested query expressions. We also show how to extend the monoid calculus to deal with vectors and arrays in more expressive ways than current query languages do, and illustrate how it can handle identity and updates.
An effective hash-based algorithm for mining association rules
Authors: Park Jong Soo , Chen Ming-Syan , Yu Philip S.
Published: November 2005

In this paper, we examine the issue of mining association rules among items in a large database of sales transactions. The mining of association rules can be mapped into the problem of discovering large itemsets where a large itemset is a group of items which appear in a sufficient number of transactions. The problem of discovering large itemsets can be solved by constructing a candidate set of itemsets first and then, identifying, within this candidate set, those itemsets that meet the large itemset requirement. Generally this is done iteratively for each large
k
-itemset in increasing order of
k
where a large
k
-itemset is a large itemset with
k
items. To determine large itemsets from a huge number of candidate large itemsets in early iterations is usually the dominating factor for the overall data mining performance. To address this issue, we propose an effective hash-based algorithm for the candidate set generation. Explicitly, the number of candidate 2-itemsets generated by the proposed algorithm is, in orders of magnitude, smaller than that by previous methods, thus resolving the performance bottleneck. Note that the generation of smaller candidate sets enables us to effectively trim the transaction database size at a much earlier stage of the iterations, thereby reducing the computational cost for later iterations significantly. Extensive simulation study is conducted to evaluate performance of the proposed algorithm.
Enhancing database correctness
Authors: Hou Wen-Chi , Zhang Zhongyang
Published: November 2005

In this paper, we introduce a new type of integrity constraint, which we call a statistical constraint, and discuss its applicability to enhancing database correctness. Statistical constraints manifest embedded relationships among current attribute values in the database and are characterized by their probabilistic nature. They can be used to detect potential errors not easily detected by the conventional constraints. Methods for extracting statistical constraints from a relation and enforcement of such constraints are described. Preliminary performance evaluation of enforcing statistical constraints on a real life database is also presented.
Hypergraph based reorderings of outer join queries with complex predicates
Authors: Bhargava Gautam , Goel Piyush , Iyer Bala
Published: November 2005

Complex queries containing outer joins are, for the most part, executed by commercial DBMS products in an "as written" manner. Only a very few reorderings of the operations are considered and the benefits of considering comprehensive reordering schemes are not exploited. This is largely due to the fact there are no readily usable results for reordering such operations for relations with
duplicates
and/or outer join predicates that are other than "
simple.
" Most previous approaches have ignored duplicates and complex predicates; the very few that have considered these aspects have suggested approaches that lead to a possibly exponential number of, and redundant intermediate joins. Since traditional query graph models are inadequate for modeling outer join queries with complex predicates, we present the needed hypergraph abstraction and algorithms for reordering such queries with joins and outer joins. As a result, the query optimizer can explore a significantly larger space of execution plans, and choose one with a low cost. Further, these algorithms are easily incorporated into well known and widely used enumeration methods such as dynamic programming.
Fault tolerant design of multimedia servers
Authors: Berson Steven , Golubchik Leana , Muntz Richard R.
Published: November 2005

Recent technological advances have made multimedia on-demand servers feasible. Two challenging tasks in such systems are: a) satisfying the real-time requirement for continuous delivery of objects at specified bandwidths and b) efficiently servicing multiple clients simultaneously. To accomplish these tasks and realize economies of scale associated with servicing a large user population, the multimedia server can require a large disk subsystem. Although a single disk is fairly reliable, a large disk farm can have an unacceptably high probability of disk failure. Further, due to the real-time constraint, the reliability and availability requirements of multimedia systems are very stringent. In this paper we investigate techniques for providing a high degree of reliability and availability, at low disk storage, bandwidth, and memory costs for on-demand multimedia servers.
DataMine—interactive rule discovery system
Authors: Imielinski T. , Virmani A.
Published: November 2005

DataMine
is a statistical database mining system with strong emphasis on interactiveness and nice graphical representation of information produced. It also supports an offline mode of discovery, and provides an extensive API which allows users to write "mining applications" just as easily as routine database applications, The central idea is to perform discovery with a "human in the loop" guiding the system using his initial hypothesis and the feedback from the system. Users can pose a rule-query against a rulebase and the system can generate all rules matching their query. The rulebase could either be pregenerated (using offline mode) or could be realized in real-time as the discovery progresses.Rules generated by the system are of the form:
Body
->
Consequent
where Body is a conjunction of the elementary predicates of the form (A=a), where A is an attribute and a is a value from the attribute domain of A. Consequent is a single elementary predicate. Each rule can have several parameters like support, confidence, atypicality, color etc. (the definitions have been left out) which can also be used by the user in framing the rule query.For continuous attributes, the system also allows the user some control in deciding how they are discretized. It also allows for the creation of extra attributes at run time which can then be used in queries like the rest.
QBI
Authors: Massari Antonio , Pavani Stefano , Saladini Lorenzo , Chrysanthis Panos K.
Published: November 2005

QBI is an icon-based query processing and exploration facility for large distributed databases [3]. As opposed to other interactive query interfaces, it combines (1) a
pure iconic specification,
i.e., no diagrams of any form, only icon manipulation, with (2)
intensional browsing
or
metaquery
tools that assist in the formulation of complete queries without involving path specification or access to the actual data in the database.Path expressions are automatically generated by QBI and irrespective of their length, represented by a single icon, allowing for better use of the screen. It requires no special knowledge of the content of the underlying database nor understanding of the details of the database schema. Hence, QBI is domain independent and equally useful to both unsophisticated and expert users.
Pattern matching and pattern discovery in scientific, program, and document databases
Authors: Wang Jason T. L. , Zhang Kaizhong , Shasha Dennis
Published: November 2005

Over the past several years we have created or borrowed algorithms for combinatorial pattern matching and pattern discovery on sequences [2] and trees.In
matching
problems, given a pattern, a set of data objects and a distance metric, we find the distance between the pattern and one or more data objects. In
discovery
problems by contrast, given a set of objects, a metric, and a distance, we seek a pattern that matches many of those objects within the given distance. (So, discovery is a lot like data mining.) Our toolkit performs both matching and discovery with current targeted applications in molecular biology and document comparison.