bluuebunny/crossref_metadata_2025 huggingface dataset:
A study on data point search for HG-trees
Authors: Kuan Joseph , Lewis Paul
Published: November 2005

A point data retrieval algorithm for the HG-tree is introduced which improves the number of nodes accessed. The HG-tree is a multidimensional indexing tree designed for point data and it is a simple modification from the Hilbert R-tree for indexing spatial data. The HG-tree data search method mainly makes use of the Hilbert index values to search for exact data, instead of using conventional point search methods as used in most of the R-tree papers. The use of Hilbert curve values and MBR can reduce the spatial cover of an MBR.

Several R-tree variants have been developed; R*-tree, S-tree, Hilbert R-tree, and R*-tree combined with the linear split method by Ang et al. Our search method on the HG-tree gives a superior speed performance compared to all other R-tree variants.
The OASIS multidatabase prototype
Authors: Roantree Mark , Murphy John , Hasselbring Wilhelm
Published: November 2005

The OASIS Prototype is under development at Dublin City University in Ireland. We describe a multi-database architecture which uses the ODMG model as a canonical model and describe an extention for construction of virtual schemas within the multidatabase system. The OMG model is used to provide a standard distribution layer for data from local databases. This takes the form of CORBA objects representing export schemas from separate data sources.
On mutli-resolution document transmission in mobile Web
Authors: Yau Stanley M. T. , Leong Hong Va , McLeod Dennis , Si Antonio
Published: November 2005

We propose a
multi-resolution transmission mechanism
that allows various organizational units of a web document to be transferred and browsed according to the amount of information captured. We define the notion of
information content
for each individual organizational unit of a web document as an indication of its captured information. The concept of information content is used as a foundation for defining the notion of
relative information content
which determines the transmission order of various units. Our mechanism allows a web client to explore the more content-bearing portion of a web document earlier so as to be able to terminate browsing a possibly irrelevant document sooner. This scheme is based on our observation that different organizational units of a document contribute to different amount of information to the document. Such a multi-resolution transmission paradigm is particularly useful in mobile web where the wireless bandwidth is a scarce resource and browsing every document in detail would consume the bandwidth unnecessarily. This is becoming more serious when the size of a web document is getting large, such as technical documents. We then present a prototype of the system in Java and CORBA to illustrate its feasibility.
XMill
Authors: Liefke Hartmut , Suciu Dan
Published: November 2005

We describe a tool for compressing XML data, with applications in data exchange and archiving, which usually achieves about twice the compression ratio of gzip at roughly the same speed. The compressor, called XMill, incorporates and combines existing compressors in order to apply them to heterogeneous XML data: it uses zlib, the library function for gzip, a collection of datatype specific compressors for simple data types, and, possibly, user defined compressors for application specific data types.
Spatial join selectivity using power laws
Authors: Faloutsos Christos , Seeger Bernhard , Traina Agma , Traina Caetano
Published: November 2005

We discovered a surprising law governing the spatial join selectivity across two sets of points. An example of such a spatial join is “
find the libraries that are within 10 miles of schools
”. Our law dictates that the number of such qualifying pairs follows a power law, whose exponent we call “pair-count exponent” (PC). We show that this law also holds for self-spatial-joins (“
find schools within 5 miles of other schools
”) in addition to the general case that the two point-sets are distinct. Our law holds for many real datasets, including diverse environments (geographic datasets, feature vectors from biology data, galaxy data from astronomy).

In addition, we introduce the concept of the Box-Occupancy-Product-Sum (BOPS) plot, and we show that it can compute the pair-count exponent in a timely manner, reducing the run time by orders of magnitude, from quadratic to linear. Due to the pair-count exponent and our analysis (Law 1), we can achieve accurate selectivity estimates in constant time (O(1)) without the need for sampling or other expensive operations. The relative error in selectivity is about 30% with our fast BOPS method, and even better (about 10%), if we use the slower, quadratic method.
NiagaraCQ
Authors: Chen Jianjun , DeWitt David J. , Tian Feng , Wang Yuan
Published: November 2005

Continuous queries are persistent queries that allow users to receive new results when they become available. While continuous query systems can transform a passive web into an active environment, they need to be able to support millions of queries due to the scale of the Internet. No existing systems have achieved this level of scalability. NiagaraCQ addresses this problem by grouping continuous queries based on the observation that many web queries share similar structures. Grouped queries can share the common computation, tend to fit in memory and can reduce the I/O cost significantly. Furthermore, grouping on selection predicates can eliminate a large number of unnecessary query invocations. Our grouping technique is distinguished from previous group optimization approaches in the following ways. First, we use an incremental group optimization strategy with dynamic re-grouping. New queries are added to existing query groups, without having to regroup already installed queries. Second, we use a query-split scheme that requires minimal changes to a general-purpose query engine. Third, NiagaraCQ groups both change-based and timer-based queries in a uniform way. To insure that NiagaraCQ is scalable, we have also employed other techniques including incremental evaluation of continuous queries, use of both pull and push models for detecting heterogeneous data source changes, and memory caching. This paper presents the design of NiagaraCQ system and gives some experimental results on the system's performance and scalability.
Efficient algorithms for mining outliers from large data sets
Authors: Ramaswamy Sridhar , Rastogi Rajeev , Shim Kyuseok
Published: November 2005

