bluuebunny/crossref_metadata_2025 huggingface dataset:
Logical logging to extend recovery to new domains
Authors: Lomet David , Tuttle Mark
Published: November 2005

Recovery can be extended to new domains at reduced logging cost by exploiting “logical” log operations. During recovery, a logical log operation may read data values from any recoverable object, not solely from values on the log or from the updated object. Hence, we needn't log these values, a substantial saving. In [8], we developed a redo recovery theory that deals with general log operations and proved that the stable database remains recoverable when it is explained in terms of an installation graph. This graph was used to derived a write graph that determines a flush order for cached objects that ensures that the database remains recoverable. In this paper, we introduce a refined write graph that permits more flexible cache management that flushes smaller sets of objects. Using this write graph, we show how: (i) the cache manager can inject its own operations to break up atomic flush sets; and (ii) the recovery process can avoid redoing operations whose effects aren't needed by exploiting generalized recovery LSNs. These advances permit more cost-effective recovery for, e.g., files and applications.
Efficient concurrency control for broadcast environments
Authors: Shanmugasundaram Jayavel , Nithrakashyap Arvind , Sivasankaran Rajendran , Ramamritham Krithi
Published: November 2005

A crucial consideration in environments where data is broadcast to clients is the low bandwidth available for clients to communicate with servers. Advanced applications in such environments do need to read data that is mutually consistent as well as current. However, given the asymmetric communication capabilities and the needs of clients in mobile environments, traditional serializability-based approaches are too restrictive, unnecessary, and impractical. We thus propose the use of a weaker correctness criterion called
update consistency
and outline mechanisms based on this criterion that ensure (1) the
mutual consistency
of data maintained by the server and read by clients, and (2) the
currency
of data read by clients. Using these mechanisms, clients can obtain data that is current and mutually consistent “off the air”, i.e., without contacting the server to, say, obtain locks. Experimental results show a substantial reduction in response times as compared to existing (serializability-based) approaches. A further attractive feature of the approach is that if caching is possible at a client, weaker forms of currency can be obtained while still satisfying the mutual consistency of data.
Update propagation protocols for replicated databates
Authors: Breitbart Yuri , Komondoor Raghavan , Rastogi Rajeev , Seshadri S. , Silberschatz Avi
Published: November 2005

Replication is often used in many distributed systems to provide a higher level of performance, reliability and availability. Lazy replica update protocols, which propagate updates to replicas through independent transactions after the original transaction commits, have become popular with database vendors due to their superior performance characteristics. However, if lazy protocols are used indiscriminately, they can result in non-serializable executions. In this paper, we propose two new lazy update protocols that guarantee serializability but impose a much weaker requirement on data placement than earlier protocols. Further, many naturally occurring distributed systems, like distributed data warehouses, satisfy this requirement. We also extend our lazy update protocols to eliminate all requirements on data placement. The extension is a hybrid protocol that propagates as many updates as possible in a lazy fashion. We implemented our protocols on the Datablitz database system product developed at Bell Labs. We also conducted an extensive performance study which shows that our protocols outperform existing protocols over a wide range of workloads.
Belief reasoning in MLS deductive databases
Authors: Jamil Hasan M.
Published: November 2005

It is envisaged that the application of the multilevel security (MLS) scheme will enhance flexibility and effectiveness of authorization policies in shared enterprise databases and will replace cumbersome authorization enforcement practices through complicated view definitions on a per user basis. However, as advances in this area are being made and ideas crystallized, the concomitant weaknesses of the MLS databases are also surfacing. We insist that the critical problem with the current model is that the
belief
at a higher security level is cluttered with irrelevant or inconsistent data as no mechanism for attenuation is supported. Critics also argue that it is imperative for MLS database users to theorize about the belief of others, perhaps at different security levels, an apparatus that is currently missing and the absence of which is seriously felt.

The impetus for our current research is this need to provide an adequate framework for belief reasoning in MLS databases. We demonstrate that a prudent application of the concept of inheritance in a deductive database setting will help capture the notion of declarative belief and belief reasoning in MLS databases in an elegant way. To this end, we develop a function to compute belief in multiple modes which can be used to reason about the beliefs of other users. We strive to develop a poised and practical logical characterization of MLS databases for the first time based on the inherently difficult concept of non-monotonic inheritance. We present an extension of the acclaimed Datalog language, called the MultiLog, and show that Datalog is a special case of our language. We also suggest an implementation scheme for MultiLog as a front-end for CORAL.
Multi-dimensional selectivity estimation using compressed histogram information
Authors: Lee Ju-Hong , Kim Deok-Hwan , Chung Chin-Wan
Published: November 2005

