bluuebunny/crossref_metadata_2025 huggingface dataset:
Concurrency and recovery in generalized search trees
Authors: Kornacker Marcel , Mohan C. , Hellerstein Joseph M.
Published: November 2005

This paper presents general algorithms for concurrency control in tree-based access methods as well as a recovery protocol and a mechanism for ensuring repeatable read. The algorithms are developed in the context of the Generalized Search Tree (GiST) data structure, an index structure supporting an extensible set of queries and data types. Although developed in a GiST context, the algorithms are generally applicable to many tree-based access methods. The concurrency control protocol is based on an extension of the link technique originally developed for B-trees, and completely avoids holding node locks during I/Os. Repeatable read isolation is achieved with a novel combination of predicate locks and two-phase locking of data records. To our knowledge, this is the first time that isolation issues have been addressed outside the context of B-trees. A discussion of the fundamental structural differences between B-trees and more general tree structures like GiSTs explains why the algorithms developed here deviate from their B-tree counterparts. An implementation of GiSTs emulating B-trees in DB2/Common Server is underway.
Dynamic itemset counting and implication rules for market basket data
Authors: Brin Sergey , Motwani Rajeev , Ullman Jeffrey D. , Tsur Shalom
Published: November 2005

We consider the problem of analyzing market-basket data and present several important contributions. First, we present a new algorithm for finding large itemsets which uses fewer passes over the data than classic algorithms, and yet uses fewer candidate itemsets than methods based on sampling. We investigate the idea of item reordering, which can improve the low-level efficiency of the algorithm. Second, we present a new way of generating “implication rules,” which are normalized based on both the antecedent and the consequent and are truly implications (not simply a measure of co-occurrence), and we show how they produce more intuitive results than other methods. Finally, we show how different characteristics of real data, as opposed by synthetic data, can dramatically affect the performance of the system and the form of the results.
Infomaster
Authors: Genesereth Michael R. , Keller Arthur M. , Duschka Oliver M.
Published: November 2005

Infomaster is an information integration system that provides integrated access to multiple distributed heterogeneous information sources on the Internet, thus giving the illusion of a centralized, homogeneous information system. We say that Infomaster creates a virtual data warehouse. The core of Infomaster is a facilitator that dynamically determines an efficient way to answer the user's query using as few sources as necessary and harmonizes the heterogeneities among these sources. Infomaster handles both structural and content translation to resolve differences between multiple data sources and the multiple applications for the collected data. Infomaster connects to a variety of databases using wrappers, such as for Z39.50, SQL databases through ODBC, EDI transactions, and other World Wide Web (WWW) sources. There are several WWW user interfaces to Infomaster, including forms based and textual. Infomaster also includes a programmatic interface and it can download results in structured form onto a client computer. Infomaster has been in production use for integrating rental housing advertisements from several newspapers (since fall 1995), and for meeting room scheduling (since winter 1996). Infomaster is also being used to integrate heterogeneous electronic product catalogs.
Asserting beliefs in MLS relational models
Authors: Jukic Nenad A. , Vrbsky Susan V.
Published: November 2005

Multilevel relations, based on the current multilevel secure (MLS) relational data models, can present a user with information that is difficult to interpret and may display an inconsistent outlook about the views of other users. Such ambiguity is due to the lack of a comprehensive method for asserting and interpreting beliefs about lower level information. In this paper we identify different beliefs that can be held by higher level users about lower level information, and we introduce the new concept of a mirage tuple. We present a mechanism for asserting beliefs about all accessible tuples, including lower level tuples. This mechanism provides every user of an MLS database with an unambiguous interpretation of all viewable information and presents a consistent account of the views at all levels below the user's level.
Research outline on extension mathematics
Authors: He Bin , Chen Jun
Published: November 2005

Based on analysis of the difficult situation for modern mathematical development and that of the current development situation about matter element theory and extension set theory, a primary research outline on extension mathematics is put forward in this paper.
Pipelining and superscalar processors
Authors: Styer Eugene
Published: November 2005

I will start this eighth segment with a small oops - I said I would discuss protected mode, but I had already looked at that in April 1996 (part five). But there are some other items, such as superscalar and the recently released MMX extensions that are worthy of discussion.
Wrapper generation for semi-structured Internet sources
Authors: Ashish Naveen , Knoblock Craig A.
Published: November 2005

With the current explosion of information on the World Wide Web (WWW) a wealth of information on many different subjects has become available on-line. Numerous sources contain information that can be classified as semi-structured. At present, however, the only way to access the information is by browsing individual pages. We cannot query web documents in a database-like fashion based on their underlying structure. However, we can provide database-like querying for semi-structured WWW sources by building wrappers around these sources. We present an approach for semi-automatically generating such wrappers. The key idea is to exploit the formatting information in pages from the source to hypothesize the underlying structure of a page. From this structure the system generates a wrapper that facilitates querying of a source and possibly integrating it with other sources. We demonstrate the ease with which we are able to build wrappers for a number of internet sources in different domains using our implemented wrapper generation toolkit.
Inferring structure in semistructured data
Authors: Nestorov Svetlozer , Abiteboul Serge , Motwani Rajeev
Published: November 2005