In this paper, we propose a novel formulation for distance-based
outliers
that is based on the distance of a point from its

k
th

nearest neighbor. We rank each point on the basis of its distance to its

k
th

nearest neighbor and declare the top
n
points in this ranking to be outliers. In addition to developing relatively straightforward solutions to finding such outliers based on the classical nested-loop join and index join algorithms, we develop a highly efficient
partition-based
algorithm for mining outliers. This algorithm first partitions the input data set into disjoint subsets, and then prunes entire partitions as soon as it is determined that they cannot contain outliers. This results in substantial savings in computation. We present the results of an extensive experimental study on real-life and synthetic data sets. The results from a real-life NBA database highlight and reveal several expected and unexpected aspects of the database. The results from a study on synthetic data sets demonstrate that the partition-based algorithm scales well with respect to both data set size and data set dimensionality.
Maintenance of cube automatic summary tables
Authors: Lehner Wolfgang , Sidle Richard , Pirahesh Hamid , Cochrane Roberta Wolfgang
Published: November 2005

Materialized views (or Automatic Summary Tables—ASTs) are commonly used to improve the performance of aggregation queries by orders of magnitude. In contrast to regular tables, ASTs are synchronized by the database system. In this paper, we present techniques for maintaining cube ASTs. Our implementation is based on IBM DB2 UDB.
Of XML and databases (panel session)
Authors: Widom Jennifer , Bosworth Adam , Lindsay Bruce , Stonebraker Michael , Suciu Dan , Carey Michael J.
Published: November 2005

This panel will examine the implications of the XML revolution, which is currently raging on the web, for database systems research and development.
Concept based design of data warehouses
Authors: Jarke M. , Quix C. , Calvanese D. , Lenzerini M. , Franconi E. , Ligoudistianos S. , Vassiliadis P. , Vassiliou Y.
Published: November 2005

The ESPRIT Project DWQ (Foundations of Data Warehouse Quality) aimed at improving the quality of DW design and operation through systematic enrichment of the semantic foundations of data warehousing. Logic-based knowledge representation and reasoning techniques were developed to control accuracy, consistency, and completeness via advanced conceptual modeling techniques for source integration, data reconciliation, and multi-dimensional aggregation. This is complemented by quantitative optimization techniques for view materialization, optimizing timeliness and responsiveness without losing the semantic advantages from the conceptual approach. At the operational level, query rewriting and materialization refreshment algorithms exploit the knowledge developed at design time. The demonstration shows the interplay of these tools under a shared metadata repository, based on an example extracted from an application at Telecom Italia.
Image mining in IRIS
Authors: Hsu Wynne , Lee Mong Li , Goh Kheng Guan
Published: November 2005

There is an increasing demand for systems that can automatically analyze images and extract semantically meaningful information. IRIS, an Integrated Retinal Information system, has been developed to provide medical professionals easy and unified access to the screening, trend and progression of diabetic-related eye diseases in a diabetic patient database. This paper shows how mining techniques can be used to accurately extract features in the retinal images. In particular, we apply a classification approach to determine the conditions for tortuousity in retinal blood vessels.
Comparative analysis of five XML query languages
Authors: Bonifati Angela , Ceri Stefano
Published: November 2005

XML is becoming the most relevant new standard for data representation and exchange on the WWW. Novel languages for extracting and restructuring the XML content have been proposed, some in the tradition of database query languages (i.e. SQL, OQL), others more closely inspired by XML. No standard for XML query language has yet been decided, but the discussion is ongoing within the World Wide Web Consortium and within many academic institutions and Internet-related major companies. We present a comparison of five, representative query languages for XML, highlighting their common features and differences.
Timer-driven database triggers and alerters
Authors: Hanson Eric N. , Noronha Lloyd X.
Published: November 2005

