bluuebunny/crossref_metadata_2025 huggingface dataset:
Provision of market services for eCo compliant electronic marketplaces
Authors: Arpinar Sena , Dogac Asuman
Published: November 2005

The progress and wider dissemination of electronic commerce will be facilitated through interoperability infrastructures. Commerce Net's eCo framework is a promising effort in this direction. In the eCo framework, businesses participate in a marketplace through standard interfaces for their services and by exchanging standardized documents. This framework does not specify any further interfaces for the services a marketplace itself may offer.In this paper, we demonstrate that a rich set of marketplace-specific services such as automated discovery of the needed services, comparison shopping, and negotiation can be offered to market participants by introducing a marketplace as an eCo business. For this purpose, a previously developed marketplace, namely MOPPET, is made eCo-compliant. We demonstrate that introducing MOPPET as an eCo business increases the functionality of the eCo market in the sense that several market specific services become available to the market participants.
Constraint databases
Authors: Van den Bussche Jan
Published: November 2005

We give a tutorial introduction to the basic definitions surrounding the idea of constraint databases, and survey and indicate some of the achieved research results on this subject. This paper is not written as a scholarly piece, nor as polished course notes, but rather as something like the transcript of an invited talk I gave at a meeting bringing together researchers from finite model theory, database theory, and computer-aided verification, which was held at Schloss Dagstuhl in October 1999.Very recently the first book on the subject appeared [20]. It covers the state of the art in constraint databases up to, say, mid 1999 [20]. You should see this paper merely as an appetizer for the book. I will also not try to be complete in my bibliographical references. Again, see the book for that.
Research and practice in federated information systems
Authors: Hasselbring W. , van den Heuvel W.-J. , Houben G. J. , Kutsche R.-D. , Rieger B. , Roantree M. , Subieta K.
Published: November 2005

EFIS 2000 was held at Dublin City University in June 2000. The principal aim of this third workshop was to bring together new insights from academic research with industry-driven developments and perspectives in the area of federated information systems. This report describes the observations of the workshop together with the outcome and future research possibilities.
EIHA?!?
Authors: Biancheri Chiara , Pazzaglia Jean-Christophe , Paddeu Gavino
Published: November 2005

The exponential growth of resources on the web, and the wide deployment of devices for multimodal access to the Internet, lead to new problems in information management. In this context, and as part of the European project Vision, we have built an interactive telematic handbook of the culture and the territory of Sardinia. A team of cultural experts browsed the web to get a large collection of Internet resources.The system built for the management of this data uses emerging Internet technologies such as the XML language suite and its applications. The result obtained is a multimodal service, called
Eiha
?!?, available through PCs and mobile phones.
Querying multi-dimensional data indexed using the Hilbert space-filling curve
Authors: Lawder J. K. , King P. J. H.
Published: November 2005

Mapping to one-dimensional values and then using a one-dimensional indexing method has been proposed as a way of indexing multi-dimensional data. Most previous related work uses the Z-Order Curve but more recently the Hilbert Curve has been considered since it has superior clustering properties. Any approach, however, can only be of practical value if there are effective methods for executing range and partial match queries. This paper describes such a method for the Hilbert Curve.
Report on the fourth international conference on flexible query answering systems (FQAS 2000)
Authors: Bosc Patrick , Motro Amihai , Pasi Gabriella
Published: November 2005