When dealing with semistructured data such as that available on the Web, it becomes important to infer the inherent structure, both for the user (e.g., to facilitate querying) and for the system (e.g., to optimize access). In this paper, we consider the problem of identifying some underlying structure in large collections of semistructured data. Since we expect the data to be fairly irregular, this structure consists of an approximate classification of objects into a hierarchical collection of types. We propose a notion of a type hierarchy for such data, and outline a method for deriving the type hierarchy, and rules for assigning types to data elements.
Workshop report on experiences using object data management in the real-world
Authors: Chaudhri Akmal B.
Published: November 2005

The OOPSLA '97 Workshop on
Experiences Using Object Data Management in the Real-World
was held at the Cobb Galleria Centre in Atlanta, Georgia on Monday 6 October 1997. This report summarises some of the commercial case-study presentations made by workshop participants.
Materialized views and data warehouses
Authors: Roussopoulos Nick
Published: November 2005

A data warehouse is a redundant collection of data replicated from several possibly distributed and loosely coupled source databases, organized to answer OLAP queries. Relational views are used both as a specification technique and as an execution plan for the derivation of the warehouse data. In this position paper, we summarize the versatility of relational views and their potential.
Unbundling active functionality
Authors: Gatziu Stella , Koschel Arne , von Bültzingsloewen Günter , Fritschi Hans
Published: November 2005

New application areas or new technical innovations expect from database management systems more and more new functionality. However, adding functions to the DBMS as an integral part of them, tends to create monoliths that are difficult to design, implement, validate, maintain and adapt. Such monoliths can be avoided if one configures DBMS according to the actually needed functionality. In order to identify the basic functional components for the configuration the current monoliths should be broken up into smaller units, or in other words they could be "unbundled". In this paper we apply unbundling to active database systems. This results in a new form of active mechanisms where active functionality is no longer an integral part of the DBMS functionality. This allows the use of active capabilities with any arbitrary DBMS and in broader contexts. Furthermore, it allows the adaption of the active functionality to the application profile. Such aspects are crucial for a wide use of active functionality in real (database or not) applications.
Efficiently mining long patterns from databases
Authors: Bayardo Roberto J.
Published: November 2005

We present a pattern-mining algorithm that scales roughly linearly in the number of maximal patterns embedded in a database irrespective of the length of the longest pattern. In comparison, previous algorithms based on Apriori scale exponentially with longest pattern length. Experiments on real data show that when the patterns are long, our algorithm is more efficient by an order of magnitude or more.
Incremental distance join algorithms for spatial databases
Authors: Hjaltason Gísli R. , Samet Hanan
Published: November 2005

Two new spatial join operations,
distance join
and
distance semi-join
, are introduced where the join output is ordered by the distance between the spatial attribute values of the joined tuples. Incremental algorithms are presented for computing these operations, which can be used in a pipelined fashion, thereby obviating the need to wait for their completion when only a few tuples are needed. The algorithms can be used with a large class of hierarchical spatial data structures and arbitrary spatial data types in any dimensions. In addition, any distance metric may be employed. A performance study using R-trees shows that the incremental algorithms outperform non-incremental approaches by an order of magnitude if only a small part of the result is needed, while the penalty, if any, for the incremental processing is modest if the entire join result is required.
NoDoSE—a tool for semi-automatically extracting structured and semistructured data from text documents
Authors: Adelberg Brad
Published: November 2005

Often interesting structured or semistructured data is not in database systems but in HTML pages, text files, or on paper. The data in these formats is not usable by standard query processing engines and hence users need a way of extracting data from these sources into a DBMS or of writing wrappers around the sources. This paper describes NoDoSE, the Northwestern Document Structure Extractor, which is an interactive tool for semi-automatically determining the structure of such documents and then extracting their data. Using a GUI, the user hierarchically decomposes the file, outlining its interesting regions and then describing their semantics. This task is expedited by a mining component that attempts to infer the grammar of the file from the information the user has input so far. Once the format of a document has been determined, its data can be extracted into a number of useful forms. This paper describes both the NoDoSE architecture, which can be used as a test bed for structure mining algorithms in general, and the mining algorithms that have been developed by the author. The prototype, which is written in Java, is described and experiences parsing a variety of documents are reported.
A case for intelligent disks (IDISKs)
Authors: Keeton Kimberly , Patterson David A. , Hellerstein Joseph M.
Published: November 2005