This paper proposes a simple model for a timer-driven triggering and alerting system. Such a system can be used with relational and object-relational databases systems. Timer-driven trigger systems have a number of advantages over traditional trigger systems that test trigger conditions and run trigger actions in response to update events. They are relatively easy to implement since they can be built using a middleware program that simply runs SQL statements against a DBMS. Also, they can check certain types of conditions, such as “a value did not change” or a “a value did not change by more than 10% in six months.” Such conditions may be of interest for a particular application, but cannot be checked correctly by an event-driven trigger system. Also, users may be perfectly happy being notified once a day, once a week, or even less often of certain conditions, depending on their application. Timer triggers are appropriate for these users. The semantics of timer triggers are defined here using a simple procedure. Timer triggers are meant to complement event-driven triggers, not replace them.
We challenge the database research community to developed alternate algorithms and optimizations for processing timer triggers, provided that the semantics are the same as when using the simple procedure presented here.
Some remarks on variable independence, closure, and orthographic dimension in constraint databases
Authors: Libkin Leonid
Published: November 2005

The notion of variable independence was introduced by Chomicki, Goldin, and Kuper in their PODS'96 paper as a means of adding a limited form of aggregation to constraint query languages while retaining the closure property. Later, Grumbach, Rigoux and Segoufin showed in their ICDT'99 paper that variable independence and a related notion of orthographic dimension are useful tools for optimizing constraint queries.

However, several results in those papers are incorrect as stated. As the notions of variable independence and orthographic dimension appear to be important for implementing constraint database prototypes, I explain in this short note the problems with the above mentioned papers and outline a solution for aggregate closure.
Spatial operators
Authors: Clementini Eliseo , Di Felice Paolino
Published: November 2005

This paper discusses issues related to the integration of spatial operators into the new generation of SQL-like query languages. Starting from spatial data models, current spatial extensions of query languages are briefly reviewed and research directions are highlighted. A taxonomy of requirements to be satisfied by spatial operators is proposed with emphasis on users' needs and on the introduction of data uncertainty support. Further, spatial operators are classified into the three important categories of topological, projective, and metric operators and for each of them the state of the art is outlined.
The implementation and performance of compressed databases
Authors: Westmann Till , Kossmann Donald , Helmer Sven , Moerkotte Guido
Published: November 2005

In this paper, we show how compression can be integrated into a relational database system. Specifically, we describe how the storage manager, the query execution engine, and the query optimizer of a database system can be extended to deal with compressed data. Our main result is that compression can significantly improve the response time of queries if very
light-weight
compression techniques are used. We will present such light-weight compression techniques and give the results of running the TPC-D benchmark on a so compressed database and a non-compressed database using the AODB database system, an experimental database system that was developed at the Universities of Mannheim and Passau. Our benchmark results demonstrate that compression indeed offers high performance gains (up to 50%) for IO-intensive queries and moderate gains for CPU-intensive queries. Compression can, however, also increase the running time of certain update operations. In all, we recommend to extend today's database systems with light-weight compression techniques and to make extensive use of this feature.
Using quantitative information for efficient association rule generation
Authors: Pôssas B. , Carvalho M. , Resende R. , Meita W.
Published: November 2005

The problem of mining association rules in categorical data presented in customer transactions was introduced by Agrawal, Imielinski and Swami [2]. This seminal work gave birth to several investigation efforts [4, 13] resulting in descriptions of how to extend the original concepts and how to increase the performance of the related algorithms.The original problem of mining association rules was formulated as how to find rules of the form

set
1

→

set
2

. This rule is supposed to denote affinity or correlation among the two sets containing nominal or ordinal data items. More specifically, such an association rule should translate the following meaning: customers that buy the products in

set
1

also buy the products in

set
2

. Statistical basis is represented in the form of minimum support and confidence measures of these rules with respect to the set of customer transactions.The original problem as proposed by Agrawal et al. [2] was extended in several directions such as adding or replacing the confidence and support by other measures, or filtering the rules during or after generation, or including quantitative attributes. Srikant e Agrawal [16] describe an new approach where quantitative data can be treated as categorical. This is very important since otherwise part of the customer transaction information is discarded. Whenever an extension is proposed it must be checked in terms of its performance. The algorithm efficiency is linked to the size of the database that is amenable to be treated. Therefore it is crucial to have efficient algorithms that enable us to examine and extract valuable decision-making information in the ever larger databases.In this paper we present an algorithm that can be used in the context of several of the extensions provided in the literature but at the same time preserves its performance, as demonstrated in a case study. The approach in our algorithm is to explore multidimensional properties of the data (provided such properties are present), allowing us to combine this additional information in a very efficient pruning phase. This results in a very flexible and efficient algorithm that was used with success in several experiments using categorical and quantitative databases.The paper is organized as follows. In the next section we describe the quantitative association rules and we present an algorithm to generate it. Section 3 presents an optimization of the pruning phase of the Apriori [4] algorithm based on quantitative information associated with the items. Section 4 presents our experimental results for mining four synthetic workloads, followed by some related work in Section 5. Finally we present some conclusions and future work in Section 6.
Object database evolution using separation of concerns
Authors: Rashid Awais , Sawyer Peter
Published: November 2005