The database query optimizer requires the estimation of the query selectivity to find the most efficient access plan. For queries referencing multiple attributes from the same relation, we need a multi-dimensional selectivity estimation technique when the attributes are dependent each other because the selectivity is determined by the joint data distribution of the attributes. Additionally, for multimedia databases, there are intrinsic requirements for the multi-dimensional selectivity estimation because feature vectors are stored in multi-dimensional indexing trees. In the 1-dimensional case, a histogram is practically the most preferable. In the multi-dimensional case, however, a histogram is not adequate because of high storage overhead and high error rates.

In this paper, we propose a novel approach for the multi-dimensional selectivity estimation. Compressed information from a large number of small-sized histogram buckets is maintained using the discrete cosine transform. This enables low error rates and low storage overheads even in high dimensions. In addition, this approach has the advantage of supporting dynamic data updates by eliminating the overhead for periodical reconstructions of the compressed information. Extensive experimental results show advantages of the proposed approach.
An efficient bitmap encoding scheme for selection queries
Authors: Chan Chee-Yong , Ioannidis Yannis E.
Published: November 2005

Bitmap indexes are useful in processing complex queries in decision support systems, and they have been implemented in several commercial database systems. A key design parameter for bitmap indexes is the
encoding scheme
, which determines the bits that are set to 1 in each bitmap in an index. While the relative performance of the two existing bitmap encoding schemes for simple selection queries of the form “
v
1
≤
A
≤
v
2
” is known (specifically, one of the encoding schemes is better for processing equality queries; i.e.,
v
1
=
v
2
, while the other is better for processing range queries; i.e.,
v
1
<
v
2
), it remains an open question whether these two encoding schemes are indeed optimal for their respective query classes in the sense that there is no other encoding scheme with better space-time tradeoff. In this paper, we establish a number of optimality results for the existing encoding schemes; in particular, we prove that neither of the two known schemes is optimal for the class of two-sided range queries. We also propose a new encoding scheme and prove that it is optimal for that class. Finally, we present an experimental study comparing the performance of the new encoding scheme with that of the existing ones as well as four hybrid encoding schemes for both simple selection queries and the more general class of membership queries of the form “
A
∈ {
v
1
,
v
2
, .…,

v
k

}”. These results demonstrate that the new encoding scheme has an overall better space-time performance than existing schemes.
A comparison of selectivity estimators for range queries on metric attributes
Authors: Blohsfeld Björn , Korus Dieter , Seeger Bernhard
Published: November 2005

In this paper, we present a comparison of nonparametric estimation methods for computing approximations of the selectivities of queries, in particular range queries. In contrast to previous studies, the focus of our comparison is on metric attributes with large domains which occur for example in spatial and temporal databases. We also assume that only small sample sets of the required relations are available for estimating the selectivity. In addition to the popular histogram estimators, our comparison includes so-called kernel estimation methods. Although these methods have been proven to be among the most accurate estimators known in statistics, they have not been considered for selectivity estimation of database queries, so far. We first show how to generate kernel estimators that deliver accurate approximate selectivities of queries. Thereafter, we reveal that two parameters, the number of samples and the so-called smoothing parameter, are important for the accuracy of both kernel estimators and histogram estimators. For histogram estimators, the smoothing parameter determines the number of bins (histogram classes). We first present the optimal smoothing parameter as a function of the number of samples and show how to compute approximations of the optimal parameter. Moreover, we propose a new selectivity estimator that can be viewed as an hybrid of histogram and kernel estimators. Experimental results show the performance of different estimators in practice. We found in our experiments that kernel estimators are most efficient for continuously distributed data sets, whereas for our real data sets the hybrid technique is most promising.
Random sampling techniques for space efficient online computation of order statistics of large datasets
Authors: Manku Gurmeet Singh , Rajagopalan Sridhar , Lindsay Bruce G.
Published: November 2005

In a recent paper [MRL98], we had described a general framework for single pass approximate quantile finding algorithms. This framework included several known algorithms as special cases. We had identified a new algorithm, within the framework, which had a significantly smaller requirement for main memory than other known algorithms. In this paper, we address two issues left open in our earlier paper.

First, all known and space efficient algorithms for approximate quantile finding require advance knowledge of the length of the input sequence. Many important database applications employing quantiles cannot provide this information. In this paper, we present a novel non-uniform random sampling scheme and an extension of our framework. Together, they form the basis of a new algorithm which computes approximate quantiles without knowing the input sequence length.

Second, if the desired quantile is an extreme value (e.g., within the top 1% of the elements), the space requirements of currently known algorithms are overly pessimistic. We provide a simple algorithm which estimates extreme values using less space than required by the earlier more general technique for computing all quantiles. Our principal observation here is that random sampling is quantifiably better when estimating extreme values than is the case with the median.
On random sampling over joins
Authors: Chaudhuri Surajit , Motwani Rajeev , Narasayya Vivek
Published: November 2005