The fourth International Conference on Flexible Query Answering Systems (FQAS'2000) was held at the Academy of Sciences in Warsaw, Poland on October, 25-27, 2000. This series of conferences was launched in 1994 by Troels Andreasen, Henning Christiansen and Henrik Larsen from Roskilde University in Denmark, who have been the main driving force behind this series ever since. The previous FQAS events were held in Denmark in 1994, 1996, mad 1998. The next conference in this series will return to Denmark in 2002.This conference provides an opportunity for researchers, developers and practitioners to explore new ideas and approaches in a multidisciplinary forum to the aim of providing effective solutions to the problem of easy, flexible and intuitive access to electronically stored information. The focus of this conference is to add flexibility to the systems for the storage and access to information; as there exist several classes of such systems, the conference draws on several research areas, including information retrieval, database management, knowledge representation, multimedia systems and human-computer interaction.As a paradigm for flexible query answering we may think about an expert human intermediary who is able to analyze users information needs and to evaluate the relevant information items from the available information sources. The knowledge on the information sources and the capability to interpret the user requests enable the expert to perform a good estimate of the items possibly satisfying the users needs, though the query, per se, may be imprecise, incomplete, etc. Thus, one of the key issues for defining flexible query answering system is the tolerance to imprecision and uncertainty in the formulation of user queries as well as in the representation of information.The conference brought together more than 70 researchers and developers working in the area of information technology. The conference program included five invited talks, a keynote speech and 12 technical sessions. There was a total of 55 reviewed papers included in the technical sessions.In the proceedings, the contributions are gathered according to 6 main topics, each one corresponding to one or more technical sessions. These principal themes are the following: Flexibility in Database Management and Querying, Information Retrieval, Knowledge Representation and Reasoning, Natural Language and Multimedia Processing, Acquisition of Data and Knowledge, Cyberspace and distributed data.The rest of this report provides a brief summary of the three main thematic areas.
SQL and management of external data
Authors: Melton Jim , Michels Jan-Eike , Josifovski Vanja , Kulkarni Krishna , Schwarz Peter , Zeidenstein Kathy
Published: November 2005

In late 2000, work was completed on yet another part of the SQL standard [1], to which we introduced our readers in an earlier edition of this column [2].Although SQL database systems manage an enormous amount of data, it certainly has no monopoly on that task. Tremendous amounts of data remain in ordinary operating system files, in network and hierarchical databases, and in other repositories. The need to query and manipulate that data alongside SQL data continues to grow. Database system vendors have developed many approaches to providing such integrated access.In this (partly guested) article, SQL's new part, Management of External Data (SQL/MED), is explored to give readers a better notion of just how applications can use standard SQL to concurrently access their SQL data and their non-SQL data.
The Clio project
Authors: Miller Renée J. , Hernández Mauricio A. , Haas Laura M. , Yan Lingling , Howard Ho C. T. , Fagin Ronald , Popa Lucian
Published: November 2005

Clio is a system for managing and facilitating the complex tasks of heterogeneous data transformation and integration. In Clio, we have collected together a powerful set of data management techniques that have proven invaluable in tackling these difficult problems. In this paper, we present the underlying themes of our approach and present a brief case study.
Iceberg-cube computation with PC clusters
Authors: Ng Raymond T. , Wagner Alan , Yin Yu
Published: November 2005

In this paper, we investigate the approach of using low cost PC cluster to parallelize the computation of iceberg-cube queries. We concentrate on techniques directed towards online querying of large, high-dimensional datasets where it is assumed that the total cube has net been precomputed. The algorithmic space we explore considers trade-offs between parallelism, computation and I/0. Our main contribution is the development and a comprehensive evaluation of various novel, parallel algorithms. Specifically: (1) Algorithm RP is a straightforward parallel version of BUC [BR99]; (2) Algorithm BPP attempts to reduce I/0 by outputting results in a more efficient way; (3) Algorithm ASL, which maintains cells in a cuboid in a skiplist, is designed to put the utmost priority on load balancing; and (4) alternatively, Algorithm PT load-balances by using binary partitioning to divide the cube lattice as evenly as possible.

We present a thorough performance evaluation on all these algorithms on a variety of parameters, including the dimensionality of the cube, the sparseness of the cube, the selectivity of the constraints, the number of processors, and the size of the dataset. A key finding is that it is not a one-algorithm-fit-all situation. We recommend a “recipe” which uses PT as the default algorithm, but may also deploy ASL under specific circumstances.
Outlier detection for high dimensional data
Authors: Aggarwal Charu C. , Yu Philip S.
Published: November 2005

The outlier detection problem has important applications in the field of fraud detection, network robustness analysis, and intrusion detection. Most such applications are high dimensional domains in which the data can contain hundreds of dimensions. Many recent algorithms use concepts of proximity in order to find outliers based on their relationship to the rest of the data. However, in high dimensional space, the data is sparse and the notion of proximity fails to retain its meaningfulness. In fact, the sparsity of high dimensional data implies that every point is an almost equally good outlier from the perspective of proximity-based definitions. Consequently, for high dimensional data, the notion of finding meaningful outliers becomes substantially more complex and non-obvious. In this paper, we discuss new techniques for outlier detection which find the outliers by studying the behavior of projections from the data set.
Adaptable query optimization and evaluation in temporal middleware
Authors: Slivinskas Giedrius , Jensen Christian S. , Snodgrass Richard Thomas
Published: November 2005

Time-referenced data are pervasive in most real-world databases. Recent advances in temporal query languages show that such database applications may benefit substantially from built-in temporal support in the DBMS. To achieve this, temporal query optimization and evaluation mechanisms must be provided, either within the DBMS proper or as a source level translation from temporal queries to conventional SQL. This paper proposes a new approach: using a middleware component on top of a conventional DBMS. This component accepts temporal SQL statements and produces a corresponding query plan consisting of algebraic as well as regular SQL parts. The algebraic parts are processed by the middleware, while the SQL parts are processed by the DBMS. The middleware uses performance feedback from the DBMS to adapt its partitioning of subsequent queries into middleware and DBMS parts. The paper describes the architecture and implementation of the temporal middleware component, termed TANGO, which is based on the Volcano extensible query optimizer and the XXL query processing library. Experiments with the system demonstrate the utility of the middleware's internal processing capability and its cost-based mechanism for apportioning the processing between the middleware and the underlying DBMS.
Efficient and effective metasearch for text databases incorporating linkages among documents
Authors: Yu Clement , Meng Weiyi , Wu Wensheng , Liu King-Lup
Published: November 2005

Linkages among documents have a significant impact on the importance of documents, as it can be argued that important documents are pointed to by many documents or by other important documents. Metasearch engines can be used to facilitate ordinary users for retrieving information from multiple local sources (text databases). There is a search engine associated with each database. In a large-scale metasearch engine, the contents of each local database is represented by a representative. Each user query is evaluated against he set of representatives of all databases in order to determine the appropriate databases (search engines) to search (invoke) In previous word, the linkage information between documents has not been utilized in determining the appropriate databases to search. In this paper, such information is employed to determine the degree of relevance of a document with respect to a given query. Specifically, the importance (rank) of each document as determined by the linkages is integrated in each database representative to facilitate the selection of databases for each given query. We establish a necessary and sufficient condition to rank databases optimally, while incorporating the linkage information. A method is provided to estimate the desired quantities stated in the necessary and sufficient condition. The estimation method runs in time linearly proportional to the number of query terms. Experimental results are provided to demonstrate the high retrieval effectiveness of the method.
STHoles
Authors: Bruno Nicolas , Chaudhuri Surajit , Gravano Luis
Published: November 2005

Attributes of a relation are not typically independent. Multidimensional histograms can be an effective tool for accurate multiattribute query selectivity estimation. In this paper, we introduce
STHoles
, a “workload-aware” histogram that allows bucket nesting to capture data regions with reasonably uniform tuple density.
STHoles
histograms are built without examining the data sets, but rather by just analyzing query results. Buckets are allocated where needed the most as indicated by the workload, which leads to accurate query selectivity estimations. Our extensive experiments demonstrate that
STHoles
histograms consistently produce good selectivity estimates across synthetic and real-world data sets and across query workloads, and, in many cases, outperform the best multidimensional histogram techniques that require access to and processing of the full data sets during histogram construction.
Global optimization of histograms
Authors: Jagadish H. V. , Jin Hui , Ooi Beng Chin , Tan Kian-Lee
Published: November 2005

Histograms are frequently used to represent the distribution of data values in an attribute of a relation. Most previous work has focused on identifying the optimal histogram (given a limited number of buckets) for a single attribute
independent of other attributes/histograms
. In this paper, we propose the idea of
global optimization of histograms
, i.e., single-attribute histograms for a set of attributes are optimized collectively so as to minimize the overall error in using the histograms. The idea is to allocate more buckets to histograms whose attributes are more frequently used and/or distributions are highly skewed. While the accuracy of some histograms is penalized (being assigned fewer buckets), we expect the global error to be low compared to the traditional method (of allocating equal number of buckets to each histogram).

We propose two algorithms to determine the histograms to construct for a collection of attributes. The first is based on dynamic programming, and the second is a greedy algorithm. We compare the overall error of these algorithms against the traditional method. Extensive experiments are conducted and the results confirm the benefits of global optimal histograms in reducing the overall error. The extent of improvement depends on the data and query distributions, ranging from no benefit when there is no significant differences in the data distributions to over a factor of 100 reduction in error in some cases we tried.

The time to compute global optimal histogram using dynamic programming is much longer than the time to compute optimal histograms separately for each attribute, and the difference widens at a faster rate as the number of histograms increases. With the greedy algorithm, the time penalty is small, but the error reduction is somewhat less as well. We propose a third algorithm, called greedy algorithm with remedy, that has running time similar to the greedy algorithm, but produces results close to global optimum. In fact, in every experiment that we tried, this algorithm found the exact global optimum.
Efficient and tumble similar set retrieval
Authors: Gionis Aristides , Gunopulos Dimitrios , Koudas Nick
Published: November 2005

Set value attributes are a concise and natural way to model complex data sets. Modern Object Relational systems support set value attributes and allow various query capabilities on them. In this paper we initiate a formal study of indexing techniques for set value attributes based on similarity, for suitably defined notions of similarity between sets. Such techniques are necessary in modern applications such as recommendations through collaborative filtering and automated advertising. Our techniques are probabilistic and approximate in nature. As a design principle we create structures that make use of well known and widely used data structuring techniques, as a means to ease integration with existing infrastructure.

We show how the problem of indexing a collection of sets based on similarity can be reduced to the problem of indexing suitably encoded (in a way that preserves similarity) binary vectors in Hamming space thus, reducing the problem to one of similarity query processing in Hamming space. Then, we introduce and analyze two data structure primitives that we use in cooperation to perform similarity query processing in a Hamming space. We show how the resulting indexing technique can be optimized for properties of interest by formulating constraint optimization problems based on the space one is willing to devote for indexing. Finally we present experimental results from a prototype implementation of our techniques using real life datasets exploring the accuracy and efficiency of our overall approach as well as the quality of our solutions to problems related to the optimization of the indexing scheme.
PREFER
Authors: Hristidis Vagelis , Koudas Nick , Papakonstantinou Yannis
Published: November 2005

Users often need to optimize the selection of objects by appropriately weighting the importance of multiple object attributes. Such optimization problems appear often in operations' research and applied mathematics as well as everyday life; e.g., a buyer may select a home as a weighted function of a number of attributes like its distance from office, its price, its area, etc.

We capture such queries in our definition of preference queries that use a weight function over a relation's attributes to derive a score for each tuple. Database systems cannot efficiently produce the top results of a preference query because they need to evaluate the weight function over all tuples of the relation. PREFER answers preference queries efficiently by using materialized views that have been pre-processed and stored.

We first show how the result of a preference query can be produced in a pipelined fashion using a materialized view. Then we show that excellent performance can be delivered given a reasonable number of materialized views and we provide an algorithm that selects a number of views to precompute and materialize given space constraints.

We have implemented the algorithms proposed in this paper in a prototype system called PREFER, which operates on top of a commercial database management system. We present the results of a performance comparison, comparing our algorithms with prior approaches using synthetic datasets. Our results indicate that the proposed algorithms are superior in performance compared to other approaches, both in preprocessing (preparation of materialized views) as well as execution time.
SPARTAN
Authors: Babu Shivnath , Garofalakis Minos , Rastogi Rajeev
Published: November 2005

While a variety of lossy compression schemes have been developed for certain forms of digital data (e.g., images, audio, video), the area of lossy compression techniques for arbitrary data tables has been left relatively unexplored. Nevertheless, such techniques are clearly motivated by the ever-increasing data collection rates of modern enterprises and the need for effective, guaranteed-quality approximate answers to queries over massive relational data sets. In this paper, we propose
SPARTAN
, a system that takes advantage of attribute semantics and data-mining models to perform lossy compression of massive data tables.
SPARTAN
is based on the novel idea of exploiting predictive data correlations and prescribed error tolerances for individual attributes to construct concise and accurate
Classification and Regression Tree (CaRT)
models for entire columns of a table. More precisely,
SPARTAN
selects a certain subset of attributes for which no values are explicitly stored in the compressed table; instead, concise CaRTs that predict these values (within the prescribed error bounds) are maintained. To restrict the huge search space and construction cost of possible CaRT predictors,
SPARTAN
employs sophisticated learning techniques and novel combinatorial optimization algorithms. Our experimentation with several real-life data sets offers convincing evidence of the effectiveness of
SPARTAN
's model-based approach —
SPARTAN
is able to consistently yield substantially better compression ratios than existing semantic or syntactic compression tools (e.g., gzip) while utilizing only small data samples for model inference.
Materialized view selection and maintenance using multi-query optimization
Authors: Mistry Hoshi , Roy Prasan , Sudarshan S. , Ramamritham Krithi
Published: November 2005

Materialized views have been found to be very effective at speeding up queries, and are increasingly being supported by commercial databases and data warehouse systems. However, whereas the amount of data entering a warehouse and the number of materialized views are rapidly increasing, the time window available for maintaining materialized views is shrinking. These trends necessitate efficient techniques for the maintenance of materialized views.

In this paper, we show how to find an efficient plan for the maintenance of a
set of materialized views
, by exploiting common subexpressions between different view maintenance expressions. In particular, we show how to efficiently select (a) expressions and indices that can be effectively shared, by
transient materialization
; (b) additional expressions and indices for
permanent materialization
; and (c) the best maintenance plan —
incremental
or
recomputation
— for each view. These three decisions are highly interdependent, and the choice of one affects the choice of the others. We develop a framework that cleanly integrates the various choices in a systematic and efficient manner. Our evaluations show that many-fold improvement in view maintenance time can be achieved using our techniques. Our algorithms can also be used to efficiently select materialized views to speed up workloads containing queries and updates.
Optimizing queries using materialized views
Authors: Goldstein Jonathan , Larson Per-Åke
Published: November 2005

Materialized views can provide massive improvements in query processing time, especially for aggregation queries over large tables. To realize this potential, the query optimizer must know how and when to exploit materialized views. This paper presents a fast and scalable algorithm for determining whether part or all of a query can be computed from materialized views and describes how it can be incorporated in transformation-based optimizers. The current version handles views composed of selections, joins and a final group-by. Optimization remains fully cost based, that is, a single “best” rewrite is not selected by heuristic rules but multiple rewrites are generated and the optimizer chooses the best alternative in the normal way. Experimental results based on an implementation in Microsoft SQL Server show outstanding performance and scalability. Optimization time increases slowly with the number of views but remains low even up to a thousand.
Adaptive precision setting for cached approximate values
Authors: Olston Chris , Loo Boon Thau , Widom Jennifer
Published: November 2005

Caching approximate values instead of exact values presents an opportunity for performance gains in exchange for decreased precision. To maximize the performance improvement, cached approximations must be of appropriate precision: approximations that are too precise easily become invalid, requiring frequent refreshing, while overly imprecise approximations are likely to be useless to applications, which must then bypass the cache. We present a parameterized algorithm for adjusting the precision of cached approximations adaptively to achieve the best performance as data values, precision requirements, or workload vary. We consider interval approximations to numeric values but our ideas can be extended to other kinds of data and approximations. Our algorithm strictly generalizes previous adaptive caching algorithms for exact copies: we can set parameters to require that all approximations be exact, in which case our algorithm dynamically chooses whether or not to cache each data value.

We have implemented our algorithm and tested it on synthetic and real-world data. A number of experimental results are reported, showing the effectiveness of our algorithm at maximizing performance, and also showing that in the special case of exact caching our algorithm performs as well as previous algorithms. In cases where bounded imprecision is acceptable, our algorithm easily outperforms previous algorithms for exact caching.
Proxy-server architectures for OLAP
Authors: Kalnis Panos , Papadias Dimitris
Published: November 2005

Data warehouses have been successfully employed for assisting decision making by offering a global view of the enterprise data and providing mechanisms for On-Line Analytical processing. Traditionally, data warehouses are utilized within the limits of an enterprise or organization. The growth of Internet and WWW however, has created new opportunities for data sharing among ad-hoc, geographically spanned and possibly mobile users. Since it is impractical for each enterprise to set up a worldwide infrastructure, currently such applications are handled by the central warehouse. This often yields poor performance, due to overloading of the central server and low transfer rate of the network.

In this paper we propose an architecture for OLAP cache servers (OCS). An OCS is the equivalent of a proxy-server for web documents, but it is designed to accommodate data from warehouses and support OLAP operations. We allow numerous OCSs to be connected via an arbitrary network, and present a centralized, a semi-centralized and an autonomous control policy. We experimentally evaluate these policies and compare the performance gain against the existing systems where caching is performed only at the client side. Our architecture offers increased autonomy at remote clients, substantial network traffic savings, better scalability, lower response time and is complementary both to existing OLAP cache systems and distributed OLAP approaches.
Modeling high-dimensional index structures using sampling
Authors: Lang Christian A. , Singh Ambuj K.
Published: November 2005

A large number of index structures for high-dimensional data have been proposed previously. In order to tune and compare such index structures, it is vital to have efficient cost prediction techniques for these structures. Previous techniques either assume uniformity of the data or are not applicable to high-dimensional data. We propose the use of sampling to predict the number of accessed index pages during a query execution. Sampling is independent of the dimensionality and preserves clusters which is important for representing skewed data. We present a general model for estimating the index page layout using sampling and show how to compensate for errors. We then give an implementation of our model under restricted memory assumptions and show that it performs well even under these constraints. Errors are minimal and the overall prediction time is up to two orders of magnitude below the time for building and probing the full index without sampling.
Progressive approximate aggregate queries with a multi-resolution tree structure
Authors: Lazaridis Iosif , Mehrotra Sharad
Published: November 2005

Answering aggregate queries like
SUM
,
COUNT
,
MIN
,
MAX
,
AVG
in an approximate manner is often desirable when the exact answer is not needed or too costly to compute. We present an algorithm for answering such queries in multi-dimensional databases, using selective traversal of a Multi-Resolution Aggregate (MRA) tree structure storing point data. Our approach provides 100% intervals of confidence on the value of the aggregate and works iteratively, coming up with improving quality answers, until some error requirement is satisfied or time constraint as reached. Using the same technique we can also answer aggregate queries exactly and our experiments indicate that even for exact answering the proposed data structure and algorithm are very fast.
On supporting containment queries in relational database management systems
Authors: Zhang Chun , Naughton Jeffrey , DeWitt David , Luo Qiong , Lohman Guy
Published: November 2005

Virtually all proposals for querying XML include a class of query we term “containment queries”. It is also clear that in the foreseeable future, a substantial amount of XML data will be stored in relational database systems. This raises the question of how to support these containment queries. The inverted list technology that underlies much of Information Retrieval is well-suited to these queries, but should we implement this technology (a) in a separate loosely-coupled IR engine, or (b) using the native tables and query execution machinery of the RDBMS? With option (b), more than twenty years of work on RDBMS query optimization, query execution, scalability, and concurrency control and recovery immediately extend to the queries and structures that implement these new operations. But all this will be irrelevant if the performance of option (b) lags that of (a) by too much. In this paper, we explore some performance implications of both options using native implementations in two commercial relational database systems and in a special purpose inverted list engine. Our performance study shows that while RDBMSs are generally poorly suited for such queries, under conditions they can outperform an inverted list engine. Our analysis further identifies two significant causes that differentiate the performance of the IR and RDBMS implementations: the join algorithms employed and the hardware cache utilization. Our results suggest that contrary to most expectations, with some modifications, a native implementations in an RDBMS can support this class of query much more efficiently.
Minimization of tree pattern queries
Authors: Amer-Yahia Sihem , Cho SungRan , Lakshmanan Laks V. S. , Srivastava Divesh
Published: November 2005

Tree patterns forms a natural basis to query tree-structured data such as XML and LDAP. Since the efficiency of tree pattern matching against a tree-structured database depends on the size of the pattern, it is essential to identify and eliminate redundant nodes in the pattern and do so as quickly as possible. In this paper, we study tree pattern minimization both in the absence and in the presence of integrity constraints (ICs) on the underlying tree-structured database.

When no ICs are considered, we call the process of minimizing a tree pattern, constraint-independent minimization. We develop a polynomial time algorithm called CIM for this purpose. CIM's efficiency stems from two key properties: (i) a node cannot be redundant unless its children are, and (ii) the order of elimination of redundant nodes is immaterial. When ICs are considered for minimization, we refer to it as constraint-dependent minimization. For tree-structured databases, required child/descendant and type co-occurrence ICs are very natural. Under such ICs, we show that the minimal equivalent query is unique. We show the surprising result that the algorithm obtained by first augmenting the tree pattern using ICS, and then applying CIM, always finds the unique minimal equivalent query; we refer to this algorithm as ACIM. While ACIM is also polynomial time, it can be expensive in practice because of its inherent non-locality. We then present a fast algorithm, CDM, that identifies and eliminates local redundancies due to ICs, based on propagating “information labels” up the tree pattern. CDM can be applied prior to ACIM for improving the minimization efficiency. We complement our analytical results with an experimental study that shows the effectiveness of our tree pattern minimization techniques.
StorHouse metanoia - new applications for database, storage & data warehousing
Authors: Cariño Felipe , Kostamaa Pekka , Kaufmann Art , Burgess John
Published: November 2005

This paper describes the StorHouse/Relational Manager (RM) database system that uses and exploits an
active storage hierarchy
. By active storage hierarchy, we mean that StorHouse/RM executes SQL queries
directly
against data stored on all hierarchical storage (i.e. disk, optical, and tape) without post processing a file or a DBA having to manage a data set. We describe and analyze StorHouse/RM features and internals. We also describe how StorHouse/RM differs from traditional HSM (Hierarchical Storage Management) systems. For commercial applications we describe an evolution to the Data Warehouse concept, called
Atomic Data Store
, whereby atomic data is stored in the database system. Atomic data is defined as storing
all
the historic data values and executing queries against them. We also describe a
Hub-and-Spoke Data Warehouse architecture
, which is used to feed or fuel data into Data Marts.

Furthermore, we provide analysis how StorHouse/RM can be
federated
with DB2, Oracle and Microsoft SQL Server 7 (SS7) and thus provide these databases an active storage hierarchy (i.e. tape). We then show two federated data modeling techniques (a) logical horizontal partitioning (LHP) of tuples and (b) logical vertical partitioning (LVP) of columns to demonstrate our database extension capabilities. We conclude with a TPC-like performance analysis of data stored on tape and disk.
The network is the database
Authors: Navas Julio C. , Wynblatt Michael
Published: November 2005

This paper describes the methodology and implementation of a data management system for highly distributed systems, which was built to solve the scalability and reliability problems faced in a wide area postal logistics application developed at Siemens. The core of the approach is to borrow from Internet routing protocols, and their proven scalability and robustness, to build a network-embedded dynamic database index, and to augment schema definition to optimize the use of this index. The system was developed with an eye toward future applications in the area of sensor networks.
The nimble integration engine
Authors: Draper Denise , Halevy Alon Y. , Weld Daniel S.
Published: November 2005

The consensus that XML has become the
de facto
standard for data interchange will spur demand for technology that allows users to integrate data from a variety of applications, repositories, and legacy systems which are located across the corporate intranet or at partner companies on the Internet.

In the past two years, Nimble Technology has developed a product for this market. Spawned from over a person-decade of data integration research, the product has been deployed at several Fortune-500 beta-customer sites. This abstract reports on the key challenges we faced in the design of our product and highlights some issues we think require more attention from the research community.
Orthogonal optimization of subqueries and aggregation
Authors: Galindo-Legaria César , Joshi Milind
Published: November 2005

There is considerable overlap between strategies proposed for subquery evaluation, and those for grouping and aggregation. In this paper we show how a number of small, independent primitives generate a rich set of efficient execution strategies —covering standard proposals for subquery evaluation suggested in earlier literature. These small primitives fall into two main, orthogonal areas: Correlation removal, and efficient processing of outerjoins and GroupBy. An optimization approach based on these pieces provides syntax-independence of query processing with respect to subqueries, i. e. equivalent queries written with or without subquery produce the same efficient plan.

We describe techniques implemented in Microsoft SQL Server (releases 7.0 and 8.0) for queries containing sub-queries and/or aggregations, based on a number of orthogonal optimizations. We concentrate separately on removing correlated subqueries, also called “query flattening,” and on efficient execution of queries with aggregations. The end result is a modular, flexible implementation, which produces very efficient execution plans. To demonstrate the validity of our approach, we present results for some queries from the TPC-H benchmark. From all published TPC-H results in the 300GB scale, at the time of writing (November 2000), SQL Server has the fastest results on those queries, even on a fraction of the processors used by other systems.
Exploiting constraint-like data characterizations in query optimization
Authors: Godfrey Parke , Gryz Jarek , Zuzarte Calisto
Published: November 2005

Query optimizers nowadays draw upon many sources of information about the database to optimize queries. They employ runtime statistics in cost-based estimation of query plans. They employ integrity constraints in the query rewrite process. Primary and foreign key constraints have long played a role in the optimizer, both for rewrite opportunities and for providing more accurate cost predictions. More recently, other types of integrity constraints are being exploited by optimizers in commercial systems, for which certain semantic query optimization techniques have now been implemented.

These new optimization strategies that exploit constraints hold the promise for good improvement. Their weakness, however, is that often the “constraints” that would be useful for optimization for a given database and workload are not explicitly available for the optimizer. Data mining tools can find such “constraints” that are true of the database, but then there is the question of how this information can be kept by the database system, and how to make this information available to, and effectively usable by, the optimizer.

We present our work on
soft constraints
in DB2. A soft constraint is a syntactic statement equivalent to an integrity constraint declaration. A soft constraint is not really a constraint, per se, since future updates may undermine it. While a soft constraint is valid, however, it can be used by the optimizer in the same way integrity constraints are. We present two forms of soft constraint:
absolute
and
statistical
. An absolute soft constraint is consistent with respect to the
current
state of the database, just in the same way an integrity constraint must be. They can be used in rewrite, as well as in cost estimation. A statistical soft constraint differs in that it may have some degree of violation with respect to the state of the database. Thus, statistical soft constraints cannot be used in rewrite, but they can still be used in cost estimation.

We are working long-term on absolute soft constraints. We discuss the issues involved in implementing a facility for absolute soft constraints in a database system (and in DB2), and the strategies that we are researching. The current DB2 optimizer is more amenable to adding facilities for statistical soft constraints. In the short-term, we have been implementing pathways in the optimizer for statistical soft constraints. We discuss this implementation.
COSIMA- your smart, speaking E-salesperson
Authors: Kieβling Werner , Holland Stefan , Fischer Stefan , Ehm Thorsten
Published: November 2005

We present a new cooperative user interface for e-shopping. COSIMA is an intelligent Internet avatar with dynamic voice output that assists customers through their e-shopping tours and advises them like a real salesperson. COSIMA uses a meta search engine based on Preference SQL, computing best matching results to the customer's wishes. COSIMA can qualify these results and generates proper voice output. Our presentation shows COSIMA in action for comparison shopping.
Monitoring business processes through event correlation based on dependency model
Authors: Adii Asaf , Botzer David , Etzion Opher , Yatzkar-Haham Tali
Published: November 2005

Events are at the core of reactive and proactive applications, which have become popular in many domains.

This demo shows the monitoring of incoming events as a means to detect possible problems in the course of business processes using a dependency model.

Contemporary modeling tools lack the capability to express the event semantics and relationships to other entities. This capability is useful when the events are based on a dependency model among business processes, applications and resources. The ability to express an event by employing a general dependency model, an to use it through a designated event correlation monitoring tool, enables the accomplishment of tasks such as impact analysis and business processes monitoring, including prediction of violation of constraints (such as: service level agreements).

This demonstrated tool provides the system designer with the ability to define and describe events and their relationships to other events, objects and tasks. The model employs various conditional dependencies that are specific to the event domain. The demo shows how systems (business processes) are monitored using the dependency / event model, by applying rules using an event correlation engine with strong expressive power.

This demo proposal describes the generic application development tool, the middleware architecture and framework and the demo.
Lots o'Ticks
Authors: Whitney Arthur , Shasha Dennis
Published: November 2005

Financial mathematicians think they can predict the future by looking at time series of trades and quotes (called ticks) from the past. The main evidence for this hypothesis is that prices fluctuate only by a small amount in a given day and more or less obey the mathematics of a random walk. The hypothesis allows traders to price options and to speculate on stocks. This demonstration presents a query language and a parallel database (50-way parallelism) to support traders who want to analyze every tick, not just end-of-day ticks, using temporal statistical queries such as time-delayed correlations and tick trends. This is the first attempt that we know of to store and analyze hundreds of gigabytes of time series data and to query that data using a declarative time series extension to SQL (available at www.kx.com).
XML data management (panel session)
Authors: Larson Per-Åke , Florescu Dana , Graefe Goetz , Moerkotte Guido , Pirahesh Hamid , Schöning Harald
Published: November 2005

XML data is likely to be widely used as a data exchange format but users also need to store and query XML data. The purpose of this panel is to explore whether and how to best provide this functionality.
Standard for multimedia databases
Authors: Smith John R.
Published: November 2005

The Moving Picture Experts Group (MPEG) is developing a new standard called the “Multimedia Content Description Interface,” also known as MPEG-7. The goal of MPEG-7 is to enable fast and effective searching and filtering of multimedia content. The effort is being driven by requirements taken from a large number of applications related to multimedia databases, interactive media services (music, TV programs), video libraries, and so forth. MPEG-7 is achieving this goal by developing an XML-Schema based standard for describing features of multimedia content. In this tutorial, we study the emerging MPEG-7 standard and describe the new challenges for MPEG-7 multimedia databases.
Real-time database — similarity and resource scheduling
Authors: Kuo Tei-Wei , Mok Aloysius K.
Published: November 2005

While much recent work has focussed on the performance of transaction systems where individual transactions have deadlines, our research addresses the semantics of data usage in real-time applications and its integration with real-time resource management, in particular, the timeless value of real-time data and the inherent path and not state-based constraints on concurrency control. Central to our research is the idea of similarity which is a reflexive, symmetric relation over the domain of a data object. By exploiting the similarity relation, we propose a class of efficient data-access policies for real-time data objects. We shall also discuss the design of a distributed real-time data-access interface. Our goal is to build a database facility which can support predictable real-time applications involving high-speed communication, information access, and multimedia.
Overview of the STanford Real-time Information Processor (STRIP)
Authors: Adelberg Brad , Kao Ben , Garcia-Molina Hector
Published: November 2005

We believe that the greatest growth potential for soft real-time databases is not as isolated monolithic databases but as components in open systems consisting of many heterogenous databases. In such environments, the flexibility to deal with unpredictable situations and the ability to cooperate with other databases (often non-real-time databases) is just as important as the guarantee of stringent timing constraints. In this paper, we describe a database designed explicitly for heterogeneous environments, the STanford Real-time Information Processor (STRIP). STRIP, which runs on standard Posix Unix, is a soft real-time main memory database with special facilities for importing and exporting data as well as handling derived data. We will describe the architecture of STRIP, its unique features, and its potential uses in overall system architectures.
Integrating contents and structure in text retrieval
Authors: Baeza-Yates Ricardo , Navarro Gonzalo
Published: November 2005

The purpose of a textual database is to store textual documents. These documents have not only textual contents, but also structure. Many traditional text database systems have focused only on querying by contents or by structure. Recently, a number of models integrating both types of queries have appeared. We argue in favor of that integration, and focus our attention on these recent models, covering a representative sampling of the proposals in the field. We pay special attention to the tradeoffs between expressiveness and efficiency, showing the compromises taken by the models. We argue in favor of achieving a good compromise, since being weak in any of these two aspects makes the model useless for many applications.
Object query standards
Authors: Wade Andrew E.
Published: November 2005

As object technology is adopted by software systems for analysis and design, language, GUI, and frameworks, the database community also is working to support objects, and to develop standards for that support. A key benefit of object technology is the ability for different objects and object tools to interoperate, so it's critical that such DBMS object standards interoperate with those of the rest of the object world. Starting with a discussion of the new issues objects bring to query standards, we present the efforts of various groups relevant to this, including ODMG, OMG, ANSI X3H2 (SQL3), and recent merger efforts feeding into SQL3.

What's different with Objects?

ODMG's OQL

OMG's Query Service

SQL3's Object extensions

Efforts to merge