This paper proposes an object database evolution approach based on
separation of concerns.
The lack of customisability and extensibility in existing evolution frameworks is a consequence of using attributes at the meta-object level to implement links among meta-objects and the injection of instance adaptation code directly into the class versions. The proposed approach uses dynamic relationships to separate the connection code from meta-objects and
aspects
- abstractions used by Aspect-Oriented Programming to localise cross-cutting concerns - to separate the instance adaptation code from class versions. The result is a customisable and extensible evolution framework with low maintenance overhead.
Cache invalidation scheme for mobile computing systems with real-time data
Authors: Yuen Joe Chun-Hung , Chan Edward , Lam Kam-Yiu , Leung H. W.
Published: November 2005

In this paper, we propose a cache invalidation scheme called Invalidation by Absolute Validity Interval (IAVI) for mobile computing systems. In IAVI, we define an absolute validity interval (AVI), for each data item based on its dynamic property such as the update interval. A mobile client can verify the validity of a cached item by comparing the last update time and its AVI. A cached item is invalidated if the current time is greater than the last update time plus its AVI. With this self-invalidation mechanism, the IAVI scheme uses the invalidation report to inform the mobile clients about changes in AVIs rather than the update event of the data items. As a result, the size of the invalidation report can be reduced significantly. Through extensive simulation experiments, we have found that the performance of the IVAI scheme is significantly better than other methods such as bit sequence and timestamp.
New TPC benchmarks for decision support and web commerce
Authors: Poess Meikel , Floyd Chris
Published: November 2005

For as long as there have been DBMS's and applications that use them, there has been interest in the performance characteristics that these systems exhibit. This month's column describes some of the recent work that has taken place in TPC, the Transaction Processing Performance Council.TPC-A and TPC-B are obsolete benchmarks that you might have heard about in the past. TPC-C V3.5 is the current benchmark for OLTP systems. Introduced in 1992, it has been run on many hardware platforms and DBMS's. Indeed, the TPC web site currently lists 202 TPC-C benchmark results. Due to its maturity, TPC-C will not be discussed in this article.We've asked two very knowledgeable individuals to write this article. Meikel Poess is the chair of the TPC H and TPC-R Subcommittees and Chris Floyd is the chair of the TPC-W Subcommittee. We greatly appreciate their efforts.A wealth of information can be found at the TPC web site [ 1 ]. This information includes the benchmark specifications themselves, TPC membership information, and benchmark results.
Infosphere project
Authors: Pu Calton , Schwan Karsten , Walpole Jonathan
Published: November 2005

We describe the Infosphere project, which is building the systems software support for information-driven applications such as digital libraries and electronic commerce. The main technical contribution is the Infopipe abstraction to support information flow with quality of service. Using building blocks such as program specialization, software feedback, domain-specific languages, and personalized information filtering, the Infopipe software generates code and manages resources to provide the specified quality of service with support for composition and restructuring.
XML and information retrieval
Authors: Carmel David , Maarek Yoelle , Soffer Aya
Published: November 2005

XML - the eXtensible Markup Language has recently emerged as a new standard for data representation and exchange on the Interact. It is believed that it will become a universal format for data exchange on the Web and that in the near future we will find vast amounts of documents in XML format on the Web. As a result, it has become crucial to address the question of how large collections of XML documents can be sorted and retrieved efficiently and effectively.To date, most work on storing, indexing, querying, and searching documents in XML has stemmed from the database community's work on semi-structured data. An alternative approach, that has received less attention to date, is to view XML documents as a collection of text documents with additional tags and relations between these tags. IR techniques have traditionally been applied to search large sets of textual data and should thus be extended to encode the structure and semantics inherent in XML documents. Integrating IR and XML search techniques will enable more sophisticated search on the structure as well as the content of these documents, while leveraging the success of IR techniques in document similarity ranking and keyword search.The SIGIR workshop on XML and information retrieval was held July 28th, in Athens Greece. The goal of the workshop was to bring together researchers and practitioners interested in XML and IR to discuss and define the most relevant topics in the relation between these two technologies, present recent results, and propose future directions for research. The topics for discussion included:• How to extend IR technologies to search XML documents• How to integrate XML structure in IR indexing structures• How to query XML documents both on content and structure• How to introduce the semantics inherent in XML into the search process• How to adopt database indexing techniques in an IR frameworkThe opening session of the workshop consisted of a survey of search engines for XML documents. This was followed by three technical sessions: query languages, retrieval algorithms, and IR systems for XML documents. The final talk of the day, "Searching Annotated Language Resources in XML", by Nancy Ide was given from the perspective of potential users of XML search systems and opened many topics for discussion. The workshop was concluded with a panel discussion where the panelists outlined their vision of the future of XML search.
Mining needle in a haystack
Authors: Joshi Mahesh V. , Agarwal Ramesh C. , Kumar Vipin
Published: November 2005