A major bottleneck in implementing sampling as a primitive relational operation is the inefficiency of sampling the output of a query. It is not even known whether it is possible to generate a sample of a join tree without first evaluating the join tree completely. We undertake a detailed study of this problem and attempt to analyze it in a variety of settings. We present theoretical results explaining the difficulty of this problem and setting limits on the efficiency that can be achieved. Based on new insights into the interaction between join and sampling, we develop join sampling techniques for the settings where our negative results do not apply. Our new sampling algorithms are significantly more efficient than those known earlier. We present experimental evaluation of our techniques on Microsoft's SQL Server 7.0.
Ripple joins for online aggregation
Authors: Haas Peter J. , Hellerstein Joseph M.
Published: November 2005

We present a new family of join algorithms, called ripple joins, for online processing of multi-table aggregation queries in a relational database management system (DBMS). Such queries arise naturally in interactive exploratory decision-support applications.

Traditional offline join algorithms are designed to minimize the time to completion of the query. In contrast, ripple joins are designed to minimize the time until an acceptably precise estimate of the query result is available, as measured by the length of a confidence interval. Ripple joins are adaptive, adjusting their behavior during processing in accordance with the statistical properties of the data. Ripple joins also permit the user to dynamically trade off the two key performance factors of on-line aggregation: the time between successive updates of the running aggregate, and the amount by which the confidence-interval length decreases at each update. We show how ripple joins can be implemented in an existing DBMS using iterators, and we give an overview of the methods used to compute confidence intervals and to adaptively optimize the ripple join “aspect-ratio” parameters. In experiments with an initial implementation of our algorithms in the POSTGRES DBMS, the time required to produce reasonably precise online estimates was up to two orders of magnitude smaller than the time required for the best offline join algorithms to produce exact answers.
Client-site query extensions
Authors: Mayr Tobias , Seshadri Praveen
Published: November 2005

We explore the execution of queries with client-site user-defined functions (UDFs). Many UDFs can only be executed at the client site, for reasons of scalability, security, confidentiality, or availability of resources. How should a query with client-site UDFs be executed? We demonstrate that the standard execution technique for server-site UDFs performs poorly. Instead, we adapt well-known distributed database algorithms and apply them to client-site UDFs. The resulting query execution techniques are implemented in the Cornell Predator database system, and we present performance results to demonstrate their effectiveness. We also consider the question of query optimization in the context of client-site UDFs. The known techniques for expensive UDFs are inadequate because they do not take the location of the UDF into account. We present an extension of traditional 'System-R' optimizers that suitably optimize queries with client-site operations.
Shrinking the warehouse update Window
Authors: Labio Wilburt Juan , Yerneni Ramana , Garcia-Molina Hector
Published: November 2005

Warehouse views need to be updated when source data changes. Due to the constantly increasing size of warehouses and the rapid rates of change, there is increasing pressure to reduce the time taken for updating the warehouse views. In this paper we focus on reducing this “update window” by minimizing the work required to compute and install a batch of updates. Various strategies have been proposed in the literature for updating a single warehouse view. These algorithms typically cannot be extended to come up with good strategies for updating an entire set of views. We develop an efficient algorithm that selects an optimal update strategy for any single warehouse view. Based on this algorithm, we develop an algorithm for selecting strategies to update a set of views. The performance of these algorithms is studied with experiments involving warehouse views based on TPC-D queries.
WALRUS
Authors: Natsev Apostol , Rastogi Rajeev , Shim Kyuseok
Published: November 2005

Traditional approaches for
content-based image querying
typically compute a single signature for each image based on color histograms, texture, wavelet tranforms etc., and return as the query result, images whose signatures are closest to the signature of the query image. Therefore, most traditional methods break down when images contain similar objects that are scaled differently or at different locations, or only certain regions of the image match.

In this paper, we propose WALRUS (WAveLet-based Retrieval of User-specified Scenes), a novel similarity retrieval algorithm that is robust to scaling and translation of objects within an image. WALRUS employs a novel similarity model in which each image is first decomposed into its regions, and the similarity measure between a pair of images is then defined to be the fraction of the area of the two images covered by matching regions from the images. In order to extract regions for an image, WALRUS considers sliding windows of varying sizes and then clusters them based on the proximity of their signatures. An efficient dynamic programming algorithm is used to compute wavelet-based signatures for the sliding windows. Experimental results on real-life data sets corroborate the effectiveness of WALRUS's similarity model that performs similarity matching at a region rather than an image granularity.
Efficient geometry-based similarity search of 3D spatial databases
Authors: Keim Daniel A.
Published: November 2005