Decision support systems (DSS) and data warehousing workloads comprise an increasing fraction of the database market today. I/O capacity and associated processing requirements for DSS workloads are increasing at a rapid rate, doubling roughly every nine to twelve months [38]. In response to this increasing storage and computational demand, we present a computer architecture for decision support database servers that utilizes “intelligent” disks (IDISKs). IDISKs utilize low-cost embedded general-purpose processing, main memory, and high-speed serial communication links on each disk. IDISKs are connected to each other via these serial links and high-speed crossbar switches, overcoming the I/O bus bottleneck of conventional systems. By off-loading computation from expensive desktop processors, IDISK systems may improve cost-performance. More importantly, the IDISK architecture allows the processing of the system to scale with increasing storage demand.
Integration of spatial join algorithms for processing multiple inputs
Authors: Mamoulis Nikos , Papadias Dimitris
Published: November 2005

Several techniques that compute the join between two spatial datasets have been proposed during the last decade. Among these methods, some consider existing indices for the joined inputs, while others treat datasets with no index, providing solutions for the case where at least one input comes as an intermediate result of another database operator. In this paper we analyze previous work on spatial joins and propose a novel algorithm, called
slot index spatial join
(SISJ), that efficiently computes the spatial join between two inputs, only one of which is indexed by an R-tree. Going one step further, we show how SISJ and other spatial join algorithms can be implemented as operators in a database environment that joins more than two spatial datasets. We study the differences between relational and spatial multiway joins, and propose a dynamic programming algorithm that optimizes the execution of complex spatial queries.
Selectivity estimation in spatial databases
Authors: Acharya Swarup , Poosala Viswanath , Ramaswamy Sridhar
Published: November 2005

Selectivity estimation of queries is an important and well-studied problem in relational database systems. In this paper, we examine selectivity estimation in the context of Geographic Information Systems, which manage spatial data such as points, lines, poly-lines and polygons. In particular, we focus on point and range queries over two-dimensional rectangular data. We propose several techniques based on using spatial indices, histograms, binary space partitionings (BSPs), and the novel notion of spatial skew. Our techniques carefully partition the input rectangles into subsets and approximate each partition accurately. We present a detailed experimental study comparing the proposed techniques and the best known sampling and parametric techniques. We evaluate them using synthetic as well as real-life TIGER datasets. Based on our experiments, we identify a BSP based partitioning that we call
Min-Skew
which consistently provides the most accurate selectivity estimates for spatial queries. The Min-Skew partitioning can be constructed efficiently, occupies very little space, and provides accurate selectivity estimates over a broad range of spatial queries.
OPTICS
Authors: Ankerst Mihael , Breunig Markus M. , Kriegel Hans-Peter , Sander Jörg
Published: November 2005

Cluster analysis is a primary method for database mining. It is either used as a stand-alone tool to get insight into the distribution of a data set, e.g. to focus further analysis and data processing, or as a preprocessing step for other algorithms operating on the detected clusters. Almost all of the well-known clustering algorithms require input parameters which are hard to determine but have a significant influence on the clustering result. Furthermore, for many real-data sets there does not even exist a global parameter setting for which the result of the clustering algorithm describes the intrinsic clustering structure accurately. We introduce a new algorithm for the purpose of cluster analysis which does
not
produce a clustering of a data set explicitly; but instead creates an augmented
ordering
of the database representing its density-based clustering structure. This cluster-ordering contains information which is equivalent to the density-based clusterings corresponding to a broad range of parameter settings. It is a versatile basis for both automatic and interactive cluster analysis. We show how to automatically and efficiently extract not only 'traditional' clustering information (e.g. representative points, arbitrary shaped clusters), but also the intrinsic clustering structure. For medium sized data sets, the cluster-ordering can be represented graphically and for very large data sets, we introduce an appropriate visualization technique. Both are suitable for interactive exploration of the intrinsic clustering structure offering additional insights into the distribution and correlation of the data.
A multimedia presentation algebra
Authors: Adali S. , Sapino M. L. , Subrahmanian V. S.
Published: November 2005

Over the last few years, there has been a tremendous increase in the number of interactive multimedia presentations prepared by different individuals and organizations. In this paper, we present an algebra for querying multimedia presentation databases. In contrast to the relational algebra, an algebra for interactive multimedia presentations must operate on trees whose branches reflect different possible playouts of a family of presentations. The query language supports selection type operations for locating objects and presentation paths that are of interest to the user, join type operations for combining presentations from multiple databases into a single presentation, and finally set theoretic operations for comparing different databases. The algebra operations can be used to locate presentations with specific properties and also for creating new presentations by borrowing different components from existing ones. We prove a host of equivalence results for queries in this algebra which may be used to build query optimizers for interactive presentation databases.
Online association rule mining
Authors: Hidber Christian
Published: November 2005