Learning models to classify rarely occurring target classes is an important problem with applications in network intrusion detection, fraud detection, or deviation detection in general. In this paper, we analyze our previously proposed two-phase rule induction method in the context of learning complete and precise signatures of rare classes. The key feature of our method is that it separately conquers the objectives of achieving high recall and high precision for the given target class. The first phase of the method aims for high recall by inducing rules with high support and a reasonable level of accuracy. The second phase then tries to improve the precision by learning rules to remove false positives in the collection of the records covered by the first phase rules. Existing sequential covering techniques try to achieve high precision for each individual disjunct learned. In this paper, we claim that such approach is inadequate for rare classes, because of two problems: splintered false positives and error-prone small disjuncts. Motivated by the strengths of our two-phase design, we design various synthetic data models to identify and analyze the situations in which two state-of-the-art methods, RIPPER and C4.5 rules, either fail to learn a model or learn a very poor model. In all these situations, our two-phase approach learns a model with significantly better recall and precision levels. We also present a comparison of the three methods on a challenging real-life network intrusion detection dataset. Our method is significantly better or comparable to the best competitor in terms of achieving better balance between recall and precision.
Filtering algorithms and implementation for very fast publish/subscribe systems
Authors: Fabret Françoise , Jacobsen H. Arno , Llirbat François , Pereira Joăo , Ross Kenneth A. , Shasha Dennis
Published: November 2005

Publish/Subscribe is the paradigm in which users express long-term interests (“subscriptions”) and some agent “publishes” events (e.g., offers). The job of Publish/Subscribe software is to send events to the owners of subscriptions satisfied by those events. For example, a user subscription may consist of an interest in an airplane of a certain type, not to exceed a certain price. A published event may consist of an offer of an airplane with certain properties including price. Each subscription consists of a conjunction of (attribute, comparison operator, value) predicates. A subscription closely resembles a trigger in that it is a long-lived conditional query associated with an action (usually, informing the subscriber). However, it is less general than a trigger so novel data structures and implementations may enable the creation of more scalable, high performance publish/subscribe systems. This paper describes an attempt at the construction of such algorithms and its implementation. Using a combination of data structures, application-specific caching policies, and application-specific query processing our system can handle 600 events per second for a typical workload containing 6 million subscriptions.
Locally adaptive dimensionality reduction for indexing large time series databases
Authors: Keogh Eamonn , Chakrabarti Kaushik , Pazzani Michael , Mehrotra Sharad
Published: November 2005

Similarity search in large time series databases has attracted much research interest recently. It is a difficult problem because of the typically high dimensionality of the data.. The most promising solutions involve performing dimensionality reduction on the data, then indexing the reduced data with a multidimensional index structure. Many dimensionality reduction techniques have been proposed, including Singular Value Decomposition (SVD), the Discrete Fourier transform (DFT), and the Discrete Wavelet Transform (DWT). In this work we introduce a new dimensionality reduction technique which we call Adaptive Piecewise Constant Approximation (APCA). While previous techniques (e.g., SVD, DFT and DWT) choose a common representation for all the items in the database that minimizes the global reconstruction error, APCA approximates each time series by a set of constant value segments of varying lengths such that their individual reconstruction errors are minimal. We show how APCA can be indexed using a multidimensional index structure. We propose two distance measures in the indexed space that exploit the high fidelity of APCA for fast searching: a lower bounding Euclidean distance approximation, and a non-lower bounding, but very tight Euclidean distance approximation and show how they can support fast exact searching, and even faster approximate searching on the same index structure. We theoretically and empirically compare APCA to all the other techniques and demonstrate its superiority.
Automatic segmentation of text into structured records
Authors: Borkar Vinayak , Deshmukh Kaustubh , Sarawagi Sunita
Published: November 2005

In this paper we present a method for automatically segmenting unformatted text records into structured elements. Several useful data sources today are human-generated as continuous text whereas convenient usage requires the data to be organized as structured records. A prime motivation is the warehouse address cleaning problem of transforming dirty addresses stored in large corporate databases as a single text field into subfields like “City” and “Street”. Existing tools rely on hand-tuned, domain-specific rule-based systems.