Searching a database of 3D-volume objects for objects which are similar to a given 3D search object is an important problem which arises in number of database applications — for example, in Medicine and CAD. In this paper, we present a new geometry-based solution to the problem of searching for similar 3D-volume objects. The problem is motivated from a real application in the medical domain where volume similarity is used as a basis for surgery decisions. Our solution for an efficient similarity search on large databases of 3D volume objects is based on a new geometric index structure. The basic idea of our new approach is to use the concept of hierarchical approximations of the 3D objects to speed up the search process. We formally show the correctness of our new approach and introduce two instantiations of our general idea, which are based on cuboid and octree approximations. We finally provide a performance evaluation of our new index structure revealing significant performance improvements over existing approaches.
Computing capabilities of mediators
Authors: Yerneni Ramana , Li Chen , Garcia-Molina Hector , Ullman Jeffrey
Published: November 2005

Existing data-integration systems based on the mediation architecture employ a variety of mechanisms to describe the query-processing capabilities of sources. However, these systems do not compute the capabilities of the mediators based on the capabilities of the sources they integrate. In this paper, we proposed a framework to capture a rich variety of query-processing capabilities of data sources and mediators. We present algorithms to compute the set of supported queries of a mediator, based on the capability limitations of its sources. Our algorithms take into consideration a variety of query-processing techniques employed by mediators to enhance the set of supported queries.
Query rewriting for semistructured data
Authors: Papakonstantinou Yannis , Vassalos Vasilis
Published: November 2005

We address the problem of query rewriting for TSL, a language for querying semistructured data. We develop and present an algorithm that, given a semistructured query
q
and a set of semistructured views
V
, finds
rewriting
queries, i.e., queries that access the views and produce the same result as
q
. Our algorithm is based on appropriately generalizing
containment mappings
, the
chase
, and
query composition
— techniques that were developed for structured, relational data. We also develop an algorithm for equivalence checking of TSL queries.

We show that the algorithm is sound and complete for TSL, i.e., it always finds every non-trivial TSL rewriting query of
q
, and we discuss its complexity. We extend the rewriting algorithm to use some forms of structural constraints (such as DTDs) and find more opportunities for query rewriting.
Record-boundary discovery in Web documents
Authors: Embley D. W. , Jiang Y. , Ng Y.-K.
Published: November 2005

Extraction of information from unstructured or semistructured Web documents often requires a recognition and delimitation of records. (By “record” we mean a group of information relevant to some entity.) Without first chunking documents that contain multiple records according to record boundaries, extraction of record information will not likely succeed. In this paper we describe a heuristic approach to discovering record boundaries in Web documents. In our approach, we capture the structure of a document as a tree of nested HTML tags, locate the subtree containing the records of interest, identify candidate separator tags within the subtree using five independent heuristics, and select a consensus separator tag based on a combined heuristic. Our approach is fast (runs linearly for practical cases within the context of the larger data-extraction problem) and accurate (100% in the experiments we conducted).
Petabyte databases
Authors: Düllmann Dirk
Published: November 2005

This paper describes the use of Object-Database Management Systems (ODBMS)for the storage of High-Energy Physics (HEP) data.
A database perspective on Lotus Domino/Notes
Authors: Mohan C.
Published: November 2005

In this one-page summary, I introduce the database aspects of Lotus Domino/Notes. These database features are covered in detail in the corresponding SIGMOD99 tutorial available at www.almaden.ibm.com/u/mohan/domino_sigmod99.ps.
Hypertext databases and data mining
Authors: Chakrabarti Soumen
Published: November 2005

The volume of unstructured text and hypertext data far exceeds that of structured data. Text and hypertext are used for digital libraries, product catalogs, reviews, newsgroups, medical reports, customer service reports, and the like. Currently measured in billions of dollars, the worldwide internet activity is expected to reach a trillion dollars by 2002. Database researchers have kept some cautious distance from this action. The goal of this tutorial is to expose database researchers to text and hypertext information retrieval (IR) and mining systems, and to discuss emerging issues in the overlapping areas of databases, hypertext, and data mining.
The need for distributed asynchronous transactions
Authors: Do Lyman , Ram Prabhu , Drew Pamela
Published: November 2005

The theme of the paper is to promote research on asynchronous transactions. We discuss our experience of executing synchronous transactions on a large distributed production system in The Boeing Company. Due to the poor performance of synchronous transactions in our environment, it motivated the exploration of asynchronous transactions as an alternate solution. This paper presents the requirements and benefits/limitations of asynchronous transactions. Open issues related to large scale deployments of asynchronous transactions are also discussed.
Improving OLTP data quality using data warehouse mechanisms
Authors: Jarke Matthias , Quix Christoph , Blees Guido , Lehmann Dirk , Michalk Gunter , Stierl Stefan
Published: November 2005