We present a novel algorithm to compute large itemsets online. The user is free to change the support threshold any time during the first scan of the transaction sequence. The algorithm maintains a superset of all large itemsets and for each itemset a shrinking, deterministic interval on its support. After at most 2 scans the algorithm terminates with the precise support for each large itemset. Typically our algorithm is by an order of magnitude more memory efficient than Apriori or DIC.
Optimization of constrained frequent set queries with 2-variable constraints
Authors: Lakshmanan Laks V. S. , Ng Raymond , Han Jiawei , Pang Alex
Published: November 2005

Currently, there is tremendous interest in providing ad-hoc mining capabilities in database management systems. As a first step towards this goal, in [15] we proposed an architecture for supporting constraint-based, human-centered, exploratory mining of various kinds of rules including associations, introduced the notion of constrained frequent set queries (CFQs), and developed effective pruning optimizations for CFQs with 1-variable (1-var) constraints.

While 1-var constraints are useful for constraining the antecedent and consequent separately, many natural examples of CFQs illustrate the need for constraining the antecedent and consequent jointly, for which 2-variable (2-var) constraints are indispensable. Developing pruning optimizations for CFQs with 2-var constraints is the subject of this paper. But this is a difficult problem because: (i) in 2-var constraints, both variables keep changing and, unlike 1-var constraints, there is no fixed target for pruning; (ii) as we show, “conventional” monotonicity-based optimization techniques do not apply effectively to 2-var constraints.

The contributions are as follows. (1) We introduce a notion of
quasi-succinctness
, which allows a quasi-succinct 2-var constraint to be reduced to two succinct 1-var constraints for pruning. (2) We characterize the class of 2-var constraints that are quasi-succinct. (3) We develop heuristic techniques for non-quasi-succinct constraints. Experimental results show the effectiveness of all our techniques. (4) We propose a query optimizer for CFQs and show that for a large class of constraints, the computation strategy generated by the optimizer is
ccc-optimal
, i.e., minimizing the effort incurred w.r.t. constraint checking and support counting.
BOAT—optimistic decision tree construction
Authors: Gehrke Johannes , Ganti Venkatesh , Ramakrishnan Raghu , Loh Wei-Yin
Published: November 2005

Classification is an important data mining problem. Given a training database of records, each tagged with a class label, the goal of classification is to build a concise model that can be used to predict the class label of future, unlabeled records. A very popular class of classifiers are decision trees. All current algorithms to construct decision trees, including all main-memory algorithms, make one scan over the training database per level of the tree.

We introduce a new algorithm (BOAT) for decision tree construction that improves upon earlier algorithms in both performance and functionality. BOAT constructs several levels of the tree in only two scans over the training database, resulting in an average performance gain of 300% over previous work. The key to this performance improvement is a novel
optimistic
approach to tree construction in which we construct an initial tree using a small subset of the data and refine it to arrive at the final tree. We guarantee that any difference with respect to the “real” tree (i.e., the tree that would be constructed by examining all the data in a traditional way) is detected and corrected. The correction step occasionally requires us to make additional scans over subsets of the data; typically, this situation rarely arises, and can be addressed with little added cost.

Beyond offering faster tree construction, BOAT is the first scalable algorithm with the ability to incrementally update the tree with respect to both insertions and deletions over the dataset. This property is valuable in dynamic environments such as data warehouses, in which the training dataset changes over time. The BOAT update operation is much cheaper than completely rebuilding the tree, and the resulting tree is guaranteed to be identical to the tree that would be produced by a complete re-build.
Approximate computation of multidimensional aggregates of sparse data using wavelets
Authors: Vitter Jeffrey Scott , Wang Min
Published: November 2005

Computing multidimensional aggregates in high dimensions is a performance bottleneck for many OLAP applications. Obtaining the exact answer to an aggregation query can be prohibitively expensive in terms of time and/or storage space in a data warehouse environment. It is advantageous to have fast, approximate answers to OLAP aggregation queries.

In this paper, we present a novel method that provides approximate answers to high-dimensional OLAP aggregation queries in massive sparse data sets in a time-efficient and space-efficient manner. We construct a
compact data cube
, which is an approximate and space-efficient representation of the underlying multidimensional array, based upon a multiresolution wavelet decomposition. In the on-line phase, each aggregation query can generally be answered using the compact data cube in one I/O or a smalll number of I/Os, depending upon the desired accuracy.

We present two I/O-efficient algorithms to construct the compact data cube for the important case of
sparse high-dimensional arrays
, which often arise in practice. The traditional histogram methods are infeasible for the massive high-dimensional data sets in OLAP applications. Previously developed wavelet techniques are efficient only for dense data. Our on-line query processing algorithm is very fast and capable of refining answers as the user demands more accuracy. Experiments on real data show that our method provides significantly more accurate results for typical OLAP aggregation queries than other efficient approximation techniques such as random sampling.
Query optimization for selections using bitmaps
Authors: Wu Ming-Chuan
Published: November 2005