We describe a tool DATAMOLD that learns to automatically extract structure when seeded with a small number of training examples. The tool enhances on Hidden Markov Models (HMM) to build a powerful probabilistic model that corroborates multiple sources of information including, the sequence of elements, their length distribution, distinguishing words from the vocabulary and an optional external data dictionary. Experiments on real-life datasets yielded accuracy of 90% on Asian addresses and 99% on US addresses. In contrast, existing information extraction methods based on rule-learning techniques yielded considerably lower accuracy.
Improving index performance through prefetching
Authors: Chen Shimin , Gibbons Phillip B. , Mowry Todd C.
Published: November 2005

This paper proposes and evaluate
Prefetching B
+
-
Trees
(pB
+
-Trees), which use prefetching to accelerate two important operations on B
+
-Tree indices: searches and range scans. To accelerate searches, pB
+
-Trees use prefetching to effectively create wider nodes than the natural data transfer size: e.g., eight vs. one cache lines or disk pages. These wider nodes reduce the height of the B
+
-Tree, thereby decreasing the number of expensive misses when going from parent to child without significantly increasing the cost of fetching a given node. Our results show that this technique speeds up search and update times by a factor of 1.21-1.5 for main-memory B
+
-Trees. In addition, it outperforms and is complementary to “Cache-Sensitive B
+
-Trees.” To accelerate range scans, pB
+
-Trees provide arrays of pointers to their leaf nodes. These allow the pB
+
-Tree to prefetch arbitrarily far ahead, even for nonclustered indices, thereby hiding the normally expensive cache misses associated with traversing the leaves within the range. Our results show that this technique yields over a
sixfold
speedup on range scans of 1000+ keys. Although our experimental evaluation focuses on main memory databases, the techniques that we propose are also applicable to hiding disk latency.
Query optimization in compressed database systems
Authors: Chen Zhiyuan , Gehrke Johannes , Korn Flip
Published: November 2005

Over the last decades, improvements in CPU speed have outpaced improvements in main memory and disk access rates by orders of magnitude, enabling the use of data compression techniques to improve the performance of database systems. Previous work describes the benefits of compression for numerical attributes, where data is stored in compressed format on disk. Despite the abundance of string-valued attributes in relational schemas there is little work on compression for string attributes in a database context. Moreover, none of the previous work suitably addresses the role of the query optimizer: During query execution, data is eithereagerlydecompressed when it is read into main memory, or datalazilystays compressed in main memory and is decompressed on demand only

In this paper, we present an effective approach for database compression based on lightweight, attribute-level compression techniques. We propose a IIierarchical Dictionary Encoding strategy that intelligently selects the most effective compression method for string-valued attributes. We show that eager and lazy decompression strategies produce sub-optimal plans for queries involving compressed string attributes. We then formalize the problem of compression-aware query optimization and propose one provably optimal and two fast heuristic algorithms for selecting a query plan for relational schemas with compressed attributes; our algorithms can easily be integrated into existing cost-based query optimizers. Experiments using TPC-H data demonstrate the impact of our string compression methods and show the importance of compression-aware query optimization. Our approach results in up to an order speed up over existing approaches.
Epsilon grid order
Authors: Böhm Christian , Braunmüller Bernhard , Krebs Florian , Kriegel Hans-Peter
Published: November 2005

The similarity join is an important database primitive which has been successfully applied to speed up applications such as similarity search, data analysis and data mining. The similarity join combines two point sets of a multidimensional vector space such that the result contains all point pairs where the distance does not exceed a parameter ε. In this paper, we propose the Epsilon Grid Order, a new algorithm for determining the similarity join of very large data sets. Our solution is based on a particular sort order of the data points, which is obtained by laying an equi-distant grid with cell length ε over the data space and comparing the grid cells lexicographically. A typical problem of grid-based approaches such as MSJ or the ε-kdB-tree is that large portions of the data sets must be held simultaneously in main memory. Therefore, these approaches do not scale to large data sets. Our technique avoids this problem by an external sorting algorithm and a particular scheduling strategy during the join phase. In the experimental evaluation, a substantial improvement over competitive techniques is shown.
Lifestreams
Authors: Freeman Eric , Gelernter David
Published: November 2005

Conventional software systems, such as those based on the “desktop metaphor,” are ill-equipped to manage the electronic information and events of the typical computer user. We introduce a new metaphor,
Lifestreams,
for dynamically organizing a user's personal workspace. Lifestreams uses a simple organizational metaphor, a time-ordered stream of documents, as an underlying storage system. Stream filters are used to organize, monitor and summarize information for the user. Combined, they provide a system that subsumes many separate desktop applications. This paper describes the Lifestreams model and our prototype system.
GESTALT
Authors: Heytens Michael L. , Nikhil Rishiyur S.
Published: November 2005