Research and products for the integration of heterogeneous legacy source databases in data warehousing have addressed numerous data quality problems in or between the sources. Such a solution is marketed by Team4 for the decision support of mobile sales representatives, using advanced view maintenance and replication management techniques in an environment based on relational data warehouse technology and Lotus Notes-based client systems. However, considering total information supply chain management, the capture of poor operational data, to be cleaned later in the data warehouse, appears sub-optimal. Based on the observation that decision support clients are often closely linked to operational data entry, we have addressed the problem of mapping the data warehouse data quality techniques back to data quality measures for improving OLTP data. The solution requires a warehouse-to-OLTP workflow which employs a combination of view maintenance and view update techniques.
Data integration and warehousing in Telecom Italia
Authors: Trisolini Stefano M. , Lenzerini Maurizio , Nardi Daniele
Published: November 2005

We discuss the main methodological and technological issues arosen in the last years in the development of the enterprise integrated database of Telecom Italia and, subsequently in the management of the primary data store for Telecom Italia data warehouse applications.

The two efforts, although driven by different needs and requirements can be regarded as a continous development of an integrated view of the enterprise data. We review the experience accumulated in the integration of over 50 internal databases, highlighting the benefits and drawbacks of this scenario for data warehousing and discuss the development of a large dedicated data store to support the analysis of data about customers and phone traffic.
DOMINO
Authors: Wolfson Ouri , Sistla Prasad , Xu Bo , Zhou Jutai , Chamberlain Sam
Published: November 2005

Consider a database that represents information about moving objects and their location. For example, for a database representing the location of taxi-cabs a typical query may be: retrieve the free cabs that are currently within 1 mile of 33 N. Michigan Ave., Chicago (to pick-up a customer); or for a trucking company database a typical query may be: retrieve the trucks that are currently within 1 mile of truck ABT312 (which needs assistance); or for a database representing the current location of objects in a battlefield a typical query may be: retrieve the friendly helicopters that are in a given region, or, retrieve the friendly helicopters that are expected to enter the region within the next 10 minutes. The queries may originate from the moving objects, or from stationary users. We will refer to applications with the above characteristics as moving-objects-database (MOD) applications, and to queries as the ones mentioned above as MOD queries.

In the military MOD applications arise in the context of the digital battlefield (see [1]), and in the civilian industry they arise in transportation systems. For example, Omnitracs developed by Qualcomm (see[2]) is a commercial system used by the transportation industry, which enables MOD functionality. It provides location management by connecting vehicles (e.g. trucks), via satellites, to company databases. The vehicles are equipped with a Global Positioning System (GPS), and they automatically and periodically report their location.
Database patchwork on the Internet
Authors: Braumandl Reinhard , Kemper Alfons , Kossmann Donald
Published: November 2005

Naturally, data processing requires three kinds of resources:

the data itself,

the functionality (i.e. database operations) and

the machines on which to run the operations.

Because of the Internet we believe that in the long run there will be alternative providers for all of these three resources for any given application.
Data providers
will bring more and more data and more and more different kinds of data to the net. Likewise,
function providers
will develop new methods to process and work with the data; e.g., function providers might develop new algorithms to compress data or to produce thumbnails out of large images and try to
sell
these on the Internet. It is also conceivable, that some people allow other people to use spare cycles of their idle machines in the Internet (as in the Condor system of the University of Wisconsin) or that some companies (
cycle providers
) even specialize on selling computing time to businesses that occasionally need to carry out very complex operations for which regular hardware is not sufficient.

At the University of Passau, we are currently developing a distributed database system to be used in the Internet. The goal is to ultimately have a system which is able to run on any machine, manage any kind of data, import any kind of data from other systems and import any kind of database operations. The system is entirely written in Java. One of the most important features of the system is that it is capable of dynamically loading (external) query operators, written in Java and supplied by any function provider, and executing these query operators in concert with pre-defined and other external operators in order to evaluate a query. Compared to object-relational database systems, which allow to integrate external data and functionality by the means of extensions (datablades, extenders or cartridges) or heterogeneous database systems such as Garlic [MS97] or Tsimmis [GMPQ
+
97], our approach makes it possible to place external query operators anywhere in a query evaluation plan as opposed to restricting the placement of external operations to the “access level” of plans. It would, for example, be possible to make our system execute a completely new relational join method, if somebody finds a new join method which is worth-while implementing. Because our system is written in Java, it is highly portable and could be used by data, function and cycle providers with almost no effort. Furthermore, our query engine is, of course, completely distributed providing all the required infrastructure for server-server communication, name services, etc.
Evolvable view environment (EVE)
Authors: Rundensteiner E. A. , Koeller A. , Zhang X. , Lee A. J. , Nica A. , Van Wyk A. , Lee Y.
Published: November 2005