Bitmaps are popular indexes for data warehouse (DW) applications and most database management systems offer them today. This paper proposes query optimization strategies for selections using bitmaps. Both
continuous
and
discrete
selection criteria are considered. Query optimization strategies are categorized into static and dynamic. Static optimization strategies discussed are the optimal design of bitmaps, and algorithms based on tree and logical reduction. The dynamic optimization discussed is the approach of inclusion and exclusion for both bit-sliced indexes and encoded bitmap indexes.
Join synopses for approximate query answering
Authors: Acharya Swarup , Gibbons Phillip B. , Poosala Viswanath , Ramaswamy Sridhar
Published: November 2005

In large data warehousing environments, it is often advantageous to provide fast, approximate answers to complex aggregate queries based on statistical summaries of the full data. In this paper, we demonstrate the difficulty of providing good approximate answers for join-queries using only statistics (in particular, samples) from the base relations. We propose
join synopses
as an effective solution for this problem and show how precomputing just
one join synopsis
for each relation suffices to significantly improve the quality of approximate answers for arbitrary queries with foreign key joins. We present optimal strategies for allocating the available space among the various join synopses when the query work load is known and identify heuristics for the common case when the work load is not known. We also present efficient algorithms for incrementally maintaining join synopses in the presence of updates to the base relations. Our extensive set of experiments on the TPC-D benchmark database show the effectiveness of join synopses and various other techniques proposed in this paper.
Query processing techniques for arrays
Authors: Marathe Arunprasad P. , Salem Kenneth
Published: November 2005

Arrays are an appropriate data model for images, gridded output from computational models, and other types of data. This paper describes an approach to array query processing. Queries are expressed in AML, a logical algebra that is easily extended with user-defined functions to support a wide variety of array operations. For example, compression, filtering, and algebraic operations on images can be described. We show how AML expressions involving such operations can be treated declaratively and subjected to useful rewrite optimizations. We also describe a plan generator that produces efficient iterator-based plans from rewritten AML expressions.
Mind your vocabulary
Authors: Chang Chen-Chuan K. , García-Molina Héctor
Published: November 2005

In this paper we present a mechanism for translating
constraint queries
,
i.e.
, Boolean expressions of constraints, across heterogeneous information sources. Integrating such systems is difficult in part because they use a wide range of constraints as the vocabulary for formulating queries. We describe algorithms that apply user-provided mapping rules to translate query constraints into ones that are understood and supported in another context,
e.g.
, that use the proper operators and value formats. We show that the translated queries
minimally
subsume the original ones. Furthermore, the translated queries are also the most compact possible. Unlike other query mapping work, we effectively consider inter-dependencies among constraints,
i.e.
, we handle constraints that cannot be translated independently. Furthermore, when constraints are not fully supported, our framework explores relaxations (semantic rewritings) into the closest supported version. Our most sophisticated algorithm (Algorithm
TDQM
) does not blindly convert queries to DNF (which would be easier to translate, but expensive); instead it performs a top-down mapping of a query tree, and does local query structure conversion only when necessary.
Bottom-up computation of sparse and Iceberg CUBE
Authors: Beyer Kevin , Ramakrishnan Raghu
Published: November 2005

We introduce the Iceberg-CUBE problem as a reformulation of the datacube (CUBE) problem. The Iceberg-CUBE problem is to compute only those group-by partitions with an aggregate value (e.g., count) above some minimum support threshold. The result of Iceberg-CUBE can be used (1) to answer group-by queries with a clause such as HAVING COUNT(*) >= X, where X is greater than the threshold, (2) for mining multidimensional association rules, and (3) to complement existing strategies for identifying interesting subsets of the CUBE for precomputation.

We present a new algorithm (BUC) for Iceberg-CUBE computation. BUC builds the CUBE bottom-up; i.e., it builds the CUBE by starting from a group-by on a single attribute, then a group-by on a pair of attributes, then a group-by on three attributes, and so on. This is the opposite of all techniques proposed earlier for computing the CUBE, and has an important practical advantage: BUC avoids computing the larger group-bys that do not meet minimum support. The pruning in BUC is similar to the pruning in the Apriori algorithm for association rules, except that BUC trades some pruning for locality of reference and reduced memory requirements. BUC uses the same pruning strategy when computing sparse, complete CUBEs.

We present a thorough performance evaluation over a broad range of workloads. Our evaluation demonstrates that (in contrast to earlier assumptions) minimizing the aggregations or the number of sorts is not the most important aspect of the sparse CUBE problem. The pruning in BUC, combined with an efficient sort method, enables BUC to outperform all previous algorithms for sparse CUBEs, even for computing entire CUBEs, and to dramatically improve Iceberg-CUBE computation.
A new method for similarity indexing of market basket data
Authors: Aggarwal Charu C. , Wolf Joel L. , Yu Philip S.
Published: November 2005