Many new database applications require computational and data modelling power simply not present in conventional database management systems. Developers are forced to design complex encodings of complex data into a limited set of database types, and to embed DML commands into a host programming language, a notoriously tricky and error-prone enterprise.

In this paper, we describe the design and implementation of GESTALT, a system and methodology for organizing and interfacing to multiple heterogeneous, existing database systems. Application programs are written in a supported programming language (currently C and Lisp) using high-level data and control abstractions native to the language. The system is flexible in that the underlying database systems can easily be replaced/upgraded/augmented without affecting existing application programs.

We also describe our experience with the system: GESTALT has been in daily operational use at MIT for over a year, supporting an information system for CAF, a research facility for the automation of semiconductor fabrication.
Nulls in relational databases
Authors: Kocharekar Raju
Published: November 2005

This paper discusses the semantic issues related to null values problem in relational databases. We argue that the proposed set of maybe operations with the three valued logic is still not adequate and needs further enhancements.
The implication problem for inclusion dependencies
Authors: Missaoui Rokia , Godin Robert
Published: November 2005

In this paper, we propose a graph theoretic approach to deal with the implication problem for inclusion dependencies. By analogy with functional dependencies, we define and present algorithms for computing the following concepts: the closure of a relation scheme R for X according to a set of inclusion dependencies and the minimal cover for inclusion dependencies.
Distributed logging for transaction processing
Authors: Daniels Dean S. , Spector Alfred Z. , Thompson Dean S.
Published: November 2005

Increased interest in using workstations and small processors for distributed transaction processing raises the question of how to implement the logs needed for transaction recovery. Although logs can be implemented with data written to duplexed disks on each processing node, this paper argues there are advantages if log data is written to multiple
log server
nodes. A simple analysis of expected logging loads leads to the conclusion that a high performance, microprocessor based processing node can support a log server if it uses efficient communication protocols and low latency, non volatile storage to buffer log data. The buffer is needed to reduce the processing time per log record and to increase throughput to the logging disk. An interface to the log servers using simple, robust, and efficient protocols is presented. Also described are the disk data structures that the log servers use. This paper concludes with a brief discussion of remaining design issues, the status of a prototype implementation, and plans for its completion.
Programming constructs for database system implementation in EXODUS
Authors: Richardson Joel E. , Carey Michael J.
Published: November 2005

The goal of the EXODUS extensible DBMS project is to enable the rapid development of a wide spectrum of high-performance, application-specific database systems EXODUS provides certain kernel facilities for use by all applications and a set of tools to aid the database implementor (DBI) in generating new database system software. Some of the DBI's work is supported by EXODUS tools which generate database components from a specification. However, components such as new abstract data types, access methods, and database operations must be explicitly coded by the DBI. This paper analyzes the major programming problems faced by the DBI, describing the collection of programming language constructs that EXODUS provides for simplifying the DBI's task. These constructs have been embedded in the E programming language, an extension of C++ designed specifically for implementing DBMS software.
An object-oriented system for engineering applications
Authors: Kemper Alfons , Lockemann Peter C. , Wallrath Mechtild
Published: November 2005

One of the most promising approaches to database support of engineering applications is the concept of object-oriented database management. Object-orientation is usually approached from either a behavioral or structural viewpoint. The former emphasizes the application-specific manipulation of technical objects while hiding their structural details whereas the latter concentrates on the structural aspects and their efficient implementation. The thesis of the paper is that the two viewpoints may enter into a fruitful symbiosis where a behaviorally object-oriented system is implemented on top of a structurally object-oriented database system, thereby combining ease of use by the engineer with high database system performance. The thesis will be demonstrated in the paper by a user-friendly interface based on user-definable abstract datatypes and its implementation using a prototype for the non-first-normal-form (NF
2
) relational model, and will be supported by an engineering example application from off-line robot programming.
Semantics and implementation of schema evolution in object-oriented databases
Authors: Banerjee Jay , Kim Won , Kim Hyoung-Joo , Korth Henry F.
Published: November 2005

Object-oriented programming is well-suited to such data-intensive application domains as CAD/CAM, AI, and OIS (office information systems) with multimedia documents. At MCC we have built a prototype object-oriented database system, called ORION. It adds persistence and sharability to objects created and manipulated in applications implemented in an object-oriented programming environment. One of the important requirements of these applications is schema evolution, that is, the ability to dynamically make a wide variety of changes to the database schema. In this paper, following a brief review of the object-oriented data model that we support in ORION, we establish a framework for supporting schema evolution, define the semantics of schema evolution, and discuss its implementation.
Concurrency control for distributed real-time databases
Authors: Sha Lui , Rajkumar Ragunathan , Lehooczky John P.
Published: November 2005