Supporting independent ISs and integrating them in distributed data warehouses (materialized views) is becoming more important with the growth of the WWW. However, views defined over autonomous ISs are susceptible to schema changes. In the
EVE
project we are developing techniques to support the maintenance of data warehouses defined over distributed
dynamic
ISs [5, 6, 7]. The
EVE
system is the first to allow views to survive
schema changes
of their underlying ISs while also adapting to changing data in those sources.
EVE
achieves this is two steps: applying view query rewriting algorithms that exploit information about alternative ISs and the information they contain, and incrementally adapting the view extent to the view definition changes. Those processes are referred to as
view synchronization
and
view adaption
, respectively. They increase the survivability of materialized views in changing environments and reduce the necessity of human interaction in system maintenance.
Exploratory mining via constrained frequent set queries
Authors: Ng Raymond , Lakshmanan Laks V. S. , Han Jiawei , Mah Teresa
Published: November 2005

Although there have been many studies on data mining, to date there have been few research prototypes or commercial systems supporting comprehensive query-driven mining, which encourages interactive exploration of the data. Our thesis is that constraint constructs and the optimization they induce play a pivotal role in mining queries, thus substantially enhancing the usefulness and performance of the mining system. This is based on the analogy of declarative query languages like SQL and query optimization which have made relational databases so successful. To this end, our proposed demo is not yet another data mining system, but of a new paradigm in data mining - mining with constraints, as the important first step towards supporting ad-hoc mining in DBMS.

In this demo, we will show a prototype exploratory mining system that implements constraint-based mining query optimization methods proposed in [5]. We will demonstrate how a user can interact with the system for exploratory data mining and how efficiently the system may execute optimized data mining queries. The prototype system will include all the constraint pushing techniques for mining association rules outlined in [5], and will include additional capabilities for mining other kinds of rules for which the computation of constrained frequent sets forms the core first step.
The active MultiSync controller of the cubetree storage organization
Authors: Roussopoulos Nick , Kotidis Yannis , Sismanis Yannis
Published: November 2005

The
Cubetree Storage Organization (CSO)
1
logically and physically clusters materialized-views data, multi-dimensional indices on them, and computed aggregate values all in one compact and tight storage structure that uses a fraction of the conventional table-based space. This is a breakthrough technology for storing and accessing multi-dimensional data in terms of storage reduction, query performance and incremental bulk update speed. CSO has been extended with an Active MultiSync controller for synchronizing multiple concurrent access and continuous asynchronous online updates for a non-stop data warehouse.
The Jungle database search engine
Authors: Böhlen Michael , Bukauskas Linas , Dyreson Curtis
Published: November 2005

Information spread in in databases cannot be found by current search engines. A database search engine is capable to access and advertise database on the WWW. Jungle is a database search engine prototype developed at Aalborg University. Operating through JDBC connections to remote databases, Jungle extracts and indexes database data and meta-data, building a data store of database information. This information is used to evaluate and optimize queries in the AQUA query language. AQUA is a natural and intuitive database query language that helps users to search for information without knowing how that information is structured. This paper gives an overview of AQUA and describes the implementation of Jungle.
XML-based information mediation with MIX
Authors: Baru Chaitan , Gupta Amarnath , Ludäscher Bertram , Marciano Richard , Papakonstantinou Yannis , Velikhov Pavel , Chu Vincent
Published: November 2005

The MIX mediator system, MIX
m
, is developed as part of the MIX Project at the San Diego Supercomputer Center, and the University of California, San Diego.
1
MIX
m
uses XML as the common model for data exchange. Mediator views are expressed in XMAS (
XML Matching And Structuring Language
), a declarative XML query language. To facilitate user-friendly query formulation and for optimization purposes, MIX
m
employs XML DTDs as a structural description (in effect, a “schema”) of the exchanged data. The novel features of the system include:

Data exchange and integration solely relies on XML, i.e., instance and schema information is represented by XML documents and XML DTDs, respectively. XML queries are denoted in XMAS, which builds upon ideas of languages like XML-QL, MSL, Yat, and UnQL. Additionally, XMAS features powerful grouping and order constructs for generating new integrated XML “objects” from existing ones.

The graphical user interface BBQ (
Blended Browsing and Querying
) is driven by the mediator view DTD and integrates browsing and querying of XML data. Complex queries can be constructed in an intuitive way, resembling QBE. Due to the nested nature of XML data and DTDs, BBQ provides graphical means to specify the nesting and grouping of query results.