In recent years, many data mining methods have been proposed for finding useful and structured information from market basket data. The association rule model was recently proposed in order to discover useful patterns and dependencies in such data. This paper discusses a method for indexing market basket data efficiently for similarity search. The technique is likely to be very useful in applications which utilize the similarity in customer buying behavior in order to make peer recommendations. We propose an index called the
signature table
, which is very flexible in supporting a wide range of similarity functions. The construction of the index structure is independent of the similarity function, which can be specified at query time. The resulting similarity search algorithm shows excellent scalability with increasing memory availability and database size.
Automatic discovery of language models for text databases
Authors: Callan Jamie , Connell Margaret , Du Aiqun
Published: November 2005

The proliferation of text databases within large organizations and on the Internet makes it difficult for a person to know which databases to search. Given
language models
that describe the contents of each database, a
database selection
algorithm such as GIOSS can provide assistance by automatically selecting appropriate databases for an information need. Current practice is that each database provides its language model upon request, but this
cooperative
approach has important limitations.

This paper demonstrates that cooperation is not required. Instead, the database selection service can construct its own language models by sampling database contents via the normal process of running queries and retrieving documents. Although random sampling is not possible, it can be approximated with carefully selected queries. This
sampling
approach avoids the limitations that characterize the cooperative approach, and also enables additional capabilities. Experimental results demonstrate that accurate language models can be learned from a relatively small number of queries and documents.
A layered architecture for querying dynamic Web content
Authors: Davulcu Hasan , Freire Juliana , Kifer Michael , Ramakrishnan I. V.
Published: November 2005

The design of
webbases
, database systems for supporting Web-based applications, is currently an active area of research. In this paper, we propose a 3-year architecture for designing and implementing webbases for querying dynamic Web content(i.e., data that can only be extracted by filling out multiple forms). The lowest layer,
virtual physical layer
, provides
navigation independence
by shielding the user from the complexities associated with retrieving data from raw Web sources. Next, the traditional
logical layer
supports
site independence
. The top layer is analogous to the
external schema layer
in traditional databases.

Within this architectural framework we address two problems unique to webbases — retrieving dynamic Web content in the virtual physical layer and querying of the external schema by the end user. The layered architecture makes it possible to automate data extraction to a much greater degree than in existing proposals. Wrappers for the virtual physical schema can be created semi-automatically, by asking the webbase designer to navigate through the sites of interest — we call this approach
mapping by example.
Thus, the webbase designer need not have expertise in the language that maps the physical schema to the raw Web (this should be contrasted to other approaches, which require expertise in various Web-enabled flavors of SQL). For the external schema layer, we propose a semantic extension of the universal relation interface. This interface provides powerful, yet reasonably simple, ad hoc querying capabilities for the end user compared to the currently prevailing “canned” form-based interfaces on the one hand or complex Web-enabling extensions of SQL on the other. Finally, we discuss the implementation of the proposed architecture.
“Honey, I shrunk the database”
Authors: Seshadri Praveen
Published: November 2005

The small-scale mobile computing market (palmtops, handhelds, smartphones, smartcards, etc.) is showing the most explosive growth in the history of computing. Within the last year, most database vendors have announced plans to build “small footprint” versions of their DBMS products to run on these small and mobile platforms. What are the real database systems issues? What are the likely markets? What are the challenges, and the dangers? Every specific vendor seems to have a different answer to these questions. They all agree on only one thing: there is a tremendous opportunity here. Our motivation for this panel is to get a number of the central decision-makers into a room and debate the issues.
Of crawlers, portals, mice, and men
Authors: Garofalakis Minos N. , Ramaswamy Sridhar , Rastogi Rajeev , Shim Kyuseok
Published: November 2005

The World Wide Web is rapidly emerging as an important medium for transacting commerce as well as for the dissemination of information related to a wide range of topics (e.g., business, government, recreation). According to most predictions, the majority of human information will be available on the Web in ten years. These huge amounts of data raise a grand challenge for the database community, namely, how to turn the Web into a more useful information utility. This is exactly the subject that will be addressed by this panel.
O-O, what's happening to DB2?
Authors: Carey M. , Chamberlin D. , Doole D. , Rielau S. , Mattos N. , Narayanan S. , Vance B. , Swagerman R.
Published: November 2005