The concurrency control of transactions in a real-time database must satisfy not only the consistency constraints of the database but also the timing constraints of individual transactions. In this paper, we present a real-time concurrency control protocol that can be used in a distributed and decomposable real-time database. The protocol is based on the integration of a modular concurrency control theory with a real-time scheduling protocol called the priority ceiling protocol. This protocol supports the replication of data objects and avoids the formation of deadlocks. Finally, an analysis of the performance of this protocol is presented.
Contracting in the days of eBusiness
Authors: Hümmer W. , Lehner W. , Wedekind H.
Published: November 2005

Putting electronic business on a sound foundation --- model theoretically as well as technologically --- has to be seen as a central challenge for research as well as for commercial development. This paper concentrates on the discovery and the negotiation phase of concluding an agreement based on a contract. We present a methodology how to come seamlessly from a many-to-many relationship in the discovery phase to a one-to-one relationship in the contract negotiation phase. Making the content of the contracts persistent is achieved by reconstructing contract templates by means of mereologic (logic of the whole-part relation). Possibly nested sub-structures of the contract template are taken as a basis for negotiation in a dialogical way. For the negotiation itself the contract templates are extended by implications (logical) and sequences (topical).
Conceptual modeling and specification generation for B2B business processes based on ebXML
Authors: Kim HyoungDo
Published: November 2005

In order to support dynamic setup of business processes among independent organizations, a formal standard schema for describing the business processes is basically required. The ebXML framework provides such a specification schema called BPSS (Business Process Specification Schema) which is available in two stand-alone representations: a UML version, and an XML version. The former, however, is not intended for the direct creation of business process specifications, but for defining specification elements and their relationships required for creating an ebXML-compliant business process specification. For this reason, it is very important to support conceptual modeling that is well organized and directly matched with major modeling concepts. This paper deals with how to represent and manage B2B business processes using UML-compliant diagrams. The major challenge is to organize UML diagrams in a natural way that is well suited with the business process meta-model and then to transform the diagrams into an XML version. This paper demonstrates the usefulness of conceptually modeling business processes by prototyping a business process editor tool called ebDesigner.
Semantic B2B integration
Authors: Cui Zhan , Jones Dean , O'Brien Paul
Published: November 2005

Solving queries to support e-commerce transactions can involve retrieving and integrating information from multiple information resources. Often, users don't care which resources are used to answer their query. In such situations, the ideal solution would be to hide from the user the details of the resources involved in solving a particular query. An example would be providing seamless access to a set of heterogeneous electronic product catalogues. There are many problems that must be addressed before such a solution can be provided. In this paper, we discuss a number of these problems, indicate how we have addressed these and go on to describe the proof-of-concept demonstration system we have developed.
Business data management for business-to-business electronic commerce
Authors: Quix Christoph , Schoop Mareike , Jeusfeld Manfred
Published: November 2005

Business-to-business electronic commerce (B2B EC) opens up new possibilities of trade. For example, new business partners from around the globe can be found, their offers can be compared, even complex negotiations can be conducted electronically, and a contract can be drawn up and fulfilled via an electronic marketplace. However, a sophisticated data management is required to provide such factilities. In this paper, the results of a multi-national project on creating a business-to-business electronic marketplace for small and medium-sized enterprises are presented. Tools for information discovery, protocol-based negotiations, and monitored contract enactment are provided and based on a business data repository. The repository integrates heterogeneous business data with business communication. Specific problems such as multi-linguality, data ownership, and traceability of contracts and related negotiations are addressed and it will be shown that the present approach provides efficient business data management for B2B EC.
Supply chain infrastructures
Authors: Ball Michael O. , Ma Meng , Raschid Louiqa , Zhao Zhengying
Published: November 2005

The need for supply chain integration (SCI) methodologies has been increasing as a consequence of the globalization of production and sales, and the advancement of enabling information technologies. In this paper, we describe our experience with implementing and modeling SCIs. We present the integration architecture and the software components of our prototype implementation. We then discuss a variety of information sharing methodologies. Then, within the framework of a multi-echelon supply chain process model spanning multiple organizations, we summarize research on the benefits of intra-organizational knowledge sharing, and we discuss performance scalability.
Investigating XQuery for querying across database object types
Authors: Wiegand Nancy
Published: November 2005

In addition to facilitating querying over the Web, XML query languages may provide high level constructs for useful facilities in traditional DBMSs that do not currently exist. In particular, current DBMS query languages do not allow querying across database object types to yield heterogeneous results. This paper motivates the usefulness of heterogeneous querying in traditional DBMSs and investigates XQuery, an emerging standard for XML query languages, to express such queries. The usefulness of querying and storing heterogeneous types is also applied to XML data within a Web information system.