Query evaluation can be demand-driven, i.e., by the user's navigation into the mediated view.
An anonymous electronic commerce scheme with an off-line authority and untrusted agents
Authors: Domingo-Ferrer Josep , Herrera-Joancomartí Jordi
Published: November 2005

In the last years, the exponential growth of computer networks has created an incredibly large offer of products and services in the net. Such a huge amount of information makes it impossible for a single person to analyze all existing offers of a product on the net and decide which of them fits better her requirements. This problem is solved with the intelligent trade agents (ITA), which are programs that have the ability to roam a network, collect business-related data and use them to make decisions to buy goods on their owners' behalf. Known ITA systems do not provide anonymity in transactions, require an on-line trusted third party and implicitly assume that the user trusts the ITA. We present a new scheme for an intelligent untrusted trade agent system allowing anonymous electronic transactions with an off-line trusted third party.
The middleware muddle
Authors: Ritter David
Published: November 2005

A new menagerie of middleware is emerging. These products promise great flexibility in partitioning enterprise applications across the diverse corporate computing landscape. What factors should you consider when choosing a solution, and how do current products stack up? More important to the focus of this article, what role should Web servers play?
Semantic interoperability in global information systems
Authors: Ouksel A. M. , Sheth A.
Published: November 2005

Internet, Web and distributed computing infrastructures continue to gain in popularity as a means of communication for organizations, groups and individuals alike. In such an environment, characterized by large distributed, autonomous, diverse, and dynamic information sources, access to relevant and accurate information is becoming increasingly complex. This complexity is exacerbated by the evolving system, semantic and structural heterogeneity of these potentially global, cross-disciplinary, multicultural and rich-media technologies. Clearly, solutions to these challenges require addressing directly a variety of interoperability issues.
Semantic and pedagogic interoperability mechanisms in the ARIADNE educational repository
Authors: Forte E. , Haenni F. , Warkentyne K. , Duval E. , Cardinaels K. , Vervaet E. , Hendrikx K. , Forte M. Wentland , Simillion F.
Published: November 2005