In this presentation, we will describe a collection of new object-relational features that have been added to IBM's DB2 Universal Database (UDB) system. The features to be described include support for structured types, object references, and hierarchies of typed tables and views. These features will be covered from the perspective of a database designer or end user. In addition to presenting the features presently available in DB2 UDB V5.2, which became available in Fall 1998, we will discuss the expected evolution and impact of this technology over time.
Bringing object-relational technology to the mainstream
Authors: Krishnamurthy Vishu , Banerjee Sandeepan , Nori Anil
Published: November 2005

Over the last few years, Oracle has evolved its flagship relational database system into an Object-Relational system by adding an extensible type system, object storage, an object cache, an extensible query and indexing framework, support for multimedia datatypes, a server-based scalable Java virtual machine, as well as enhancing its SQL DDL and DML language. These extensions were done with the practical goal of bringing objects to mainstream use.
Implementing the spirit of SQL-99
Authors: Brown Paul
Published: November 2005

This paper describes the current INFORMIX IDS/UD release (9.2 or Centaur) and compares and contrasts its functionality with the features of the SQL-99 language standard. INFORMIX and Illustra have been shipping DBMSs implementing the spirit of the SQL-99 standard for five years. In this paper, we review our experience working with ORDBMS technology, and argue that while SQL-99 is a huge improvement over SQL-92, substantial further work is necessary to make object-relational DBMSs truly useful. Specifically, we describe several interesting pieces of functionality unique to IDS/UD, and several dilemmas our customers have encountered that the standard does not address.
EMC information sharing
Authors: Kohler Walt
Published: November 2005

In this extended abstract we briefly describe EMC's information sharing technology that enables UNIX and NT systems to directly access MVS mainframe datasets and how this technology can be used to directly access an MVS DB2 database.
Daytona and the fourth-generation language Cymbal
Authors: Greer Rick
Published: November 2005

The Daytona™ data management system is used by AT&T to solve a wide spectrum of data management problems. For example, Daytona is managing a 4 terabyte data warehouse whose largest table contains over 10 billion rows. Daytona's architecture is based on translating its high-level query language Cymbal (which includes SQL as a subset) completely into C and then compiling that C into object code. The system resulting from this architecture is fast, powerful, easy to use and administer, reliable and open to UNIX™ tools. In particular, two forms of data compression plus robust horizontal partitioning enable Daytona to handle terabytes with ease.
Merge replication in Microsoft's SQL server 7.0
Authors: Hammond Brad
Published: November 2005

SQL Server 7.0 offers three different styles of replication that we call Transactional Replication, Snapshot Replication, and Merge Replication. Merge Replication means that data changes can be performed at any replica, and that the changes performed at multiple replicas are later merged together. Because Merge Replication allows updates to disconnected replicas, it is particularly well suited to applications that require a lot of autonomy. A special process called the Merge Agent propagates changes between replicas, filters data as appropriate, and detects and handles conflicts according to user-specified rules.
Versions and workspaces in Microsoft repository
Authors: Bergstraesser Thomas , Bernstein Philip A. , Pal Shankar , Shutt David
Published: November 2005

This paper describes the version and workspace features of Microsoft Repository, a layer that implements fine-grained objects and relationships on top of Microsoft SQL Server. It supports branching and merging of versions, delta storage, checkout-checkin, and single-version views for version-unaware applications.
Nodose version 2.0
Authors: Adelberg Brad , Denny Matthew
Published: November 2005

This paper describes a tool, called Nodose, we have developed to expedite the creation of robust wrappers. Nodose allows non-programmers to build components that can convert data from the source format to XML or another generic format. Further, the generated code performs a set of statistical checks at runtime that attempt to find extraction errors before they are propogated back to users.
SERF
Authors: Rundensteiner E. A. , Claypool K. , Li M. , Chen L. , Zhang Z. , Natarajan C. , Jin J. , De Lima S. , Weiner S.
Published: November 2005

The age of information management and with it the advent of increasingly sophisticated technologies have kindled a need in the database community and others to
re-structure
existing systems and move forward to make use of these new technologies. Legacy application systems are being transformed to newer state-of-the-art systems, information sources are being mapped from one data model to another, a diversity of data sources are being transformed to load, cleanse and consolidate data into modern data-warehouses [CR99].

Re-structuring is thus a critical task for a variety of applications. For this reason, most object-oriented database systems (OODB) today support some form of re-structuring support [Tec94, Obj93, BKKK87]. This existing support of current OODBs [BKKK87, Tec94, Obj93] is limited to a
pre-defined
taxonomy of
simple fixed-semantic
schema evolution operations. However, such simple changes, typically to individual types only, are not sufficient for many advanced applications [Bré96]. More radical changes, such as combining two types of redefining the relationship between two types, are either very difficult or even impossible to achieve with current commercial database technology [Tec94, Obj93]. In fact, most OODBs would typically require the user to write ad-hoc programs to accomplish such transformations. Research that has begun to look into the issue of complex changes [Bré96, Ler96] is still limited by providing a
fixed
set of some selected (even if now more complex) operations.