This paper reports on the principles underlying the semantic and pedagogic interoperability mechanisms built in the European Knowledge Pool System, developed by the European research project ARIADNE. This system, which is the central feature of ARIADNE, consists in a distributed repository of pedagogical documents (or learning objects) of diverse granularity, origin, content, type, language, etc., which are stored in view of their use (and reuse) in telematics-based training or teaching curricula. The learning objects are indexed, usually by faculty staff, according to the ARIADNE metadata set. The principles embodied in the indexation tool, which interacts directly with the repository,stem from a few theoretical ideas but foremost from empirical, pragmatic considerations, suggested by the context of actual use. They tentatively address the stringent demands for semantic and pedagogic interoperability implied by a context of rather wide cultural and linguistic diversity, as well as those stemming from the very nature of the domain application itself: education and training. Possible extensions to the educational metadata scheme developed by ARIADNE on these basis, may accommodate corporate training/information needs. These extensions are briefly discussed as a mean for enhancing 'semantic' interoperability between different (kinds of) corporations. Finally, the architecture of the ARIADNE system, which heavily relies on this educational metadata system, is briefly reviewed.
Report on the 13th Brazilian symposium on database systems (SBBD'98)
Authors: Nascimento Mario A. , Medeiros Claudia Bauzer
Published: November 2005

The Brazilian Symposium on Database Systems (SBBD) is a traditional conference in Brazil, and is sponsored by the Brazilian Computer Society. SBBD's technical program contemplates the following activities: presentation of peer reviewed full technical papers, invited talks, tutorials (either invited and selected from submissions), discussion panels and presentation of tools.
Engineering federated information systems
Authors: Conrad S. , Hasselbring W. , Hohenstein U. , Kutsche R.-D. , Roantree M. , Saake G. , Saltor F.
Published: November 2005

After the successful first International Workshop on Engineering Federated Database Systems (EFDBS'97) in Barcelona in June 1997 [CEH
+
97], the goal of this second workshop was to bring together researchers and practitioners interested in various issues in the development of federated information systems, whereby the scope has been extended to cover database and non-database information sources (the change from EFDBS to EFIS reflects this). This report provides details of the workshop content and the conclusions reached in the final discussion.
Distributed transactions in practice
Authors: Ram Prabhu , Do Lyman , Drew Pamela
Published: November 2005

The concept of transactions and its application has found wide and often indiscriminate usage. In large enterprises, the model for distributed database applications has moved away from the client-server model to a multi-tier model with large database application software forming the middle tier. The software philosophy of “buy and not build” in large enterprises has had a major influence by extending functional requirements such as transactions and data consistency throughout the multiple tiers. In this article, we will discuss the effects of applying traditional transaction management techniques to multi-tier architectures in distributed environments. We will show the performance costs associated with distributed transactions and discuss ways by which enterprises really manage their distributed data to circumvent this performance hit. Our intent is to share our experience as an industrial customer with the database research and vendor community to create more usable and scalable designs.
Mining frequent patterns without candidate generation
Authors: Han Jiawei , Pei Jian , Yin Yiwen
Published: November 2005

Mining frequent patterns in transaction databases, time-series databases, and many other kinds of databases has been studied popularly in data mining research. Most of the previous studies adopt an Apriori-like candidate set generation-and-test approach. However, candidate set generation is still costly, especially when there exist prolific patterns and/or long patterns.

In this study, we propose a novel frequent pattern tree (FP-tree) structure, which is an extended prefix-tree structure for storing compressed, crucial information about frequent patterns, and develop an efficient FP-tree-based mining method, FP-growth, for mining
the complete set of frequent patterns
by pattern fragment growth. Efficiency of mining is achieved with three techniques: (1) a large database is compressed into a highly condensed, much smaller data structure, which avoids costly, repeated database scans, (2) our FP-tree-based mining adopts a pattern fragment growth method to avoid the costly generation of a large number of candidate sets, and (3) a partitioning-based, divide-and-conquer method is used to decompose the mining task into a set of smaller tasks for mining confined patterns in conditional databases, which dramatically reduces the search space. Our performance study shows that the FP-growth method is efficient and scalable for mining both long and short frequent patterns, and is about an order of magnitude faster than the Apriori algorithm and also faster than some recently reported new frequent pattern mining methods.
High speed on-line backup when using logical log operations
Authors: Lomet David B.
Published: November 2005

Media recovery protects a database from failures of the stable medium by maintaining an extra copy of the database, called the backup, and a media recovery log. When a failure occurs, the database is “restored” from the backup, and the media recovery log is used to roll forward the database to the desired time, usually the current time. Backup must be both fast and “on-line”, i.e. concurrent with on-going update activity. Conventional online backup sequentially copies from the stable database, almost independent of the database cache manager, but requires page-oriented log operations. But results of logical operations must be flushed to a stable database (a backup is a stable database) in a constrained order to guarantee recovery. This order is not naturally achieved for the backup by a cache manager concerned only with crash recovery. We describe a “full speed” backup, only loosely coupled to the cache manager, and hence similar to current online backups, but effective for general logical log operations. This requires additional logging of cached objects to guarantee media recoverability. We then show how logging can be greatly reduced when log operations have a constrained form which nonetheless provides very useful additional logging efficiency for database systems.
Efficient resumption of interrupted warehouse loads
Authors: Labio Wilburt Juan , Wiener Janet L. , Garcia-Molina Hector , Gorelik Vlad
Published: November 2005

Data warehouses collect large quantities of data from distributed sources into a single repository. A typical load to create or maintain a warehouse processes GBs of data, takes hours or even days to execute, and involves many complex and user-defined transformations of the data (e.g., find duplicates, resolve data inconsistencies, and add unique keys). If the load fails, a possible approach is to “redo” the entire load. A better approach is to resume the incomplete load from where it was interrupted. Unfortunately, traditional algorithms for resuming the load either impose unacceptable overhead during normal operation, or rely on the specifics of transformations. We develop a resumption algorithm called
DR
that imposes no overhead and relies only on the high-level properties of the transformations. We show that
DR
can lead to a ten-fold reduction in resumption time by performing experiments using commercial software.
On-line reorganization in object databases
Authors: Lakhamraju Mohana K. , Rastogi Rajeev , Seshadri S. , Sudarshan S.
Published: November 2005

Reorganization of objects in an object databases is an important component of several operations like compaction, clustering, and schema evolution. The high availability requirements (24 × 7 operation) of certain application domains requires reorganization to be performed on-line with minimal interference to concurrently executing transactions.

In this paper, we address the problem of on-line reorganization in object databases, where a set of objects have to be migrated from one location to another. Specifically, we consider the case where objects in the database may contain physical references to other objects. Relocating an object in this case involves finding the set of objects (parents) that refer to it, and modifying the references in each parent. We propose an algorithm called the Incremental Reorganization Algorithm (IRA) that achieves the above task with minimal interference to concurrently executing transactions. The IRA algorithm holds locks on at most two distinct objects at any point of time. We have implemented IRA on Brahma, a storage manager developed at IIT Bombay, and conducted an extensive performance study. Our experiments reveal that IRA makes on-line reorganization feasible, with very little impact on the response times of concurrently executing transactions and on overall system throughput. We also describe how the IRA algorithm can handle system failures.