To address these limitations of the
current
restructuring technology, we have proposed the SERF framework which aims at providing a rich environment for doing complex user-defined transformations
flexibly
,
easily
and
correctly
[CJR98b]. The goal of our work is to increase the usability and utility of the SERF framework and its applicability to re-structuring problems beyond OODB evolution. Towards that end, we provide
re-usable
transformations via the notion of SERF Templates that can be packaged into libraries, thereby increasing the
portability
of these transformations. We also now have a first cut at providing an assurance of consistency for the users of this system, a semantic optimizer that provides some performance improvements via enhanced query optimization techniques with emphasis on the re-structuring primitives [CNR99]. In this demo we give an overview of the SERF framework, its current status and the enhancements that are planned for the future. We also present an example of the application of SERF to a domain other than schema evolution, i.e., the web restructuring.
The Aqua approximate query answering system
Authors: Acharya Swarup , Gibbons Phillip B. , Poosala Viswanath , Ramaswamy Sridhar
Published: November 2005

Aqua is a system for providing fast, approximate answers to aggregate queries, which are very common in OLAP applications. It has been designed to run on top of any commercial relational DBMS. Aqua precomputes
synopses
(special statistical summaries) of the original data and stores them in the DBMS. It provides approximate answers along with quality guarantees by rewriting the queries to run on these synopses. Finally, Aqua keeps the synopses up-to-date as the database changes, using fast incremental maintenance techniques.
The Cornell Jaguar project
Authors: Bonnet Phillippe , Buza Kyle , Chan Zhiyuan , Cheng Victor , Chung Randolph , Hickey Takako , Kennedy Ryan , Mahashin Daniel , Mayr Tobias , Oprencak Ivan , Seshadri Praveen , Siu Hubert
Published: November 2005

The Cornell Jaguar Project is exploring a variety of issues related to mobility and query processing. One broad theme is to break down the traditional client and server boundaries, leading to ubiquitous query processing. Another theme is to extend database and query processing techniques to small-scale and mobile devices. The project builds on and extends the Cornell PREDATOR database engine.
A user-centered interface for querying distributed multimedia databases
Authors: Cruz Isabel F. , James Kimberly M.
Published: November 2005

Facilitating information retrieval in the vastly growing realm of digital media has become increasingly difficult. Delaunay
MM
seeks to assist all users in finding relevant information through an interactive interface that supports pre- and post-query refinement, and a customizable multimedia information display. This project leverages the strengths of visual query languages with a resourceful framework to provide users with a single intuitive interface. The interface and its supporting framework are described in this paper.
Electronic market
Authors: Christoffel Michael , Pulkowski Sebastian , Schmitt Bethina , Lockemann Peter C.
Published: November 2005

This contribution argues that electronic markets can serve as a powerful mechanism to entice providers to identify their customer base and to offer customer-oriented, high-quality and economical services and to induce customers to a more focused and price-conscious behavior. The paper claims that this should be particularly true for the provision and access to scientific literature where the tradition so far has been mostly free access by customers and non-transparent cost accounting and service procurement by university libraries. We report on a project for developing a technical network infrastructure that allows for a more cost-transparent access to scientific literature by campus users and attempts to add a competitive element to library services. Equally important, it provides added value to the users so that they can orient themselves in the vast expanses of scientific literature much faster and more economically. We cover three major elements of the infrastructure: user agents, traders and source wrappers.
The Asilomar report on database research
Authors: Bernstein Phil , Brodie Michael , Ceri Stefano , DeWitt David , Franklin Mike , Garcia-Molina Hector , Gray Jim , Held Jerry , Hellerstein Joe , Jagadish H. V. , Lesk Michael , Maier Dave , Naughton Jeff , Pirahesh Hamid , Stonebraker Mike , Ullman Jeff
Published: November 2005

The database research community is rightly proud of success in basic research, and its remarkable record of technology transfer. Now the field needs to radically broaden its research focus to attack the issues of capturing, storing, analyzing, and presenting the vast array of online data. The database research community should embrace a broader research agenda — broadening the definition of database management to embrace all the content of the Web and other online data stores, and rethinking our fundamental assumptions in light of technology shifts. To accelerate this transition, we recommend changing the way research results are evaluated and presented. In particular, we advocate encouraging more speculative and long-range work, moving conferences to a poster format, and publishing all research literature on the Web.
Efficient materialization and use of views in data warehouses
Authors: Farias de Souza Márcio , Sampaio Marcus Costa
Published: November 2005

Given the complexity of many queries over a Data Warehouse (DW), it is interesting to precompute and store in the DW the answer sets of some demanding operations, so called materialized views. In this paper, we present an algorithm, including its experimental evaluation, which allows the materialization of several views simultaneously without losing sight of processing costs for queries using these materialized views.