|
|
ABSTRACTS
|
|
|
RESEARCH SESSION 1:COMPRESSION
AND INDEXING
Compressing Large
Boolean Matrices using Reordering Techniques
David S. Johnson, Shankar Krishnan (AT&T Labs-Research), Jatin Chhugani,
Subodh Kumar (John Hopkins Univ.), Suresh Venkatasubramanian (AT&T
Labs-Research)
Large boolean matrices
are a basic representational unit in a variety of applications, with some
notable examples being interactive visualization systems, mining large graph
structures, and association rule mining. Designing space and time efficient
scalable storage and query mechanisms for such large matrices is a challenging
problem. We present a lossless compression strategy to store and access
such large matrices efficiently on disk. Our approach is based on viewing
the columns of the matrix as points in a very high dimensional Hamming space,
and then formulating an appropriate optimization problem that reduces to
solving an instance of the Traveling Salesman Problem on this space. Finding
good solutions to large TSP's in high dimensional Hamming spaces is itself
a challenging and little-explored problem -- we cannot readily exploit geometry
to avoid the need to examine all N^2 inter-city distances and instances
can be too large for standard TSP codes to run in main memory. Our multi-faceted
approach adapts classical TSP heuristics by means of instance-partitioning
and sampling, and may be of independent interest. For instances derived
from interactive visualization and telephone call data we obtain significant
improvement in access time over standard techniques, and for the visualization
application we also make significant improvements in compression.
On the Performance
of Bitmap Indices for High Cardinality Attributes
Kesheng Wu, Ekow Otoo, Arie Shoshani (Lawrence Berkeley National Laboratory)
It is well established
that bitmap indices are efficient for read-only attributes with low attribute
cardinalities. For an attribute with a high cardinality, the size of the
bitmap index can be very large. To overcome this size problem, specialized
compression schemes are used. Even though there are empirical evidences
that some of these compression schemes work well, there has not been any
systematic analysis of their effectiveness. In this paper, we systematically
analyze the two most efficient bitmap compression techniques, the Byte-aligned
Bitmap Code(BBC) and the Word-Aligned Hybrid (WAH) code. Our analyses show
that both compression schemes can be optimal. We propose a novel strategy
to select the appropriate algorithms so that this optimality is achieved
in practice. In addition, our analyses and tests show that the compressed
indices are relatively small compared with commonly used indices such as
B-trees. Given these facts, we conclude that bitmap index is efficient on
attributes of low cardinalities as well as on those of high cardinalities.
Practical Suffix Tree Construction
Sandeep Tata, Richard A. Hankins, Jignesh M. Patel (Univ. of Michigan)
Large string datasets
are common in a number of emerging text and biological database applications.
Common queries over such datasets include both exact and approximate string
matches. These queries can be evaluated very efficiently by using a suffix
tree index on the string dataset. Although suffix tree scan be constructed
quickly in memory for small input datasets, constructing persistent trees
for large datasets has been challenging. In this paper, we explore suffix
tree construction algorithms over a wide spectrum of data sources and sizes.
First, we show that on modern processors, a cache-efficient algorithm with
O(n^2) complexity outperforms the popular O(n) Ukkonen algorithm, even for
in-memory construction. For larger datasets, the disk I/O requirement quickly
becomes the bottleneck in each algorithm's performance. To address this
problem, we present a buffer management strategy for the O(n^2) algorithm,
creating a new disk-based construction algorithm that scales to sizes much
larger than have been previously described in the literature. Our approach
far outperforms the best known disk-based construction algorithms.
RESEARCH
SESSION 2:XML VIEWS AND SCHEMAS
Answering XPath
Queries over Networks by Sending Minimal Views
Keishi Tajima, Yoshiki Fukui (JAIST)
When a client submits
a set of XPath queries to a XML database on a network, the set of answer
sets sent back by the database may include redundancy in two ways: some
elements may appear in more than one answer set, and some elements in some
answer sets may be subelements of other elements in other (or the same)
answer sets. Even when a client submits a single query, the answer can be
self-redundant because some elements may be subelements of other elements
in that answer. Therefore, sending those answers as they are is not optimal
with respect to communication costs. In this paper, we propose a method
of minimizing communication costs in XPath processing over networks. Given
a single or a set of queries, we compute a minimal-size view set that can
answer all the original queries. The database sends this view set to the
client, and the client produces answers from it. We show algorithms for
computing such a minimal view set for given queries. This view set is optimal;
it only includes elements that appear in some of the final answers, and
each element appears only once.
A Framework for
Using Materialized XPath Views in XML Query Processing
Andrey Balmin, Fatma Ozcan, Kevin Beyer, Roberta Cochrane, Hamid Pirahesh
(IBM Almaden)
XML languages, such
as XQuery, XSLT and SQL/XML, employ XPath as the search and extraction language.
XPath expressions often define complicated navigation, resulting in expensive
query processing, especially when executed over large collections of documents.
In this paper, we propose a framework for exploiting materialized XPath
views to expedite processing of XML queries. We explore a class of materialized
XPath views, which may contain XML fragments, typed data values, full paths,
node references or any combination thereof. We develop an XPath matching
algorithm to determine when such views can be used to answer a user query
containing XPath expressions. We use the match information to identify the
portion of an XPath expression in the user query which is not covered by
the XPath view. Finally, we construct, possibly multiple, compensation expressions
which need to be applied to the view to produce the query result. Experimental
evaluation, using our prototype implementation, shows that the matching
algorithm is very efficient and usually accounts for a small fraction of
the total query compilation time.
Schema-Free XQuery
Yunyao Li, Cong Yu, H. V. Jagadish (Univ. of Michigan)
The widespread adoption
of XML holds out the promise that document structure can be exploited to
specify precise database queries. However, the user may have only a limited
knowledge of the XML structure, and hence may be unable to produce a correct
XQuery, especially in the context of a heterogeneous information collection.
The default is to use keyword-based search and we are all too familiar with
how difficult it is to obtain precise answers by these means. We seek to
address these problems by introducing the notion of Meaningful Lowest Common
Ancestor Structure (MLCAS) for finding related nodes within an XML document.
By automatically computing MLCAS and expanding ambiguous tag names, we add
new functionality to XQuery and enable users to take full advantage of XQuery
in querying XML data precisely and efficiently without requiring (perfect)
knowledge of the document structure. Such a Schema-Free XQuery is potentially
of value not just to casual users with partial knowledge of schema, but
also to experts working in a data integration or data evolution context.
In such a context, a schema-free query, once written, can be applied universally
to multiple data sources that supply similar content under different schemas,
and applied "forever" as these schemas evolve. Our experimental
evaluation found that it was possible to express a wide variety of queries
in a schema-free manner and have them return correct results over a broad
diversity of schemas. Furthermore, the evaluation of a schema-free query
is not expensive using a novel stack-based algorithm we develop for computing
MLCAS: from 1 to 4 times the execution time of an equivalent schema-aware
query.
RESEARCH
SESSION 3: CONTROLLING ACCESS
Client-Based
Access Control Management for XML Documents
Luc Bouganim (INRIA Rocquencourt), Francois Dang Ngoc, Philippe Pucheral
(PRiSM Laboratory)
The erosion of trust
put in traditional database servers and in Database Service Providers, the
growing interest for different forms of data dissemination and the concern
for protecting children from suspicious Internet content are different factors
that lead to move the access control from servers to clients. Several encryption
schemes can be used to serve this purpose but all suffer from a static way
of sharing data. With the emergence of hardware and software security elements
on client devices, more dynamic client-based access control schemes can
be devised. This paper proposes an efficient client-based evaluator of access
control rules for regulating access to XML documents. This evaluator takes
benefit from a dedicated index to quickly converge towards the authorized
parts of a - potentially streaming - document. Additional security mechanisms
guarantee that prohibited data can never be disclosed during the processing
and that the input document is protected from any form of tampering. Experiments
on synthetic and real datasets demonstrate the effectiveness of the approach.
Secure XML Publishing
without Information Leakage in the Presence of Data Inference
Xiaochun Yang (Northeastern Univ.), Chen Li (Univ. of California, Irvine)
Recent applications
are seeing an increasing need that publishing XML documents should meet
precise security requirements. In this paper, we consider data-publishing
applications where the publisher specifies what information is sensitive
and should be protected. We show that if a partial document is published
carelessly, users can use common knowledge (e.g., ``all patients in the
same ward have the same disease'') to infer more data, which can cause
leakage of sensitive information. The goal is to protect such information
in the presence of data inference with common knowledge. We consider common
knowledge represented as semantic XML constraints. We formulate the process
how users can infer data using three types of common XML constraints.
Interestingly, no matter what sequences users follow to infer data, there
is a unique, maximal document that contains all possible inferred documents.
We develop algorithms for finding a partial document of a given XML document
without causing information leakage, while allowing publishing as much
data as possible. Our experiments on real data sets show that effect of
inference on data security, and how the proposed techniques can prevent
such leakage from happening. Limiting Disclosure
in Hippocratic Databases
Kristen LeFevre (Univ. of Wisconsin), Rakesh Agrawal (IBM Almaden), Vuk
Ercegovac, Raghu Ramakrishnan (Univ. of Wisconsin),Yirong Xu (IBM Almaden),
David DeWitt (Univ. of Wisconsin)
We present a practical
and efficient approach to incorporating privacy policy enforcement into
an existing application and database environment, and we explore some of
the semantics tradeoffs introduced by enforcing these rules at cell-level
granularity. Through a comprehensive set of performance experiments, we
show that the cost of privacy enforcement is small, and scalable to large
databases.
RESEARCH
SESSION 4: XML (I)
On Testing Satisfiability
of Tree Pattern Queries
Laks Lakshmanan, Ganesh Ramesh, Hui Wang, Zheng Zhao (Univ. of British
Columbia)
XPath and XQuery (which
includes XPath as a sublanguage) are the major query languages for XML.
An important issue arising in efficient evaluation of queries expressed
in these languages is satisfiability, i.e., whether there exists a database,
consistent with the schema if one is available, on which the query has
a non-empty answer. Our experience shows satisfiability check can effect
substantial savings in query evaluation. We systematically study satisfiability
of tree pattern queries (which capture a useful fragment of XPath) together
with additional constraints, with or without a schema. We identify cases
in which this problem can be solved in polynomial time and develop novel
efficient algorithms for this purpose. We also show that in several cases,
the problem is NP-complete. We ran a comprehensive set of experiments
to verify the utility of satisfiability check as a preprocessing step
in query processing. Our results show that this check takes a negligible
fraction of the time needed for processing the query while often yielding
substantial savings.
Containment
of Nested XML Queries
Xin Dong, Alon Halevy, Igor Tatarinov (Univ. of Washington)
Query containment
is the most fundamental relationship between a pair of database queries:
a query Q is said to be contained in a query Q' if the answer for Q is
always a subset of the answer for Q',independent of the current state
of the database. Query containment is an important problem in a wide variety
of data management applications, including verification of integrity constraints,
reasoning about contents of data sources in data integration, semantic
caching, verification of knowledge bases, determining queries independent
of updates, and most recently, in query reformulation for peer data management
systems. Query containment has been studied extensively in the relational
context and for XPath queries, but not for XML queries with nesting. We
consider the theoretical aspects of the problem of query containment for
XML queries with nesting. We begin by considering conjunctive XML queries
(c-XQueries), and show that containment is in polynomial time if we restrict
the fan-out (number of sibling sub-blocks) to be 1. We prove that for
arbitrary fan-out, containment is coNP-hard already for queries with nesting
depth 2, even if the query does not include variables in the return clauses.
We then show that for queries with fixed nesting depth, containment is
coNP-complete. Next, we establish the computational complexity of query
containment for several practical extensions of c-XQueries, including
queries with union and arithmetic comparisons, and queries where the XPath
expressions may include descendant edges and negation. Finally, we describe
a few heuristics for speeding up query containment checking in practice
by exploiting properties of the queries and the underlying schema.
Efficient XML-to-SQL
Query Translation: Where to Add the Intelligence ?
Rajasekar Krishnamurthy (IBM Almaden), Raghav Kaushik (Microsoft Research),
Jeffrey Naughton (Univ. of Wisconsin-Madison)
We consider the efficiency
of queries generated by XML to SQL translation. We first show that published
XML-to-SQL query translation algorithms are suboptimal in that they often
translate simple path expressions into complex SQL queries even when much
simpler equivalent SQL queries exist. There are two logical ways to deal
with this problem. One could generate suboptimal SQL queries using a fairly
naive translation algorithm, and then attempt to optimize the resulting
SQL; or one could use a more intelligent translation algorithm with the
hopes of generating efficient SQL directly. We show that optimizing the
SQL after it is generated is problematic, becoming intractable even in
simple scenarios; by contrast, designing a translation algorithm that
exploits information readily available at translation time is a promising
alternative. To support this claim, we present a translation algorithm
that exploits translation time information to generate efficient SQL for
path expression queries over tree schemas.
Taming XPath
Queries by Minimizing Wildcard Steps
Chee-Yong Chan (National Univ. of Singapore), Wenfei Fan (Univ. of Edinburgh
& Bell Laboratories), Yiming Zeng (National Univ. of Singapore)
This paper presents
a novel and complementary technique to optimize an XPath query by minimizing
its wildcard steps. Our approach is based on using a general composite
axis called the layer axis, to rewrite a sequence of XPath steps (all
of which are wildcard steps except for possibly the last)into a single
layer-axis step. We describe an efficient implementation of the layer
axis and present a novel and efficient rewriting algorithm to minimize
both non-branching as well as branching wildcard steps in XPath queries.
We also demonstrate the usefulness of wildcard-step elimination by proposing
an optimized evaluation strategy for wildcard-free Path queries that enables
selective loading of only the relevant input XML data for query evaluation.
Our experimental results not only validate the scalability and efficiency
of our optimized evaluation strategy, but also demonstrate the effectiveness
of our rewriting algorithm for minimizing wildcard steps in XPath queries.
To the best of our knowledge, this is the first effort that addresses
this new optimization problem.
The NEXT Framework
for Logical Xquery Optimization
Alin Deutsch, Yannis Papakonstantinou, Yu Xu (Univ. of California, San
Diego)
Classical logical
optimization techniquesrely on a logical semantics of the query language.
The adaptation of these techniques to XQuery is precluded by its definition
as a functional language with operational semantics. We introduce Nested
XML Tableaux which enable a logical foundation for XQuery semantics and
provide the logical plan optimization framework of our XQuery processor.
As a proof of concept, we develop and evaluate a minimization algorithm
for removing redundant navigation within and across nested subqueries.
The rich XQuery features create key challenges that fundamentally extend
the prior work on the problems of minimizing conjunctive and tree pattern
queries.
RESEARCH
SESSION 5:STREAM MINING
Detecting Change
in Data Streams
Daniel Kifer, Shai Ben-David, Johannes Gehrke (Cornell Univ.)
Detecting changes
in a data stream is an important area of research with many applications.
In this paper, we present a novel method for the detection and estimation
of change. In addition to providing statistical guarantees on the reliability
of detected changes, our method also provides meaningful descriptions
and quantification of these changes. Our approach assumes that the points
in the stream are independently generated, but otherwise makes no assumptions
on the nature of the generating distribution. Thus our techniques work
for both continuous and discrete data. In an experimental study we demonstrate
the power of our techniques.
Stochastic Consistency,
and Scalable Pull-Based Caching for Erratic Data Stream Sources
Shanzhong Zhu, Chinya V. Ravishankar (Univ.of California, Riverside)
We introduce the notion
of stochastic consistency, and propose a novel approach to achieving it
for caches of highly erratic data. Erratic data sources, such as stock
prices, sensor data, and network traffic statistics, are common and important
in practice. However their erratic patterns of change can make caching
hard. Stochastic consistency guarantees that errors in cached values of
erratic data remain within a user-specified bound, with a user-specified
probability. We use a Brownian motion model to capture the behavior of
data changes, and use its underlying theory to predict when caches should
initiate pulls to refresh cached copies to maintain stochastic consistency.
Our approach allows servers to remain totally stateless, thus achieving
excellent scalability and reliability. We also discuss a new real-time
scheduling approach for servicing pull requests at the server. Our scheduler
delivers prompt response whenever possible, and minimizes the aggregate
cache-source deviation due to delays during server overload. We conduct
extensive experiments to validate our model on real-life datasets, and
show that our scheme outperforms current schemes.
False Positive
or False Negative: Mining Frequent Item sets from High Speed Transactional
Data Streams
Jeffrey Xu Yu (The Chinese Univ. of Hong Kong), Zhihong Chong (Fudan Univ.),
Hongjun Lu (The Hong Kong Univ. of Science and Technology), Aoying Zhou
(Fudan Univ.)
The problem of finding
frequent items has been recently studied over high speed data streams.
However, mining frequent item sets from transactional data streams has
not been well addressed yet in terms of its bounds of memory consumption.
The main difficulty is due to the nature of the exponential explosion
of item sets. Given a domain of Iunique items, the possible number of
item sets can be up to2**I-1. When the length of data streams approaches
to a very large number N, the possibility of an item set to be frequent
becomes larger and difficult to track with limited memory. However, the
real killer of effective frequent item set mining is that most of existing
algorithms are false-positive oriented. That is, they control memory consumption
in the counting processes by an error parameter e, and allow items with
support below the specified minimum support s but above s-e counted as
frequent ones. Such false-positive items increase the number of false-positive
frequent item sets exponentially, which may make the problem computationally
intractable with bounded memory consumption. In this paper, we developed
algorithms that can effectively mine frequent item(set)s from high speed
transactional data streams with a bound of memory consumption. While our
algorithms are false-negative oriented, that is, certain frequent item
sets may not appear in the results, the number of false-negative item
sets can be controlled by a predefined parameter so that desired recall
rate of frequent item sets can be guaranteed. We developed algorithms
based on Chernoff bound. Our extensive experimental studies show that
the proposed algorithms have high accuracy, require less memory, and consume
less CPU time. They significantly outperform the existing false-positive
algorithms.
INDUSTRIAL
SESSION 1: NOVEL SQL EXTENSIONS
Returning Modified
Rows - SELECT Statements with Side Effects
Andreas Behm, Serge Rielau, Richard Swagerman (IBM Toronto Lab)
SQL in the IBM®
DB2® Universal Database™ for Linux®, UNIX®, and Windows®
(DB2 UDB) database management product has been extended to support nested
INSERT, UPDATE, and DELETE operations in SELECT statements. This allows
database applications additional processing on modified rows. Within a
single unit of work, applications can retrieve a result set containing
the modified rows from a table or view modified by an SQL data-change
operation. This eliminates the need to select the row after an INSERT
or UPDATE, or before a DELETE statement. As a result, fewer network round
trips, less server CPU time, fewer cursors, and less server memory are
required. In addition, deadlocks can be avoided. The proposed approach
is integrated with the set semantics of SQL, and does not require any
procedural logic or modifications on the underlying relational data model.
Pipelining multiple update, insert and delete operations using the same
source data provides a very efficient way for multi-table data-change
statements typically found in ETL (extraction, transformation, load) applications.
We demonstrate significant performance benefit with our experiences in
the TPC-C benchmark. Experimental results show that the new SQL is more
efficient in query execution compared to classic SQL.
PIVOT and UNPIVOT:
Optimization and Execution Strategies in an RDBMS and Scalable Pull-Based
Caching for Erratic Data Sources
Conor Cunningham, Cesar Galindo-Legaria, Goetz Graefe (Microsoft Corp.)
PIVOT and UNPIVOT,
two operators on tabular data that exchange rows and columns, enable data
transformations useful in data modeling, data analysis, and data presentation.
They can quite easily be implemented inside a query processor, much like
select, project, and join. Such a design provides opportunities for better
performance, both during query optimization and query execution. We discuss
query optimization and execution implications of this integrated design
and evaluate the performance of this approach using a prototype implementation
in Microsoft SQL Server.
A Multi-Purpose
Implementation of Mandatory Access Control in Relational Database Management
Systems
Walid Rjaibi, Paul Bird (IBM Toronto Lab)
Mandatory Access Control
(MAC) implementations in Relational Database Management Systems (RDBMS)
have focused solely on Multilevel Security (MLS). MLS has posed a number
of challenging problems to the database research community, and there
has been an abundance of research work to address those problems. Unfortunately,
the use of MLS RDBMS has been restricted to a few government organizations
where MLS is of paramount importance such as the intelligence community
and the Department of Defense. The implication of this is that the investment
of building an MLS RDBMS cannot be leveraged to serve the needs of application
domains where there is a desire to control access to objects based on
the label associated with that object and the label associated with the
subject accessing that object, but where the label access rules and the
label structure do not necessarily match the MLS two security rules and
the MLS label structure. This paper introduces a flexible and generic
implementation of MAC in RDBMS that can be used to address the requirements
from a variety of application domains, as well as to allow an RDBMS to
efficiently take part in an end-to-end MAC enterprise solution. The paper
also discusses the extensions made to the SQL compiler component of an
RDBMS to incorporate the label access rules in the access plan it generates
for an SQL query, and to prevent unauthorized leakage of data that could
occur as a result of traditional optimization techniques performed by
SQL compilers.
RESEARCH
SESSION 6:XML (II)
Indexing Temporal
XML Documents
Alberto Mendelzon, Flavio Rizzolo (Univ. of Toronto), Alejandro Vaisman
(Univ. of Buenos Aires)
Different models have
been proposed recently for representing temporal data, tracking historical
information, and recovering the state of the document as of any given
time, in XML documents. We address the problem of indexing temporal XML
documents. In particular we show that by indexing "continuous paths",
i.e. paths that are valid continuously during a certain interval in a
temporal XML graph, we can dramatically increase query performance. We
describe in detail the indexing scheme, denoted TempIndex, and compare
its performance against both a system based on a non-temporal path index,
and one based on DOM.
Schema-based
Scheduling of Event Processors and Buffer Minimization for Queries on
Structured Data Streams
Christoph Koch, Stefanie Scherzinger (Technische Universitat Wien), Nicole
Schweikardt (Humboldt Universitat zu Berlin), Bernhard Stegmaier (Technische
Universitat Munchen)
We introduce an extension
of the XQuery language, FluX, that supports event-based query processing
and the conscious handling of main memory buffers. Purely event-based
queries of this language can be executed on streaming XML data in a very
direct way. We then develop an algorithm that allows to efficiently rewrite
XQueries into the event-based FluX language. This algorithm uses order
constraints from a DTD to schedule event handlers and to thus minimize
the amount of buffering required for evaluating a query. We discuss the
various technical aspects of query optimization and query evaluation within
our framework. This is complemented with an experimental evaluation of
our approach.
Bloom Histogram:
Path Selectivity Estimation for XML Data with Updates
Wei Wang (Univ. of NSW), Haifeng Jiang, Hongjun Lu (Hong Kong Univ. of
Science and Technology), Jeffrey Xu Yu (The Chinese Univ. of Hong Kong)
Cost-based XML query
optimization calls for accurate estimation of the selectivity of path
expressions. Some other interactive and internet applications can also
benefit from such estimations. While there are a number of estimation
techniques proposed in the literature, almost none of them has any guarantee
on the estimation accuracy within a given space limit. In addition, most
of them assume that the XML data are more or less static, i.e., with few
updates. In this paper, we present a framework for XML path selectivity
estimation in a dynamic context. Specifically, we propose a novel data
structure, bloom histogram, to approximate XML path frequency distribution
within a small space budget and to estimate the path selectivity accurately
with the bloom histogram. We obtain the upper bound of its estimation
error and discuss the trade-offs between the accuracy and the space limit.
To support updates of bloom histograms efficiently when underlying XML
data change, a dynamic summary layer is used to keep exact or more detailed
XML path information. We demonstrate through our extensive experiments
that the new solution can achieve significantly higher accuracy with an
even smaller space than the previous methods in both static and dynamic
environments.
INDUSTRIAL
SESSION 2: NEW DBMS ARCHITECTURES AND PERFORMANCE
Hardware Acceleration
in Commercial Databases: A Case Study of Spatial Operations
Nag Nagender Bandi (Univ. of California, Santa Barbara), Chengyu Sun (California
State Univ., Los Angeles), Divyakant Agrawal, Amr El Abbadi (Univ. of
California, Santa Barbara)
Traditional databases
have focused on the issue of reducing I/O cost as it is the bottleneck
in many operations. As databases become increasingly accepted in areas
such as Geographic Information Systems (GIS) and Bio-informatics, commercial
DBMS need to support data types for complex data such as spatial geometries
and protein structures. These non-conventional data types and their associated
operations present new challenges. In particular, the computational cost
of some spatial operations can be orders of magnitude higher than the
I/O cost. In order to improve the performance of spatial query processing,
innovative solutions for reducing this computational cost are beginning
to emerge. Recently, it has been proposed that hardware acceleration of
an off-the-shelf graphics card can be used to reduce the computational
cost of spatial operations. However, this proposal is preliminary in that
it establishes the feasibility of the hardware assisted approach in a
stand-alone setting but not in a real-world commercial database. In this
paper we present an architecture to show how hardware acceleration of
an off-the-shelf graphics card can be integrated into a popular commercial
database to speed up spatial queries. Extensive experimentation with real-world
datasets shows that significant improvement in the performance of spatial
operations can be achieved with this integration. The viability of this
approach underscores the significance of a tighter integration of hardware
acceleration into commercial databases for spatial applications.
P*TIME: Highly
Scalable OLTP DBMS for Managing Update-Intensive Stream Workload
Sang K. Cha (Transact In Memory, Inc.), Changbin Song (Seoul National
Univ.)
Over the past thirty
years since the system R and Ingres projects started to lay the foundation
for today's RDBMS implementations, the underlying hardware and software
platforms have changed dramatically. However, the fundamental RDBMS architecture,
especially, the storage engine architecture, largely remains unchanged.
While this conventional architecture may suffices for satisfying most
of today's applications, its deliverable performance range is far from
meeting the so-called growing "real-time enterprise" demand
of acquiring and querying high-volume update data streams cost-effectively.
P*TIME is a new, memory-centric light-weight OLTP RDBMS designed and built
from scratch to deliver orders of magnitude higher scalability on commodity
SMP hardware than existing RDBMS implementations, not only in search but
also in update performance. Its storage engine layer incorporates our
previous innovations for exploiting engine-level micro-parallelism such
as differential logging and optimistic latch-free index traversal concurrency
control protocol. This paper presents the architecture and performance
of P*TIME and reports our experience of deploying P*TIME as the stock
market database server at one of the largest on-line brokerage firms.
Generating Thousand
Benchmark Queries in Seconds
Meikel Poess (Oracle Corp.), John M. Stephens, Jr. (Gradient Systems)
The combination of
an exponential growth in the amount of data managed by a typical business
intelligence system and the increased competitiveness of a global economy
has propelled decision support systems (DSS) from the role of exploratory
tools employed by a few visionary companies to become a core requirement
for a competitive enterprise. That same maturation has often resulted
in a selection process that requires an ever more critical system evaluation
and selection to be completed in an increasingly short period of time.
While there have been some advances in the generation of data sets for
system evaluation (see [3]), the quantification of query performance has
often relied on models and methodologies that were developed for systems
that were more simplistic, less dynamic, and less central to a successful
business. In this paper we present QGEN, a flexible, high-level query
generator optimized for decision support system evaluation. QGEN is able
to generate arbitrary query sets, which conform to a selected statistical
profile without requiring that the queries be statically defined or disclosed
prior to testing. Its novel design links query syntax with abstracted
data distributions, enabling users to parameterize their query workload
to match an emerging access pattern or data set modification. This results
in query sets that retain comparability for system comparisons while reflecting
the inherent dynamism of operational systems, and which provide a broad
range of syntactic and semantic coverage, while remaining focused on appropriate
commonalities within a particular evaluation process or business segment.
RESEARCH
SESSION 7:XML AND RELATIONS
XQuery on SQL
Hosts
Torsten Grust, Sherif Sakr, Jens Teubner (Univ. of Konstanz)
Relational database
systems may be turned into efficient XML and XPath processors if the system
is provided with a suitable relational tree encoding. This paper extends
this relational XML processing stack and shows that an RDBMS can also
serve as a highly efficient XQuery runtime environment. Our approach is
purely relational: XQuery expressions are compiled into SQL code which
operates on the tree encoding. The core of the compilation procedure trades
XQuery's notions of variable scopes and nested iteration (FLWOR blocks)
for equi-joins. The resulting relational XQuery processor closely adheres
to the language semantics, e.g., it obeys node identity as well as document
and sequence order, and can support XQuery's full axis feature. The system
exhibits quite promising performance figures in experiments. Somewhat
unexpectedly, we will also see that the XQuery compiler can make good
use of SQL's OLAP functionality.
ROX: Relational
Over XML
Alan Halverson (Univ. of Wisconsin-Madison), Vanja Josifovski, Guy Lohman,
Hamid Pirahesh (IBM Almaden), Mathias Moerschel
An increasing percentage
of the data needed by business applications is being generated in XML
format. Storing the XML in its native format will facilitate new applications
that exchange business objects in XML format and query portions of XML
documents using XQuery. This paper explores the feasibility of accessing
natively-stored XML data through traditional SQL interfaces, called Relational
Over XML (ROX), in order to avoid the costly conversion of legacy applications
to XQuery. It describes the forces that are driving the industry to evolve
toward the ROX scenario as well as some of the issues raised by ROX. The
impact of denormalization of data in XML documents is discussed both from
a semantic and performance perspective. We also weigh the implications
of ROX for manageability and query optimization. We experimentally compared
the performance of a prototype of the ROX scenario to today's SQL engines,
and found that good performance can be achieved through a combination
of utilizing XML's hierarchical storage to store relations "pre-joined"
as well as creating indices over the remaining join columns. We have developed
an experimental framework using DB2 8.1 for Linux, Unix and Windows, and
have gathered initial performance results that validate this approach.
From XML View
Updates to Relational View Updates: old solutions to a new problem
Vanessa Braganholo (Universidade Federal do Rio Grande do Sul), Susan
Davidson (Univ. of Pennsylvania, and INRIA-FUTURS), Carlos Heuser (Universidade
Federal do Rio Grande do Sul)
This paper addresses
the question of updating relational databases through XML views. Using
"query trees" to capture the notions of selection, projection,
nesting, grouping, and heterogeneous sets found throughout most XML query
languages, we show how XML views expressed using query trees can be mapped
to a set of corresponding relational views. We then show how updates on
the XML view are mapped to updates on the corresponding relational views.
Existing work on updating relational views can then be leveraged to determine
whether or not the relational views are updatable with respect to the
relational updates, and if so, to translate the updates to the underlying
relational database.
RESEARCH
SESSION 8:STREAM MINING (II)
XWAVE: Optimal
and Approximate Extended Wavelets for Streaming Data
Sudipto Guha (Univ. of Pennsylvania), Chulyun Kim, Kyuseok Shim (Seoul
National Univ.)
Wavelet synopses have
been found to be of interest in query optimization and approximate query
answering. Recently, extended wavelets were proposed by Deligiannakis
and Roussopoulos for datasets containing multiple measures. Extended wavelets
optimize the storage utilization by attempting to store the same wavelet
coefficient across different measures. This reduces the bookkeeping overhead
and more coefficients can be stored. An optimal algorithm for minimizing
the error in representation and an approximation algorithm for the complementary
problem was provided. However, both their algorithms take linear space.
Synopsis structures are often used in environments where space is at a
premium and the data arrives as a continuous stream which is too expensive
to store. In this paper, we give algorithms for extended wavelets which
are space sensitive, i.e., use space which is dependent on the size of
the synopsis (and at most on the logarithm of the total data) and operates
in a streaming fashion. We present better optimal algorithms based on
dynamic programming and a near optimal approximate greedy algorithm. We
also demonstrate the performance benefits of our algorithms compared to
previous ones through experiments on real-life and synthetic datasets.
REHIST: Relative
Error Histogram Construction Algorithms
Sudipto Guha (Univ. of Pennsylvania), Kyuseok Shim, Jungchul Woo (Seoul
National Univ.)
Histograms and Wavelet
synopses provide useful tools in query optimization and approximate query
answering. Traditional histogram construction algorithms, such as V-Optimal,
optimize absolute error measures for which the error in estimating a true
value of 10 by 20 has the same effect of estimating a true value of1000
by 1010. However, several researchers have recently pointed out the drawbacks
of such schemes and proposed wavelet based schemes to minimize relative
error measures. None of these schemes provide satisfactory guarantees
-- and we provide evidence that the difficulty may lie in the choice of
wavelets as the representation scheme. In this paper, we consider histogram
construction for the known relative error measures. We develop optimal
as well as fast approximation algorithms. We provide a comprehensive theoretical
analysis and demonstrate the effectiveness of these algorithms in providing
significantly more accurate answers through synthetic and real life data
sets.
Distributed
Set-Expression Cardinality Estimation
Abhinandan Das (Cornell Univ.), Sumit Ganguly (IIT Kanpur), Minos Garofalakis,
Rajeev Rastogi (Bell Labs, Lucent Technologies)
We consider the problem
of estimating set-expression cardinality in a distributed streaming environment
where rapid update streams originating at remote sites are continually
transmitted to a central processing system. At the core of our algorithmic
solutions for answering set-expression cardinality queries are two novel
techniques for lowering data communication costs without sacrificing answer
precision. Our first technique exploits global knowledge of the distribution
of certain frequently occurring stream elements to significantly reduce
the transmission of element state information to the central site. Our
second technical contribution involves a novel way of capturing the semantics
of the input set expression in a boolean logic formula, and using models
(of the formula) to determine whether an element state change at a remote
site can affect the set expression result. Results of our experimental
study with real-life as well as synthetic data sets indicate that our
distributed set-expression cardinality estimation algorithms achieve substantial
reductions in message traffic compared to naive approaches that provide
the same accuracy guarantees.
INDUSTRIAL
SESSION 3: SEMANTIC QUERY APPROACHES
Supporting Ontology-Based
Semantic Matching in RDBMS
Souripriya Das, Eugene Chong, George Eadon, Jagannathan Srinivasan (Oracle
Corp.)
Ontologies are increasingly
being used to build applications that utilize domain-specific knowledge.
This paper addresses the problem of supporting ontology-based semantic
matching in RDBMS. Specifically, 1) A set of SQL operators, namely ONT_RELATED,
ONT_EXPAND, ONT_DISTANCE, and ONT_PATH, are introduced to perform ontology-based
semantic matching, 2) A new indexing scheme ONT_INDEXTYPE is introduced
to speed up ontology-based semantic matching operations, and 3) System-defined
tables are provided for storing ontologies specified in OWL. Our approach
enables users to reference ontology data directly from SQL using the semantic
match operators, thereby opening up possibilities of combining with other
operations such as joins as well as making the ontology-driven applications
easy to develop and efficient. In contrast, other approaches use RDBMS
only for storage of ontologies and querying of ontology data is typically
done via APIs. This paper presents the ontology-related functionality
including inferencing, discusses how it is implemented on top of Oracle
RDBMS, and illustrates the usage with several database applications.
BioPatentMiner:
An Information Retrieval System for BioMedical Patents
Sougata Mukherjea, Bhuvan Bamba (IBM India Research Lab)
Before undertaking
new biomedical research, identifying concepts that have already been patented
is essential. Traditional keyword based search on patent databases may
not be sufficient to retrieve all the relevant information, especially
for the biomedical domain. More sophisticated retrieval techniques are
required. This paper presents BioPatentMiner, a system that facilitates
information retrieval from biomedical patents. It integrates information
from the patents with knowledge from biomedical ontologies to create a
Semantic Web. Besides keyword search and queries linking the properties
specified by one or more RDF triples, the system can discover Semantic
Associations between the resources. The system also determines the importance
of the resources to rank the results of a search and prevent information
overload while determining the Semantic Associations.
Flexible String
Matching Against Large Databases in Practice
Nick Koudas, Amit Marathe, Divesh Srivastava (AT&T Labs-Research)
Data Cleaning is an
important process that has been at the center of research interest in
recent years. Poor data quality is the result of a variety of reasons,
including data entry errors and multiple conventions for recording database
fields, and has a significant impact on a variety of business issues.
Hence, there is a pressing need for technologies that enable flexible
(fuzzy) matching of string information in a database. Cosine similarity
with tf-idf is a well-established metric for comparing text, and recent
proposals have adapted this similarity measure for flexibly matching a
query string with values in a single attribute of a relation. In deploying
tf-idf based flexible string matching against real AT&T databases,
we observed that this technique needed to be enhanced in many ways. First,
along the functionality dimension, where there was a need to flexibly
match along multiple string-valued attributes, and also take advantage
of known semantic equivalences. Second, we identified various performance
enhancements to speed up the matching process, potentially trading off
a small degree of accuracy for substantial performance gains. In this
paper, we report on our techniques and experience in dealing with flexible
string matching against real AT&T databases.
RESEARCH
SESSION 9:STREAM QUERY PROCESSING
Memory-Limited
Execution of Windowed Stream Joins
Utkarsh Srivastava, Jennifer Widom (Stanford Univ.)
We address the problem
of computing approximate answers to continuous sliding-window joins over
data streams when the available memory may be insufficient to keep the
entire join state. One approximation scenario is to provide a maximum
subset of the result, with the objective of losing as few result tuples
as possible. An alternative scenario is to provide a random sample of
the join result, e.g., if the output of the join is being aggregated.
We show formally that neither approximation can be addressed effectively
for a sliding-window join of arbitrary input streams. Previous work has
only addressed the maximum-subset problem, and has implicitly used a frequency-based
model of stream arrival. We address the sampling problem for this model.
More importantly, we point out a broad class of applications for which
an age-based model of stream arrival is more appropriate, and we address
both approximation scenarios under this new model. Finally, for the case
of multiple joins being executed with an overall memory constraint, we
provide an algorithm for memory allocation across the joins that optimizes
a combined measure of approximation in all scenarios considered. All of
our algorithms are implemented and experimental results demonstrate their
effectiveness.
Resource Sharing
in Continuous Sliding-Window Aggregates
Arvind Arasu, Jennifer Widom (Stanford Univ.)
We consider the problem
of resource sharing when processing large numbers of continuous queries.
We specifically address sliding-window aggregates over data streams, an
important class of continuous operators for which sharing has not been
addressed. We present a suite of sharing techniques that cover a wide
range of possible scenarios: different classes of aggregation functions
(algebraic, distributive, holistic), different window types (time-based,
tuple-based, suffix, historical), and different input models (single stream,
multiple substreams). We provide precise theoretical performance guarantees
for our techniques, and show their practical effectiveness through a thorough
experimental study.
Remembrance
of Streams Past: Overload-Sensitive Management of Archived Streams
Sirish Chandrasekaran, Michael J. Franklin (UC Berkeley)
This paper studies
Data Stream Management Systems that combine real-time data streams with
historical data, and hence access incoming streams and archived data simultaneously.
A significant problem for these systems is the I/O cost of fetching historical
data which inhibits processing of the live data streams. Our solution
is to reduce the I/O cost for accessing the archive by retrieving only
a reduced (summarized or sampled) version of the historical data. This
paper does not propose new summarization or sampling techniques, but rather
a framework in which multiple resolutions of summarization/sampling can
be generated efficiently. The query engine can select the appropriate
level of summarization to use depending on the resources currently available.
The central research problem studied is whether to generate the multiple
representations of archived data eagerly upon data-arrival, lazily at
query-time, or in a hybrid fashion. Concrete techniques for each approach
are presented, which are tied to a specific data reduction technique (random
sampling). The tradeoffs among the three approaches are studied both analytically
and experimentally.
WIC: A General-Purpose
Algorithm for Monitoring Web Information Sources
Sandeep Pandey, Kedar Dhamdhere, Christopher Olston (Carnegie Mellon Univ.)
The Web is becoming
a universal information dissemination medium, due to a number of factors
including its support for content dynamicity. A growing number of Web
information providers post near real-time updates in domains such as auctions,
stock markets, bulletin boards, news, weather, roadway conditions, sports
scores, etc. External parties often wish to capture this information for
a wide variety of purposes ranging from online data mining to automated
synthesis of information from multiple sources. There has been a great
deal of work on the design of systems that can process streams of data
from Web sources, but little attention has been paid to how to produce
these data streams, given that Web pages generally require ``pull-based''
access. In this paper we introduce a new general-purpose algorithm for
monitoring Web information sources, effectively converting pull-based
sources into push-based ones. Our algorithm can be used in conjunction
with continuous query systems that assume information is fed into the
query engine in a push-based fashion. Ideally, a Web monitoring algorithm
for this purpose should achieve two objectives: (1) timeliness and (2)
completeness of information captured. However, we demonstrate both analytically
and empirically using real-world data that these objectives are fundamentally
at odds. When resources available for Web monitoring are limited, and
the number of sources to monitor is large, it may be necessary to sacrifice
some timeliness to achieve better completeness, or vice versa. To take
this fact into account, our algorithm is highly parameterized and targets
an application-specified balance between timeliness and completeness.
In this paper we formalize the problem of optimizing for a flexible combination
of timeliness and completeness, and prove that our parameterized algorithm
is a 2-approximation in all cases, and in certain cases is optimal.
RESEARCH
SESSION 10:MANAGING WEB INFORMATION SOURCES
Similarity Search
for Web Services
Xin Dong, Alon Halevy, Jayant Madhavan, Ema Nemes, Jun Zhang (Univ. of
Washington)
Web services are loosely
coupled software components, published, located, and invoked across the
web. The growing number of web services available within an organization
and on the Web raises a new and challenging search problem: locating desired
web services. Traditional keyword search is insufficient in this context:
the specific types of queries users require are not captured, the very
small text fragments in web services are unsuitable for keyword search,
and the underlying structure and semantics of the web services are not
exploited. We describe the algorithms underlying the Woogle search engine
for webservices. Woogle supports similarity search for web services, such
as finding similar web-service operations and finding operations that
compose with a given one. We describe novel techniques to support these
types of searches, and an experimental study on a collection of over 1500
web-service operations that shows the high recall and precision of our
algorithms.
AWESOME
- A Data Warehouse-based System for Adaptive Website Recommendations
Andreas Thor, Erhard Rahm (Univ. of Leipzig)
Recommendations are
crucial for the success of large websites. While there are many ways to
determine recommendations, the relative quality of these recommenders
depends on many factors and is largely unknown. We propose a new classification
of recommenders and comparatively evaluate their relative quality for
a sample website. The evaluation is performed with AWESOME (Adaptive WEbSite
recOMmEndations), a new data warehouse-based recommendation system capturing
and evaluating user feedback on presented recommendations. Moreover, we
show how AWESOME performs an automatic and adaptive closed-loop website
optimization by dynamically selecting the most promising recommenders
based on continuously measured recommendation feedback. We propose and
evaluate several alternatives for dynamic recommender selection including
a powerful machine learning approach.
Accurate and
Efficient Crawling for Relevant Websites
Martin Ester (Simon Fraser Univ.), Hans-Peter Kriegel, Matthias Schubert
(Univ. of Munich)
Focused web crawlers
have recently emerged as an alternative to the well-established web search
engines. While the well-known focused crawlers retrieve relevant web pages,
there are various applications which target whole websites instead of
single web pages. For example, companies are represented by websites,
not by individual web pages. To answer queries targeted at websites, web
directories are an established solution. In this paper, we introduce a
novel focused website crawler to employ the paradigm of focused crawling
for the search of relevant websites. The proposed crawler is based on
a two-level architecture and corresponding crawl strategies with an explicit
concept of websites. The external crawler views the web as a graph of
linked websites, selects the websites to be examined next and invokes
internal crawlers. Each internal crawler views the web pages of a single
given website and performs focused (page) crawling within that website.
Our experimental evaluation demonstrates that the proposed focused website
crawler clearly outperforms previous methods of focused crawling which
were adapted to retrieve websites instead of single web pages.
Instance-based
Schema Matching for Web Databases by Domain-specific Query Probing
Jiying Wang (Hong Kong Univ. of Science and Technology), Ji-Rong Wen (Microsoft
Research Asia), Fred Lochovsky (Hong Kong Univ. of Science and Technology),
Wei-Ying Ma (Microsoft Research Asia)
In a Web database
that dynamically provides information in response to user queries, two
distinct schemas, interface schema (the schema users can query) and result
schema (the schema users can browse), are presented to users. Each partially
reflects the actual schema of the Web database. Most previous work only
studied the problem of schema matching across query interfaces of Web
databases. In this paper, we propose a novel schema model that distinguishes
the interface and the result schema of a Web database in a specific domain.
In this model, we address two significant Web database schema-matching
problems: intra-site and inter-site. The first problem is crucial in automatically
extracting data from Web databases, while the second problem plays a significant
role in meta-retrieving and integrating data from different Web databases.
We also investigate a unified solution to the two problems based on query
probing and instance-based schema matching techniques. Using the model,
a cross validation technique is also proposed to improve the accuracy
of the schema matching. Our experiments on real Web databases demonstrate
that the two problems can be solved simultaneously with high precision
and recall.
RESEARCH
SESSION 11:DISTRIBUTED SEARCH AND QUERY PROCESSING
Computing PageRank
in a Distributed Internet Search Engine System
Yuan Wang, David DeWitt (University of Wisconsin - Madison)
Existing Internet
search engines use web crawlers to download data from the Web. Page quality
is measured on central servers, where user queries are also processed.
This paper argues that using crawlers has a list of disadvantages. Most
importantly, crawlers do not scale. Even Google, the leading search engine,
indexes less than 1% of the entire Web. This paper proposes a distributed
search engine framework, in which every web server answers queries over
its own data. Results from multiple web servers will be merged to generate
a ranked hyperlink list on the submitting server. This paper presents
a series of algorithms that compute PageRank in such framework. The preliminary
experiments on a real data set demonstrate that the system achieves comparable
accuracy on PageRank vectors to Google's well-known PageRank algorithm
and, therefore, high quality of query results.
Enhancing P2P
File-Sharing with an Internet-Scale Query Processor
Boon Thau Loo (UC Berkeley), Joseph M. Hellerstein (UC Berkeley and Intel
Research Berkeley), Ryan Huebsch (UC Berkeley), Scott Shenker (UC Berkeley
and International Computer Science Institute), Ion Stoica (UC Berkeley)
In this paper, we
address the problem of designing a scalable, accurate query processor
for peer-to-peer filesharing and similar distributed keyword search systems.
Using a globally-distributed monitoring infrastructure, we perform an
extensive study of the Gnutella file sharing network, characterizing its
topology, data and query workloads. We observe that Gnutella's query processing
approach performs well for popular content, but quite poorly for rare
items with few replicas. We then consider an alternate approach based
on Distributed Hash Tables (DHTs). We describe our implementation of PIER
Search, a DHT-based system, and propose a hybrid system where Gnutella
is used to locate popular items, and PIER Search for handling rare items.
We develop an analytical model of the two approaches, and use it in concert
with our Gnutella traces to study the trade-off between query recall and
system overhead of the hybrid system. We evaluate a variety of localized
schemes for identifying items that are rare and worth handling via the
DHT. Lastly, we show in a live deployment on fifty nodes on two continents
that it nicely complements Gnutella in its ability to handle rare items.
Online Balancing
of Range-Partitioned Data with Applications to Peer-to-Peer Systems
Prasanna Ganesan, Mayank Bawa, Hector Garcia-Molina (Stanford Univ.)
We consider the problem
of horizontally partitioning a dynamic relation across a large number
of disks/nodes by the use of range partitioning. Such partitioning is
often desirable in large-scale parallel databases, a swell as in peer-to-peer
(P2P) systems. As tuples are inserted and deleted, the partitioning may
need to be adjusted, and data moved, in order to achieve storage balance
across the participant disks/nodes. We propose efficient, asymptotically
optimal algorithms that ensure storage balance at all times, even against
an adversarial insertion and deletion of tuples. We combine the above
algorithms with distributed routing structures to architect a P2P system
that supports efficient range queries, while simultaneously guaranteeing
storage balance.
Network-Aware
Query Processing for Distributed Stream-Based Applications
Yanif Ahmad, Ugur Cetintemel (Brown Univ.)
This paper investigates
the benefits of network awareness when processing queries in widely-distributed
environments such as the Internet. We present algorithms that leverage
knowledge of network characteristics (e.g., topology, bandwidth, etc.)
when deciding on the network locations where the query operators are executed.
Using a detailed emulation study based on realistic network models, we
analyze and experimentally evaluate the proposed approaches for distributed
stream processing. Our results quantify the significant benefits of the
network-aware approaches and reveal the fundamental trade-off between
bandwidth efficiency and result latency that arises in networked query
processing.
Data Sharing
Through Query Translation in Autonomous Sources
Anastasios Kementsietsidis, Marcelo Arenas (Univ. of Toronto)
Given a point q, a
reverse k nearest neighbor (RkNN) query retrieves all the data points
that have q as one of their k nearest neighbors. Existing methods for
processing such queries have at least one of the following deficiencies:
(i) they do not support arbitrary values of k (ii) they cannot deal efficiently
with database updates, (iii) they are applicable only to 2D data (but
not to higher dimensionality), and (iv) they retrieve only approximate
results. Motivated by these shortcomings, we develop algorithms for exact
processing of RkNN with arbitrary values of k on dynamic datasets of any
dimensionality. Our methods utilize a conventional multi-dimensional index
on the dataset and do not require any pre-computation. In addition to
their flexibility, we experimentally verify that the proposed algorithms
outperform the existing ones even in their restricted focus.
RESEARCH
SESSION 12:STREAM DATA MANAGEMENT SYSTEMS
Linear Road:
A Stream Data Management Benchmark
Arvind Arasu (Stanford Univ.), Mitch Cherniack, Eduardo Galvez (Brandeis
Univ.), David Maier (OHSU/OGI), Anurag Maskey, Esther Ryvkina (Brandeis
Univ.), Michael Stonebraker, Richard Tibbetts (MIT)
This paper specifies
the Linear Road Benchmark for Stream Data Management Systems (SDMS). Stream
Data Management Systems process streaming data by executing continuous
and historical queries while producing query results in real-time. This
benchmark makes it possible to compare the performance characteristics
of SDMS' relative to each other and to alternative(e.g., relational) systems.
Linear Road has been endorsed as an SDMS benchmark by both Aurora (out
of Brandeis University, Brown University and MIT) and STREAM (out of Stanford
University).Linear Road is inspired by the increasing prevalence of ``variable
tolling'' on highway systems throughout the world. Variable tolling uses
dynamically determined factors such as congestion levels and accident
proximity to calculate toll charges. Linear Road specifies a variable
tolling system for a fictional urban area including such features as accident
detection and alerts, traffic congestion measurements, toll calculations
and historical queries. After specifying the benchmark, we describe experimental
results involving two implementations: one using a commercially available
Relational Database Management System and the other using Aurora. Our
results show that a dedicated Stream Data Management System can outperform
a Relational Database Management System by at least a factor of 5 on streaming
data applications.
Query Languages
and Data Models for Database Sequences and Data Streams
Yan-Nei Law (UCLA), Haixun Wang (IBM T. J. Watson Research), Carlo Zaniolo
(UCLA)
We study the fundamental
limitations of relational algebra (RA)and SQL in supporting sequence and
stream queries, and present effective query language and data model enrichments
to deal with them. We begin by observing the well-known limitations of
SQL in application domains which are important for data streams, such
as sequence queries and data mining. Then we present a formal proof that,
for continuous queries on data streams, SQL suffers from additional expressive
power problems. We begin by focusing on the notion of non blocking (NB)
queries that are the only continuous queries that can be supported on
data streams. We characterize the notion of non blocking queries by showing
that they are equivalent to monotonic queries. Therefore the notion of
NB-completeness for RA can be formalized as its ability to express all
monotonic queries expressible in RA using only the monotonic operators
of RA. We show that RA is not NB-complete, and SQL is not more powerful
than RA for monotonic queries. To solve these problems, we propose extensions
that allow SQL to support all the monotonic queries expressible by a Turing
machine using only monotonic operators. We show that these extensions
are(i) user-defined aggregates (UDAs) natively coded in SQL (rather than
in an external language), and (ii) a generalization of the union operator
to support the merging of multiple streams according to their timestamps.
These query language extensions require matching extensions to basic relational
data model to support sequences explicitly ordered by timestamps. Along
with the formulation of very powerful queries, the proposed extensions
entail more efficient expressions for many simple queries. In particular,
we show that non blocking queries are simple to characterize according
to their syntactic structure.
RESEARCH
SESSION 13:AUDITING
Tamper Detection
in Audit Logs
Richard Snodgrass, Shilong Yao, Christian Collberg (Univ. of Arizona)
Audit logs are considered
good practice for business systems, and are required by federal regulations
for secure systems, drug approval data, medical information disclosure,
financial records, and electronic voting. Given the central role of audit
logs, it is critical that they are correct and inalterable. It is not
sufficient to say, "our data is correct, because we store all interactions
in a separate audit log." The integrity of the audit log itself must
also be guaranteed. This paper proposes mechanisms within a database management
system (DBMS), based on cryptographically strong one-way hash functions,
that prevent an intruder, including an auditor or an employee or even
an unknown bug within the DBMS itself, from silently corrupting the audit
log. We propose that the DBMS store additional information in the database
to enable a separate audit log validator to examine the database along
with this extra information and state conclusively whether the audit log
has been compromised. We show with an implementation on a high-performance
storage engine that the overhead for auditing is low and that the validator
can efficiently and correctly determine if the audit log has been compromised.
Auditing Compliance
with a Hippocratic Database
Rakesh Agrawal, Roberto Bayardo, Christos Faloutsos, Jerry Kiernan, Ralf
Rantzau, Ramakrishnan Srikant (IBM Almaden)
We introduce an auditing
framework for determining whether a database system is adhering to its
data disclosure policies. Users formulate audit expressions to specify
the (sensitive) data subject to disclosure review. An audit component
accepts audit expressions and returns all queries (deemed "suspicious")
that accessed the specified data during their execution. The overhead
of our approach on query processing is small, involving primarily the
logging of each query string along with other minor annotations. Database
triggers are used to capture updates in a backlog database. At the time
of audit, a static analysis phase selects a subset of logged queries for
further analysis. These queries are combined and transformed into an SQL
audit query, which when run against the backlog database, identifies the
suspicious queries efficiently and precisely. We describe the algorithms
and data structures used in a DB2-based implementation of this framework.
Experimental results reinforce our design choices and show the practicality
of the approach.
RESEARCH
SESSION 14:DATA WAREHOUSING
High-Dimensional
OLAP: A Minimal Cubing Approach
Xiaolei Li, Jiawei Han, Hector Gonzalez (Univ. of Illinois at Urbana-Champaign)
Data cube has been
playing an essential role in fast OLAP (online analytical processing)
in many multi-dimensional data warehouses. However, there exist data sets
in applications like bioinformatics, statistics, and text processing that
are characterized by high dimensionality, e.g., over 100 dimensions, and
moderate size, e.g., around 10^6 tuples. No feasible data cube can be
constructed with such data sets. In this paper we will address the problem
of developing an efficient algorithm to perform OLAP on such data sets.<p>Experience
tells us that although data analysis tasks may involve a high dimensional
space, most OLAP operations are performed only on a small number of dimensions
at a time. Based on this observation, we propose a novel method that computes
a thin layer of the data cube together with associated value-list indices.
This layer, while being manageable in size, will be capable of supporting
flexible and fast OLAP operations in the original high dimensional space.
Through experiments we will show that the method has I/O costs that scale
nicely with dimensionality and that are comparable to the costs of accessing
a fully materialized data cube.
The Polynomial
Complexity of Fully Materialized Coalesced Cubes
Yannis Sismanis, Nick Roussopoulos (Univ. of Maryland)
The data cube operator
encapsulates all possible groupings of a dataset and has proved to be
an invaluable tool in analyzing vast amountsof data. However its apparent
exponential complexity has significantly limited its applicability to
low dimensional datasets. Recently the idea of the coalesced cube was
introduced, and showed that high-dimensional coalesced cubes are orders
of magnitudes smaller in size than the original data cubes even when they
calculate and store every possible aggregation with 100% precision. In
this paper we present an analytical framework for estimating the size
of coalesced cubes. By using this framework on uniform coalesced cubes
we show that their size and the required computation time scales polynomially
with the dimensionality of the data set and, therefore, a full data cube
at 100% precision is not inherently cursed by high dimensionality. Additionally,
we show that such coalesced cubes scale polynomially (and close to linearly)
with the number of tuples on the dataset. We were also able to develop
an efficient algorithm for estimating the size of coalesced cubes before
actually computing them, based only on metadata about the cubes. Finally,
we complement our analytical approach with an extensive experimental evaluation
using real and synthetic data sets, and demonstrate that not only uniform
but also zipfian and real coalesced cubes scale polynomially.
RESEARCH
SESSION 15:LINK ANALYSIS
Relational Link-based
Ranking
Floris Geerts (Univ. of Edinburgh), Heikki Mannila, Evimaria Terzi (Univ.
of Helsinki)
Link analysis methods
show that the interconnections between web pages have lots of valuable
information. The link analysis methods are, however, inherently oriented
towards analyzing binary relations. We consider the question of generalizing
link analysis methods for analyzing relational databases. To this aim,
we provide a generalized ranking framework and address its practical implications.
More specifically, we associate with each relational database and set
of queries a unique weighted directed graph, which we call the database
graph. We explore the properties of database graphs. In analogy to link
analysis algorithms, which use the Web graph to rank web pages, we use
the database graph to rank partial tuples. In this way we can, e.g., extend
the PageRank link analysis algorithm to relational databases and give
this extension a random querier interpretation. Similarly, we extend the
HITS link analysis algorithm to relational databases. We conclude with
some preliminary experimental results.
ObjectRank:
Authority-Based Keyword Search in Databases
Andrey Balmin (IBM Almaden), Vagelis Hristidis (Florida International
Univ.), Yannis Papakonstantinou (UC San Diego)
The ObjectRank system
applies authority-based ranking to keyword search in databases modeled
as labeled graphs. Conceptually, authority originates at the nodes (objects)
containing the keywords and flows to objects according to their semantic
connections. Each node is ranked according to its authority with respect
to the particular keywords. One can adjust the weight of global importance,
the weight of each keyword of the query, the importance of a result actually
containing the keywords versus being referenced by nodes containing them,
and the volume of authority flow via each type of semantic connection.
Novel performance challenges and opportunities are addressed. First, schemas
impose constraints on the graph, which are exploited for performance purposes.
Second, in order to address the issue of authority ranking with respect
to the given keywords (as opposed to Google's global PageRank) we precompute
single keyword ObjectRanks and combine them during run time. We conducted
user surveys and a set of performance experiments on multiple real and
synthetic datasets, to assess the semantic meaningfulness and performance
of ObjectRank.
Combating Web
Spam with TrustRank
Zoltan Gyongyi, Hector Garcia-Molina (Stanford Univ.), Jan Pedersen (Yahoo!,
Inc.)
Web spam pages use
various techniques to achieve higher-than-deserved rankings in a search
engine's results. While human experts can identify spam, it is too expensive
to manually evaluate a large number of pages. Instead, we propose techniques
to semi-automatically separate reputable, good pages from spam. We first
select a small set of seed pages to be evaluated by an expert. Once we
manually identify the reputable seed pages, we use the link structure
of the web to discover other pages that are likely to be good. In this
paper we discuss possible ways to implement the seed selection and the
discovery of good pages. We present results of experiments run on the
World Wide Web indexed by AltaVista and evaluate the performance of our
techniques. Our results show that we can effectively filter out spam from
a significant fraction of the web, based on a good seed set of less than
200 sites.
RESEARCH
SESSION 16:SENSORS, GRID, PUB/SUB SYSTEMS
Model-Driven
Data Acquisition in Sensor Networks *
BEST PAPER *
Amol Deshpande (UC Berkeley), Carlos Guestrin (Intel Research Berkeley),
Samuel Madden (MIT and Intel Research Berkeley), Joseph Hellerstein (UC
Berkeley and Intel Research Berkeley), Wei Hong (Intel Research Berkeley)
Declarative queries
are proving to be anattractive paradigm for interacting withnetworks of
wireless sensors. The metaphor that "the sensor net is a database"
is problematic, however, because sensors do not exhaustively represent
the data in the real world. In order to map the raw sensor readings onto
physical reality, a "model" of that reality is required to complement
the readings. In this paper, we enrich interactive sensor querying with
statistical modeling techniques. We demonstrate that such models can help
provide answers that are both more meaningful, and, by introducing approximations
with probabilistic confidences, significantly more efficient to compute
in both time and energy. Utilizing the combination of a model and live
data acquisition raises the challenging optimization problem of selecting
the best sensor readings to acquire, balancing the increase in the confidence
of our answer against the communication and data acquisition costs in
the network. We describe an exponential time algorithm for finding the
optimal solution to this optimization problem, and a polynomial-time heuristic
for identifying solutions that perform well in practice. We evaluate our
approach on several real-world sensor-network data sets, taking into account
the real measured data and communication quality, demonstrating that our
model-based approach provides a high-fidelity representation of the real
phenomena and leads to significant performance gains versus traditional
data acquisition techniques.
GridDB: A Data-Centric
Overlay for Scientific Grids
David Liu, Michael J. Franklin (UC Berkeley)
We present GridDB,
a data-centric overlay for scientific grid data analysis. In contrast
to currently deployed process-centric middleware, GridDB manages data
entities rather than processes. GridDB provides a suite of services important
to data analysis: a declarative interface, type-checking, interactive
query processing, and memorization. We discuss several elements of GridDB:workflow/data
model, query language, software architecture and query processing; and
a prototype implementation. We validate GridDB by showing its modeling
of real-world physics and astronomy analyses, and measurements on our
prototype.
Towards an Internet-Scale
XML Dissemination Service
Yanlei Diao, Shariq Rizvi, Michael J. Franklin (UC Berkeley)
Publish/subscribe
systems have demonstrated the ability to scale to large numbers of users
and high data rates when providing content-based data dissemination services
on the Internet. However, their services are limited by the data semantics
and query expressiveness that they support. On the other hand, the recent
work on selective dissemination of XML data has made significant progress
in moving from XML filtering to the richer functionality of transformation
for result customization, but in general has ignored the challenges of
deploying such XML-based services on an Internet-scale. In this paper,
we address these challenges in the context of incorporating the rich functionality
of XML data dissemination in a highly scalable system. We present the
architectural design of ONYX, a system based on an overlay network. We
identify the salient technical challenges in supporting XML filtering
and transformation in this environment and propose techniques for solving
them.
INDUSTRIAL
SESSION 4: AUTOMATIC TUNING IN COMMERCIAL DVMSS
DB2 Design Advisor:
Integrated Automatic Physical Database Design
Danny Zilio (IBM Toronto Lab), Jun Rao (IBM Almaden), Sam Lightstone (IBM
Toronto Lab), Guy Lohman (IBM Almaden), Adam Storm, Christian, Garcia-Arellano
(IBM Toronto Lab), Scott Fadden (IBM Portland)
The DB2 Design Advisor
in IBM DB2 Universal Database (DB2 UDB) Version 8.2 for Linux, UNIX and
Windows is a tool that, for a given workload, automatically recommends
physical design features that are any subset of indexes, materialized
query tables (also called materialized views), shared-nothing database
partitionings, and multidimensional clustering of tables. Our work is
the very first industrial-strength tool that covers the design of as many
as four different features, a significant advance to existing tools, which
support no more than just indexes and materialized views. Building such
a tool is challenging, because of not only the large search space introduced
by the interactions among features, but also the extensibility needed
by the tool to support additional features in the future. We adopt a novel
"hybrid" approach in the Design Advisor that allows us to take
important interdependencies into account as well as to encapsulate design
features as separate components to lower the reengineering cost. The Design
Advisor also features a built-in module that automatically reduces the
given workload, and therefore provides great scalability for the tool.
Our experimental results demonstrate that our tool can quickly provide
good physical design recommendations that satisfy users' requirements.
Automatic SQL
Tuning in Oracle 10g
Benoit Dageville, Dinesh Das, Karl Dias, Khaled Yagoub, Mohamed Zait,
Mohamed Ziauddin (Oracle Corp.)
SQL tuning is a very
critical aspect of database performance tuning. It is an inherently complex
activity requiring a high level of expertise in several domains: query
optimization, to improve the execution plan selected by the query optimizer;
access design, to identify missing access structures; and SQL design,
to restructure and simplify the text of a badly written SQL statement.
Furthermore, SQL tuning is a time consuming task due to the large volume
and evolving nature of the SQL workload and its underlying data. In this
paper we present the new Automatic SQL Tuning feature of Oracle 10g. This
technology is implemented as a core enhancement of the Oracle query optimizer
and offers a comprehensive solution to the SQL tuning challenges mentioned
above. Automatic SQL Tuning introduces the concept of SQL profiling to
transparently improve execution plans. It also generates SQL tuning recommendations
by performing cost-based access path and SQL structure "what-if"
analyses. This feature is exposed to the user through both graphical and
command line interfaces. The Automatic SQL Tuning is an integral part
of the Oracle's framework for self-managing databases. The superiority
of this new technology is demonstrated by comparing the results of Automatic
SQL Tuning to manual tuning using a real customer workload.
Database Tuning
Advisor for Microsoft SQL Server 2005
Sanjay Agrawal, Surajit Chaudhuri, Lubor Kollar, Arun Marathe, Vivek Narasayya,
Manoj Syamala (Microsoft Corp.)
The Database Tuning
Advisor (DTA) that is part of Microsoft SQL Server 2005 is an automated
physical database design tool that significantly advances the state-of-the-art
in several ways. First, DTA is capable to providing an integrated physical
design recommendation for horizontal partitioning, indexes, and materialized
views. Second, unlike today's physical design tools that focus solely
on performance, DTA also supports the capability for a database administrator
(DBA) to specify manageability requirements while optimizing for performance.
Third, DTA is able to scale to large databases and workloads using several
novel techniques including: (a) workload compression (b) reduced statistics
creation and (c) exploiting test server to reduce load on production server.
Finally, DTA greatly enhances scriptability and customization through
the use of a public XML schema for input and output. This paper provides
an overview of DTA's novel functionality, the rationale for its architecture,
and demonstrates DTA's quality and scalability on large customer workloads.
RESEARCH
SESSION 17:TOP-K RANKING
Efficiency-Quality
Tradeoffs for Vector Score Aggregation
Pavan Kumar C Singitham, Mahathi Mahabhashyam (Stanford Univ.), Prabhakar
Raghavan (Verity Inc.)
Finding the l-nearest
neighbors to a query in a vector space is an important primitive in text
and image retrieval. Here we study an extension of this problem with applications
to XML and image retrieval: we have multiple vector spaces, and the query
places a weight on each space. Match scores from the spaces are weighted
by these weights to determine the overall match between each record and
the query; this is a case of score aggregation. We study approximation
algorithms that use a small fraction of the computation of exhaustive
search through all records, while returning nearly the best matches. We
focus on the tradeoff between the computation and the quality of the results.
We develop two approaches to retrieval from such multiple vector spaces.
The first is inspired by resource allocation. The second, inspired by
computational geometry, combines the multiple vector spaces together with
all possible query weights into a single larger space. While mathematically
elegant, this abstraction is intractable for implementation. We therefore
devise an approximation of this combined space. Experiments show that
all our approaches (to varying extents) enable retrieval quality comparable
to exhaustive search, while avoiding its heavy computational cost.
Merging the
Results of Approximate Match Operations
Sudipto Guha (Univ. of Pennsylvania), Nick Koudas, Amit Marathe, Divesh
Srivastava (AT&T Labs-Research
Data Cleaning is an
important process that has been at the center of research interest in
recent years. An important end goal of effective data cleaning is to identify
the relational tuple or tuples that are "most related" to a
given query tuple. Various techniques have been proposed in the literature
for efficiently identifying approximate matches to a query string against
a single attribute of a relation. In addition to constructing a ranking
(i.e., ordering) of these matches, the techniques often associate, with
each match, scores that quantify the extent of the match. Since multiple
attributes could exist in the query tuple, issuing approximate match operations
for each of them separately will effectively create a number of ranked
lists of the relation tuples. Merging these lists to identify a final
ranking and scoring, and returning the top-K tuples, is a challenging
task. In this paper, we adapt the well-known foot rule distance (for merging
ranked lists) to effectively deal with scores. We study efficient algorithms
to merge rankings, and produce the top-K tuples, in a declarative way.
Since techniques for approximately matching a query string against a single
attribute in a relation are typically best deployed in a database, we
introduce and describe two novel algorithms for this problem and we provide
SQL specifications for them. Our experimental case study, using real application
data along with a realization of our proposed techniques on a commercial
data base system, highlights the benefits of the proposed algorithms and
attests to the overall effectiveness and practicality of our approach.
Top-k Query
Evaluation with Probabilistic Guarantees
Martin Theobald, Gerhard Weikum, Ralf Schenkel (Max-Planck Institute of
Computer Science)
Top-k queries based
on ranking elements of multidimensional datasets are a fundamental building
block for many kinds of information discovery. The best known general-purpose
algorithm for evaluating top-k queries is Fagin's threshold algorithm
(TA). Since the user's goal behind top-k queries is to identify one or
a few relevant and novel data items, it is intriguing to use approximative
variants of TA to reduce run-time costs. This paper introduces a family
of approximative top-k algorithms based on probabilistic arguments. When
scanning index lists of the underlying multidimensional data space in
descending order of local scores, various forms of convolution and derived
bounds are employed to predict when it is safe, with high probability,
to drop candidate items and to prune the index scans. The precision and
the efficiency of the developed methods are experimentally evaluated based
on a large Web corpus and a structured data collection.
RESEARCH
SESSION 18:DBMS ARCHITECTURE AND PERFORMANCE
STEPS Towards
Cache-resident Transaction Processing
Stavros Harizopoulos, Anastassia Ailamaki (Carnegie Mellon Univ.)
Online transaction
processing (OLTP) is a multi-billion dollar industry with high-end database
servers employing state-of-the-art processors to maximize performance.
Unfortunately, recent studies show that CPUs are far from realizing their
maximum intended throughput because of delays in the processor caches.
When running OLTP, instruction-related delays in the memory subsystem
account for 25 to 40% of the total execution time. In contrast to data,
instruction misses cannot be overlapped with out-of-order execution, and
instruction caches cannot grow as the slower access time directly affects
the processor speed. The challenge is to alleviate the instruction-related
delays without increasing the cache size. We propose Steps, a technique
that minimizes instruction cache misses in OLTP workloads by multiplexing
concurrent transactions and exploiting common code paths. One transaction
paves the cache with instructions, while close followers enjoy a nearly
miss-free execution. Steps yields up to 96.7% reduction in instruction
cache misses for each additional concurrent transaction, and at the same
time eliminates up to 64% of mispredicted branches by loading a repeating
execution pattern into the CPU. This paper (a) describes the design and
implementation of Steps, (b) analyzes Steps using microbenchmarks, and
(c) shows Steps performance when running TPC-C on top of the Shore storage
manager.
Write-Optimized
B-Trees
Goetz Graefe (Microsoft)
Large writes are beneficial
both on individual disks and on disk arrays, e.g., RAID-5. The presented
design enables large writes of internal B-tree nodes and leaves. It supports
both in-place updates and large append-only ("log-structured")
write operations within the same storage volume, within the same B-tree,
and even at the same time. The essence of the design is to make page migration
inexpensive, to migrate pages while writing them, and to make such migration
optional rather than mandatory as in log-structured file systems. The
inexpensive page migration also aids traditional defragmentation as well
as consolidation of free space needed for future large writes. These advantages
are achieved with a very limited modification to conventional B-trees
that also simplifies other B-tree operations, e.g., key range locking
and compression. Prior proposals and prototypes implemented transacted
B-tree on top of log-structured file systems and added transaction support
to log-structured file systems. Instead, the presented design adds techniques
and performance characteristics of log-structured file systems to traditional
B-trees and their standard transaction support, notably without adding
a layer of indirection for locating B-tree nodes on disk. The result retains
fine-granularity locking, full transactional ACID guarantees, fast search
performance, etc. expected of a modern B-tree implementation, yet adds
efficient transacted page relocation and large, high-bandwidth writes.
Cache-Conscious
Radix-Decluster Projections
Stefan Manegold, Peter Boncz, Martin Kersten, Niels Nes (CWI)
As CPUs become more
powerful with Moore's law and memory latencies stay constant, the impact
of the memory access performance bottleneck continues to grow on relational
operators like join, which can exhibit random access on a memory region
larger than the hardware caches. While cache-conscious variants for various
relational algorithms have been described, previous work has mostly ignored
(the cost of) projection columns. However, real-life joins almost always
come with projections, such that proper projection column manipulation
should be an integral part of any generic join algorithm. In this paper,
we analyze cache-conscious hash-join algorithms including projections
on two storage schemes: N-ary Storage Model (NSM) and Decomposition Storage
Model (DSM). It turns out, that the strategy of first executing the join
and only afterwards dealing with the projection columns (i.e., post-projection)
on DSM, in combination with a new finely tunable algorithm called Radix-Decluster,
outperforms all previously reported projection strategies. To make this
result generally applicable, we also outline how DSM Radix-Decluster can
be integrated in a NSM-based RDBMS using projection indices.
Clotho: Decoupling
Memory Page Layout from Storage Organization
Minglong Shao, Jiri Schindler, Steven Schlosser, Anastassia Ailamaki,
Gregory Ganger (Carnegie Mellon Univ.)
As database application
performance depends on the utilization of the memory hierarchy, smart
data placement plays a central role in increasing locality and in improving
memory utilization. Existing techniques, however, do not optimize accesses
to all levels of the memory hierarchy and for all the different workloads,
because each storage level uses different technology (cache, memory, disks)
and each application accesses data using different patterns. Clotho is
a new buffer pool and storage management architecture that decouples in-memory
page layout from data organization on non-volatile storage devices to
enable independent data layout design at each level of the storage hierarchy.
Clotho can maximize cache and memory utilization by (a) transparently
using appropriate data layouts in memory and non-volatile storage, and
(b) dynamically synthesizing data pages to follow application access patterns
at each level as needed. Clotho creates in-memory pages individually tailored
for compound and dynamically changing workloads, and enables efficient
use of different storage technologies (e.g., disk arrays or MEMS-based
storage devices). This paper describes the Clotho design and prototype
implementation and evaluates its performance under a variety of workloads
using both disk arrays and simulated MEMS-based storage devices.
INDUSTRIAL
SESSION 5: XML IMPLEMENTATIONS AUTOMATIC PHYSICAL DESIGN AND INDEXING
Query Rewrite
for XML in Oracle XML DB
Muralidhar Krishnaprasad, Zhen Liu, Anand Manikutty, James W. Warner,
Vikas Arora, Susan Kotsovolos (Oracle Corp.)
Oracle XML DB integrates
XML storage and querying using the Oracle relational and object relational
framework. It has the capability to physically store XML documents by
shredding them as relational or object relational data, and creating logical
XML documents using SQL/XML publishing functions. However, querying XML
in a relational or object relational database poses several challenges.
The biggest challenge is to efficiently process queries against XML in
a database whose fundamental storage is table-based and whose fundamental
query engine is tuple- oriented. In this paper, we present the 'XML Query
Rewrite' technique used in Oracle XML DB. This technique integrates querying
XML using XPath embedded inside SQL operators and SQL/XML publishing functions
with the object relational and relational algebra. A common set of algebraic
rules is used to reduce both XML and object queries into their relational
equivalent. This enables a large class of XML queries over XML type tables
and views to be transformed into their semantically equivalent relational
or object relational queries. These queries are then amenable to classical
relational optimizations yielding XML query performance comparable to
relational. Furthermore, this rewrite technique lays out a foundation
to enable rewrite of XQuery over XML.
Indexing XML
Data Stored in a Relational Database
Shankar Pal, Istvan Cseri, Gideon Schaller, Oliver Seeliger, Leo Giakoumakis,
Vasili Vasili Zolotov (Microsoft Corp.)
As XML usage grows
for both data-centric and document-centric applications, introducing native
support for XML data in relational databases brings significant benefits.
It provides a more mature platform for the XML data model and serves as
the basis for interoperability between relational and XML data. Whereas
query processing on XML data shredded into one or more relational tables
is well understood, it provides limited support for the XML data model.
XML data can be persisted as a byte sequence (BLOB) in columns of tables
to support the XML model more faithfully. This introduces new challenges
for query processing such as the ability to index the XML blob for good
query performance. This paper reports novel techniques for indexing XML
data in the upcoming version of Microsoft® SQL Server™, and how
it ties into the relational framework for query processing.
Automated Statistics
Collection in DB2 UDB
Ashraf Aboulnaga, Peter Haas (IBM Almaden), Mokhtar Kandil, Sam Lightstone
(IBM Toronto Development Lab), Guy Lohman, Volker Markl (IBM Almaden),
Ivan Popivanov (IBM Toronto Development Lab), Vijayshankar Raman (IBM
Almaden)
The use of inaccurate
or outdated database statistics by the query optimizer in a relational
DBMS often results in a poor choice of query execution plans and hence
unacceptably long query processing times. Configuration and maintenance
of these statistics has traditionally been a time-consuming manual operation,
requiring that the database administrator (DBA) continually monitor query
performance and data changes in order to determine when to refresh the
statistics values and when and how to adjust the set of statistics that
the DBMS maintains. In this paper we describe the new Automated Statistics
Collection (ASC) component of DB2 Stinger. This autonomic technology frees
the DBA from the tedious task of manually supervising the collection and
maintenance of database statistics. ASC monitors both the update-delete-insert
(UDI) activities on the data as well as query feedback (QF), i.e., the
results of the queries that are executed on the data. ASC uses these two
sources of information to automatically decide which statistics to collect
and when to collect them. This combination of UDI-driven and QF-driven
autonomic processes ensures that the system can handle unforeseen queries
while also ensuring good performance for frequent and important queries.
We present the basic concepts, architecture, and key implementation details
of ASC in DB2 Stinger, and present a case study showing how the use of
ASC can speed up a query workload by orders of magnitude without requiring
any DBA intervention.
High Performance
Index Build Algorithms for Intranet Search Engines
Marcus Fontoura, Eugene Shekita, Jason Zien, Sridhar Rajagopalan, Andreas
Neumann (IBM Almaden)
There has been a substantial
amount of research on high-performance algorithms for constructing an
inverted text index. However, constructing the inverted index in a intranet
search engine is only the final step in a more complicated index build
process. Among other things, this process requires an analysis of all
the data being indexed to compute measures like PageRank. The time to
perform this global analysis step is significant compared to the time
to construct the inverted index, yet it has not received much attention
in the research literature. In this paper, we describe how the use of
slightly outdated information from global analysis and a fast index construction
algorithm based on radix sorting can be combined in a novel way to significantly
speed up the index build process without sacrificing search quality.
Automated Design
of Multi-Dimensional Clustering Tables in Relational Databases
Sam Lightstone (IBM Toronto Laboratory), Bishwaranjan Bhattacharjee (IBM
T.J. Watson Research Center)
The ability to physically
cluster a database table on multiple dimensions is a powerful technique
that offers significant performance benefits in many OLAP, warehousing,
and decision-support systems. An industrial implementation of this technique
for the DB2® Universal Database™ (DB2 UDB) product, called multidimensional
clustering (MDC), which co-exists with other classical forms of data storage
and indexing methods, was described in VLDB 2003. This paper describes
the first published model for automating the selection of clustering keys
in single-dimensional and multidimensional relational databases that use
a cell/block storage structure for MDC. For any significant dimensionality
(3 or more), the possible solution space is combinatorially complex. The
automated MDC design model is based on what-if query cost modeling, data
sampling, and a search algorithm for evaluating a large constellation
of possible combinations. The model is effective at trading the benefits
of potential combinations of clustering keys against data scarcity and
performance. It also effectively selects the granularity at which dimensions
should be used for clustering (such as week of year versus month of year).
We show results from experiments indicating that the model provides design
recommendations of comparable quality to those made by human experts.
The model has been implemented in the IBM® DB2 UDB for Linux®,
UNIX® and Windows® Version 8.2 release.
RESEARCH
SESSION 19:PRIVACY
Vision Paper:
Enabling Privacy for the Paranoids
Gagan Aggarwal, Mayank Bawa, Prasanna Ganesan, Hector Garcia-Molina, Krishnaram
Kenthapadi, Nina Mishra, Rajeev Motwani, Utkarsh Srivastava,Dilys Thomas,
Jennifer Widom, Ying Xu (Stanford Univ.)
P3P is a set of standards
that allow corporations to declare their privacy policies. Hippocratic
Databases have been proposed to implement such policies within a corporation's
datastore. From an end-user individual's point of view, both of these
rest on an uncomfortable philosophy of trusting corporations to protect
his/her privacy. Recent history chronicles several episodes when such
trust has been willingly or accidentally violated by corporations facing
bankruptcy courts, civil subpoenas or lucrative mergers. We contend that
data management solutions for information privacy must restore controls
in the individual's hands. We suggest that enabling such control will
require a radical re-think on modeling, release/acquisition, and management
of personal data.
A Privacy-Preserving Index for Range Queries
Bijit Hore, Sharad Mehrotra, Gene Tsudik
Database outsourcing is an emerging data management paradigm which has
the potential to transform the IT operations of corporations. In this
paper we address privacy threats in database outsourcing scenarios where
trust in the service provider is limited. Specifically, we analyze the
data partitioning (bucketization) technique and algorithmically develop
this technique to build privacy-preserving indices on sensitive attributes
of a relational table. Such indices enable an untrusted server to evaluate
obfuscated range queries with minimal information leakage. We analyze
the worst-case scenario of inference attacks that can potentially lead
to breach of privacy (e.g., estimating the value of a data element within
a small error margin) and identify statistical measures of data privacy
in the context of these attacks. We also investigate precise privacy guarantees
of data partitioning which form the basic building blocks of our index.
We then develop a model for the fundamental privacy-utility tradeoff and
design a novel algorithm for achieving the desired balance between privacy
and utility (accuracy of range query evaluation) of the index.
A Privacy-Preserving
Index for Range Queries
Bijit Hore, Sharad Mehrotra, Gene Tsudik (Univ. of California, Irvine)
Database outsourcing
is an emerging data management paradigm which has the potential to transform
the IT operations of corporations. In this paper we address privacy threats
in database outsourcing scenarios where trust in the service provider
is limited. Specifically, we analyze the data partitioning (bucketization)
technique and algorithmically develop this technique to build privacy-preserving
indices on sensitive attributes of a relational table. Such indices enable
an untrusted server to evaluate obfuscated range queries with minimal
information leakage. We analyze the worst-case scenario of inference attacks
that can potentially lead to breach of privacy (e.g., estimating the value
of a data element within a small error margin) and identify statistical
measures of data privacy in the context of these attacks. We also investigate
precise privacy guarantees of data partitioning which form the basic building
blocks of our index. We then develop a model for the fundamental privacy-utility
tradeoff and design a novel algorithm for achieving the desired balance
between privacy and utility (accuracy of range query evaluation) of the
index.
Resilient Rights
Protection for Sensor Streams
Radu Sion, Mikhail Atallah, Sunil Prabhakar (Purdue Univ.)
Today's world of increasingly
dynamic computing environments naturally results in more and more data
being available as fast streams. Applications such as stock market analysis,
environmental sensing, web clicks and intrusion detection are just a few
of the examples where valuable data is streamed. Often, streaming information
is offered on the basis of a non-exclusive, single-use customer license.
One major concern, especially given the digital nature of the valuable
stream, is the ability to easily record and potentially "re-play"
parts of it in the future. If there is value associated with such future
re-plays, it could constitute enough incentive for a malicious customer
(Mallory)to duplicate segments of such recorded data, subsequently re-selling
them for profit. Being able to protect against such infringements becomes
a necessity. In this paper we introduce the issue of rights protection
for discrete streaming data through watermarking. This is a novel problem
with many associated challenges including: operating in a finite window,
single-pass,(possibly) high-speed streaming model, surviving natural domain
specific transforms and attacks (e.g. extreme sparse sampling and summarizations),while
at the same time keeping data alterations within allowable bounds. We
propose a solution and analyze its resilience to various types of attacks
as well as some of the important expected domain-specific transforms,
such as sampling and summarization. We implement a proof of concept software
(wms.*) and perform experiments on real sensor data from the NASA Infrared
Telescope Facility at the University of Hawaii, to assess encoding resilience
levels in practice. Our solution proves to be well suited for this new
domain. For example, we can recover an over97% confidence watermark from
a highly down-sampled (e.g. less than8%) stream or survive stream summarization
(e.g. 20%) and random alteration attacks with very high confidence levels,
often above 99%.
RESEARCH
SESSION 20: NEAREST NEIGHBOR SEARCH
Reverse kNN
Search in Arbitrary Dimensionality
Yufei Tao (City University of Hong Kong), Dimitris Papadias, Xiang Lian
(Hong Kong University of Science and Technology)
Given a point q, a
reverse k nearest neighbor (RkNN) query retrieves all the data points
that have q as one of their k nearest neighbors. Existing methods for
processing such queries have at least one of the following deficiencies:
(i) they do not support arbitrary values of k (ii) they cannot deal efficiently
with database updates, (iii) they are applicable only to 2D data (but
not to higher dimensionality), and (iv) they retrieve only approximate
results. Motivated by these shortcomings, we develop algorithms for exact
processing of RkNN with arbitrary values of k on dynamic datasets of any
dimensionality. Our methods utilize a conventional multi-dimensional index
on the dataset and do not require any pre-computation. In addition to
their flexibility, we experimentally verify that the proposed algorithms
outperform the existing ones even in their restricted focus.
GORDER: An Efficient
Method for KNN Join Processing
Chenyi Xia (National University of Singapore), Hongjun Lu (Hong Kong University
of Science and Technology), Beng Chin Ooi, Jin Hu (National University
of Singapore)
An important but very
expensive primitive operation of high-dimensional databases is the K-Nearest
Neighbor (KNN)similarity join. The operation combines each point of one
dataset with its KNNs in the other dataset and it provides more meaningful
query results than the range similarity join. Such an operation is useful
for data mining and similarity search. In this paper, we propose a novel
KNN-join algorithm, called the Gorder (or the G-ordering KNN) join method.
Gorder is a block nested loop join method that exploits sorting, join
scheduling and distance computation filtering and reduction to reduce
both I/O and CPU costs. It sorts input datasets into the G-order and applied
the scheduled block nested loop join on the G-ordered data. The distance
computation reduction is employed to further reduce CPU cost. It is simple
and yet efficient, and handles high-dimensional data efficiently. Extensive
experiments on both synthetic cluster and real life datasets were conducted,
and the results illustrate that Gorder is an efficient KNN-join method
and outperforms existing methods by a wide margin.
Query and Update
Efficient B+-Tree Based Indexing of Moving Objects
Christian S. Jensen (Aalborg Univ.), Dan Lin, Beng Chin Ooi (National
Univ. of Singapore)
A number of emerging
applications of data management technology involve the monitoring and
querying of large quantities of continuous variables, e.g., the positions
of mobile service users, termed moving objects. In such applications,
large quantities of state samples obtained via sensors are streamed to
a database. Indexes for moving objects must support queries efficiently,
but must also support frequent updates. Indexes based on minimum bounding
regions (MBRs) such as the R-tree exhibit high concurrency overheads during
node splitting, and each individual update is known to be quite costly.
This motivates the design of a solution that enables the B+-tree to manage
moving objects. We represent moving-object locations as vectors that are
time stamped based on their update time. By applying a novel linearization
technique to these values, it is possible to index the resulting values
using a single B+-tree that partitions values according to their timestamp
and otherwise preserves spatial proximity. We develop algorithms for range
and k nearest neighbor queries, as well as continuous queries. The proposal
can be grafted into existing database systems cost effectively. An extensive
experimental study explores the performance characteristics of the proposal
and also shows that it is capable of substantially outperforming the R-tree
based TPR-tree for both single and concurrent access scenarios.
INDUSTRIAL
SESSION 6: DATA MANAGEMENT WITH RFIDS AND EASE OF USE TERRITORIES
Integrating
Automatic Data Acquisition with Business Processes Experiences with SAP's
Auto-ID Infrastructure
Christof Bornhövd, Tao Lin, Stephan Haller, Joachim Schaper (SAP
Research)
Smart item technologies,
like RFID and sensor networks, are considered to be the next big step
in business process automation. Through automatic and real-time data acquisition,
these technologies can benefit a great variety of industries by improving
the efficiency of their operations. SAP's Auto-ID infrastructure enables
the integration of RFID and sensor technologies with existing business
processes. In this paper we give an overview of the existing infrastructure,
discuss lessons learned from successful customer pilots, and point out
some of the open research issues.
Managing
RFID Data (invited)
Sudarshan S. Chawathe (Univ. of Maryland), Venkat Krishnamurthy, Sridhar
Ramachandrany (OAT Systems), and Sanjay Sarma (MIT)
Production Database
Systems: Making Them Easy is Hard Work
David Campbell (Microsoft Corporation)
Enterprise capable
database products have evolved into incredibly complex systems, some of
which present hundreds of configuration parameters to the system administrator.
So, while the processing and storage costs for maintaining large volumes
of data have plummeted, the human costs associated with maintaining the
data have continued to rise. In this presentation, we discuss the framework
and approach used by the team who took Microsoft SQL Server from a state
where it had several hundred configuration parameters to a system that
can configure itself and respond to changes in workload and environment
with little human intervention.
RESEARCH
SESSION 21:SIMILARITY SEARCH AND APPLICATIONS
Indexing Large
Human-Motion Databases
Eamonn Keogh, Themistoklis Palpanas, Victor B. Zordan, Dimitrios Gunopulos
(Univ. of California, Riverside), Marc Cardle (Univ. of Cambridge)
Data-driven animation
has become the industry standard for computer games and many animated
movies and special effects. In particular, motion capture data recorded
from live actors, is the most promising approach offered thus far for
animating realistic human characters. However, the manipulation of such
data for general use and re-use is not yet a solved problem. Many of the
existing techniques dealing with editing motion rely on indexing for annotation,
segmentation, and re-ordering of the data. Euclidean distance is inappropriate
for solving these indexing problems because of the inherent variability
found in human motion. The limitations of Euclidean distance stems from
the fact that it is very sensitive to distortions in the time axis. A
partial solution to this problem, Dynamic Time Warping (DTW), aligns the
time axis before calculating the Euclidean distance. However, DTW can
only address the problem of local scaling. As we demonstrate in this paper,
global or uniform scaling is just as important in the indexing of human
motion. We propose a novel technique to speed up similarity search under
uniform scaling, based on bounding envelopes. Our technique is intuitive
and simple to implement. We describe algorithms that make use of this
technique, we perform an experimental analysis with real datasets, and
we evaluate it in the context of a motion capture processing system. The
results demonstrate the utility of our approach, and show that we can
achieve orders of magnitude of speedup over the brute force approach,
the only alternative solution currently available.
On The Marriage
of Lp-norms and Edit Distance
Lei Chen (Univ. of Waterloo), Raymond Ng (Univ. of British Columbia)
Existing studies on
time series are based on two categories of distance functions. The first
category consists of the Lp-norms. They are metric distance functions
but cannot support local time shifting. The second category consists of
distance functions which are capable of handling local time shifting but
are non-metric. The first contribution of this paper is the proposal of
a new distance function, which we call ERP ("Edit distance with Real
Penalty"). Representing a marriage ofL1-norm and the edit distance,
ERP can support local time shifting, and is a metric. The second contribution
of the paper is the development of pruning strategies for large time series
databases. Given that ERP is a metric, one way to prune is to apply the
triangle inequality. Another way to prune is to develop a lower bound
on the ERPdistance. We propose such a lower bound, which has the nice
computational property that it can be efficiently indexed with a standard
B+-tree. Moreover, we show that these two ways of pruning can be used
simultaneously for ERP distances. Specifically, the false positives obtained
from the B+-tree can be further minimized by applying the triangle inequality.
Based on extensive experimentation with existing benchmarks and techniques,
we show that this combination delivers superb pruning power and search
time performance, and dominates all existing strategies.
Approximate
NN queries on Streams with Guaranteed Error/performance Bounds
Nick Koudas (AT&T Labs-Research), Beng Chin Ooi, Kian-Lee Tan, Rui
Zhang (National Univ. of Singapore)
In data stream applications,
data arrive continuously and can only be scanned once as the query processor
has very limited memory(relative to the size of the stream) to work with.
Hence, queries on data streams do not have access to the entire data set
and query answers are typically approximate. While there have been many
studies on the k Nearest Neighbors (kNN) problem in conventional multi-dimensional
databases, the solutions cannot be directly applied to data streams for
the above reasons. In this paper, we investigate the kNN problem over
data streams. We first introduce the $e$-approximate kNN (ekNN) problem
that finds the approximate kNN answers of a query point $Q$ such that
the absolute error of the k-th nearest neighbor distance is bounded by
$e$. To support ekNN queries over streams, we propose a technique called
DISC (aDaptive Indexing on Streams by space-filling Curves). DISC can
adapt to different data distributions to either(a)~optimize memory utilization
to answer ekNN queries under certain accuracy requirements or (b) achieve
the best accuracy under a given memory constraint. At the same time, DISC
provide efficient updates and query processing which are important requirements
in data stream applications. Extensive experiments were conducted using
both synthetic and real data sets and the results confirm the effectiveness
and efficiency of DISC.
Object Fusion
in Geographic Information Systems
Catriel Beeri, Yaron Kanza, Eliyahu Safra, Yehoshua Sagiv (The Hebrew
Univ.)
Given two geographic
databases, a fusion algorithm should produce all pairs of corresponding
objects (i.e., objects that represent the same real-world entity). Four
fusion algorithms, which only use locations of objects, are described
and their performance is measured in terms of recall and precision. These
algorithms are designed to work even when locations are imprecise and
each database represents only some of the real-world entities. Results
of extensive experimentation are presented and discussed. The tests show
that the performance depends on the density of the data sources and the
degree of overlap among them. All four algorithms are much better than
the current state of the art (i.e., the one-sided nearest-neighbor join).
One of these four algorithms is best in all cases, at a cost of a small
increase in the running time compared to the other algorithms.
Maintenance
of Spatial Semijoin Queries on Moving Points
Glenn Iwerks, Hanan Samet (Univ. of Maryland at College Park), Kenneth
Smith (MITRE Corp.)
In this paper, we
address the maintenance of spatial semijoin queries over continuously
moving points, where points are modeled as linear functions of time. This
is analogous to the maintenance of a materialized view except, as time
advances, the query result may change independently of updates. As in
a materialized view, we assume there is no prior knowledge of updates
before they occur. We present a new approach, continuous fuzzy sets (CFS),
to maintain continuous spatial semijoins efficiently. CFS is compared
experimentally to a simple scaling of previous work. The result is significantly
better performance of CFS compared to previous work by up to an order
of magnitude in some cases.
Voronoi-Based
K Nearest Neighbor Search for Spatial Network Databases
Mohammad Kolahdouzan, Cyrus Shahabi (Univ. of Southern California)
A frequent type of
query in spatial networks (e.g., road networks)is to find the K nearest
neighbors (KNN) of a given query object. With these networks, the distances
between objects depend on their network connectivity and it is computationally
expensive to compute the distances (e.g., shortest paths) between objects.
In this paper, we propose a novel approach to efficiently and accurately
evaluate KNN queries in spatial network databases using first order Voronoi
diagram. This approach is based on partitioning a large network to small
Voronoi regions, and then pre-computing distances both within and across
the regions. By localizing the pre-computation within the regions, we
save on both storage and computation and by performing across-the-network
computation for only the border points of the neighboring regions, we
avoid global pre-computation between every node-pair. Our empirical experiments
with several real-world data sets show that our proposed solution outperforms
approaches that are based on on-line distance computation by up to one
order of magnitude, and provides a factor of four improvement in the selectivity
of the filter step as compared to the index-based approaches.
A Framework
for Projected Clustering of High Dimensional Data Streams
Charu Aggarwal (T.J. Watson Res. Ctr.), Jiawei Han, Jianyong Wang (UIUC),
Philip Yu (T.J. Watson Res. Ctr.)
The data stream problem
has been studied extensively in recent years, because of the great ease
in collection of stream data. The nature of stream data makes it essential
to use algorithms which require only one pass over the data. Recently,
single-scan, stream analysis methods have been proposed in this context.
However, a lot of stream data is high-dimensional in nature. High-dimensional
data is inherently more complex in clustering, classification, and similarity
search. Recent research discusses methods for projected clustering over
high-dimensional data sets. This method is however difficult to generalize
to data streams because of the complexity of the method and the large
volume of the data streams. In this paper, we propose a new, high-dimensional,
projected data stream clustering method, called HPStream. The method incorporates
a fading cluster structure, and the projection based clustering methodology.
It is incrementally updatable and is highly scalable on both the number
of dimensions and the size of the data streams, and it achieves better
clustering quality in comparison with the previous stream clustering methods.
Our performance study with both real and synthetic data sets demonstrates
the efficiency and effectiveness of our proposed framework and implementation
methods.
RESEARCH
SESSION 22:QUERY PROCESSING
Efficient Query
Evaluation on Probabilistic Databases
Nilesh Dalvi, Dan Suciu (Univ. of Washington)
We describe a system
that supports arbitrarily complex SQL queries on probabilistic databases.
The query semantics is based on a probabilistic model and the results
are ranked, much like in Information Retrieval. Our main focus is efficient
query evaluation, a problem that has not received attention in the past.
We describe an optimization algorithm that can compute efficiently most
queries. We show, however, that the data complexity of some queries is
#P-complete, which implies that these queries do not admit any efficient
evaluation methods. For these queries we describe both an approximation
algorithm and a Monte-Carlo simulation algorithm.
Efficient Indexing
Methods for Probabilistic Threshold Queries over Uncertain Data
Reynold Cheng, Yuni Xia, Sunil Prabhakar, Rahul Shah, Jeffrey S. Vitter
(Purdue Univ.)
It is infeasible for
a sensor database to contain the exact value of each sensor at all points
in time. This uncertainty is inherent in these systems due to measurement
and sampling errors, and resource limitations. In order to avoid drawing
erroneous conclusions based upon stale data, the use of uncertainty intervals
that model each data item as a range and associated probability density
function (pdf) rather than a single value has recently been proposed.
Querying these uncertain data introduces imprecision into answers, in
the form of probability values that specify the likeliness the answer
satisfies the query. These queries are more expensive to evaluate than
their traditional counterparts but are guaranteed to be correct and more
informative due to the probabilities accompanying the answers. Although
the answer probabilities are useful, for many applications, it is only
necessary to know whether the probability exceeds a given threshold --
we term these Probabilistic Threshold Queries (PTQ). In this paper we
address the efficient computation of these types of queries. In particular,
we develop two index structures and associated algorithms to efficiently
answer PTQs. The first index scheme is based on the idea of augmenting
uncertainty information to an R-tree. We establish the difficulty of this
problem by mapping one-dimensional intervals to a two-dimensional space,
and show that the problem of interval indexing with probabilities is significantly
harder than interval indexing which is considered a well-solved problem.
To overcome the limitations of this R-tree based structure, we apply a
technique called variance based clustering, where data points with similar
degrees of uncertainty are clustered together. Our extensive index structure
can answer the queries for various kinds of uncertainty pdfs, in an almost
optimal sense. Extensive experimental evaluations are carried out to compare
the effectiveness of various techniques.
Probabilistic
Ranking of Database Query Results
Surajit Chaudhuri, Gautam Das (Microsoft Research), Vagelis Hristidis
(Florida International Univ.), Gerhard Weikum (MPI Informatik)
We investigate the
problem of ranking answers to a database query when many tuples are returned.
We adapt and apply principles of probabilistic models from Information
Retrieval for structured data. Our proposed solution is domain-independent.
It leverages data and workload statistics and correlations. Our ranking
functions can be further customized for different applications. We present
results of preliminary experiments which demonstrate the efficiency as
well as the quality of our ranking system.
INDUSTRIAL
SESSION 7: DATA MANAGEMENT CHALLENGES IN LIFE SCIENCES AND EMAIL SYSTEMS
Managing Data
from High-Throughput Genomic Processing: A Case Study (invited)
Toby Bloom, Ted Sharpe (Broad Institute of MIT and Harvard)
Genomic data has become
the canonical example of very large, very complex data sets. As such,
there has been significant interest in ways to provide targeted database
support to address issues that arise in genomic processing. Whether genomic
data is truly a special case, or just another application area exhibiting
problems common to other domains, is an as yet unanswered question. In
this abstract, we explore the structure and processing requirements of
a large-scale genome sequencing center, as a case study of the issues
that arise in genomic data managements, and as a means to compare those
issues with those that arise in other domains.
Database Challenges
in the Integration of Biomedical Data Sets (invited)
Rakesh Nagarajan (Washington University, School of Medicine), Mushtaq
Ahmed (Persistent Systems Pvt. Ltd.), Aditya PhatakAditya Phatak (Persistent
Systems Pvt. Ltd.)
The clinical and basic
science research domains present exciting and difficult data integration
issues. Solving these problems is crucial as current research efforts
in the field of biomedicine heavily depend upon integrated storage, querying,
analysis, and visualization of clinicopathology information, genomic annotation,
and large scale functional genomic research data sets. Such large scale
experimental analyses are essential to decipher the pathophysiological
processes occurring in most human diseases so that they may be effectively
treated. In this paper, we discuss the challenges of integration of multiple
biomedical data sets n ot only at the university level but also at the
national level and present the data warehousing based solution we have
employed at Washington University School of Medicine. We also describe
the tools we have developed to store, query, analyze, and visualize these
data sets together.
The Bloomba
Personal Content Database (invited)
Raymie Stata (UC Santa Cruz), Patrick Hunt (Stata Labs), Thiruvalluvan
M. G. (iSoftTech Ltd.)
We believe continued
growth in the volume of personal content, together with a shift to a multi-device
personal computing environment, will inevitably lead to the development
of Personal Content Databases (PCDBs). These databases will make it easier
for users to find, use, and replicate large, heterogeneous repositories
of personal content. In this paper, we describe the PCDB used to power
Bloomba, a commercial personal information manager in broad use. We highlight
areas where the special requirements of personal content and personal
platforms have influenced the design and implementation of our PCDB. We
also discuss what we have and have not been able to leverage from the
database community and suggest a few lines of research that would be useful
to builders of PCDBs.
RESEARCH
SESSION 23:NOVEL MODELS
An Annotation
Management System for Relational Databases
Deepavali Bhagwat, Laura Chiticariu, Wang-Chiew Tan, Gaurav Vijayvargiya
(Univ. of California, Santa Cruz)
We present an annotation
management system for relational databases. In this system, every piece
of data in a relation is assumed to have zero or more annotations associated
with it and annotations are propagated along, from the source to the output,
as data is being transformed through a query. Such an annotation management
system is important for understanding the provenance and quality of data,
especially in applications that deal with integration of scientific and
biological data. We present an extension, pSQL, of a fragment of SQL that
has three different types of annotation propagation schemes, each useful
for different purposes. The default scheme propagates annotations according
to where data is copied from. The default-all scheme propagates annotations
according to where data is copied from among all equivalent formulations
of a given query. The custom scheme allows a user to specify how annotations
should propagate. We present a storage scheme for the annotations and
describe algorithms for translating a pSQL query under each propagation
scheme into one or more SQL queries that would correctly retrieve the
relevant annotations according to the specified propagation scheme. For
the default-all scheme, we also show how we generate finitely many queries
that can simulate the annotation propagation behavior of the set of all
equivalent queries, which is possibly infinite. The algorithms are implemented
and the feasibility of the system is demonstrated by a set of experiments
that we have conducted.
Symmetric Relations
and Cardinality-Bounded Multisets in Database Systems
Kenneth Ross, Julia Stoyanovich (Columbia Univ.)
In a binary symmetric
relationship, A is related to B if and only if B is related to A. Symmetric
relationships between k participating entities can be represented as multisets
of cardinality k. Cardinality-bounded multisets are natural in several
real-world applications. Conventional representations in relational databases
suffer from several consistency and performance problems. We argue that
the database system itself should provide native support for cardinality-bounded
multisets. We provide techniques to be implemented by the database engine
that avoid the drawbacks, and allow a schema designer to simply declare
a table to be symmetric in certain attributes. We describe a compact data
structure, and update methods for the structure. We describe an algebraic
symmetric closure operator, and show how it can be moved around in a query
plan during query optimization in order to improve performance. We describe
indexing methods that allow efficient lookups on the symmetric columns.
We show how to perform database normalization in the presence of symmetric
relations. We provide techniques for inferring that a view is symmetric.
We also describe a syntactic SQL extension that allows the succinct formulation
of queries over symmetric relations.
Algebraic Manipulation
of Scientific Datasets
Bill Howe, David Maier (Oregon Health & Science University)
We investigate algebraic
processing strategies for large numeric datasets equipped with a possibly
irregular grid structure. Such datasets arise, for example, in computational
simulations, observation networks, medical imaging, and 2-D and 3-D rendering.
Existing approaches for manipulating these datasets are incomplete: The
performance of SQL queries for manipulating large numeric datasets is
not competitive with specialized tools. Database extensions for processing
multidimensional discrete data can only model regular, rectilinear grids.
Visualization software libraries are designed to process gridded datasets
efficiently, but no algebra has been developed to simplify their use and
afford optimization. Further, these libraries are data dependent --physical
changes to data representation or organization break user programs. In
this paper, we present an algebra of grid fields for manipulating both
regular and irregular gridded datasets, algebraic optimization techniques,
and an implementation backed by experimental results. We compare our techniques
to those of spatial databases and visualization software libraries, using
real examples from an Environmental Observation and Forecasting System.
We find that our approach can express optimized plans inaccessible to
other techniques, resulting in improved performance with reduced programming
effort.
RESEARCH
SESSION 24:QUERY PROCESSING AND OPTIMIZATION
Multi-objective
Query Processing for Database Systems
Wolf-Tilo Balke (Univ. of California, Berkeley), Ulrich Guntzer (University
of Tübingen)
Query processing in
database systems has developed beyond mere exact matching of attribute
values. Scoring database objects and retrieving only the top k matches
or Pareto-optimal result sets (skyline queries) are already common for
a variety of applications. Specialized algorithms using either paradigm
can avoid naïve linear database scans and thus improve scalability.
However, these paradigms are only two extreme cases of exploring viable
compromises for each user's objectives. To find the correct result set
for arbitrary cases of multi-objective query processing in databases we
will present a novel algorithm for computing sets of objects that are
non-dominated with respect to a set of monotonic objective functions.
Naturally containing top k and skyline retrieval paradigms as special
cases, this algorithm maintains scalability also for all cases in between.
Moreover, we will show the algorithm's correctness and instance-optimality
in terms of necessary object accesses and how the response behavior can
be improved by progressively producing result objects as quickly as possible,
while the algorithm is still running.
Lifting the
Burden of History from Adaptive Query Processing
Amol Deshpande (Univ. of California, Berkeley), Joseph M. Hellerstein
(Univ. of California, Berkeley and Intel Research, Berkeley)
Adaptive query processing
schemes attempt to reoptimize query plans during the course of query execution.
A variety of techniques for adaptive query processing have been proposed,
varying in the granularity at which they can make decisions. The eddy
is the most aggressive of these techniques, with the flexibility to choose
tuple-by-tuple how to order the application of operators. In this paper
we identify and address a fundamental limitation of the original eddies
proposal: the "burden of history" in routing. We observe that
routing decisions have long-term effects on the state of operators in
the query, and can severely constrain the ability of the eddy to adapt
over time. We then propose a mechanism we call STAIRs that allows the
query engine to manipulate the state stored inside the operators and undo
the effects of past routing decisions. We demonstrate that eddies with
STAIRs achieve both high adaptively and good performance in the face of
uncertainty, outperforming prior eddy proposals by orders of magnitude.
A Combined Framework
for Grouping and Order Optimization
T Thomas Neumann, Guido Moerkotte (University of Mannheim)
Since the introduction
of cost-based query optimization by Selinger et al. in their seminal paper,
the performance-critical role of interesting orders has been recognized.
Some algebraic operators change interesting orders (e.g. sort and select),while
others exploit them (e.g. merge join).Likewise, Wang and Cherniack (VLDB
2003) showed that existing groupings should be exploited to avoid redundant
grouping operations. Ideally, the reasoning about interesting orderings
and groupings should be integrated into one framework. So far, no complete,
correct, and efficient algorithm for ordering and grouping inference has
been proposed. We fill this gap by proposing a general two-phase approach
that efficiently integrates the reasoning about orderings and groupings.
Our experimental results show that with a modest increase of the time
and space requirements of the preprocessing phase both orderings and groupings
can be handled at the same time. More importantly, there is no additional
cost for the second phase during which the plan generator changes and
exploits orderings and groupings by adding operators to subplans.
The Case for
Precision Sharing
Sailesh Krishnamurthy, Michael J. Franklin (UC Berkeley), Joseph M. Hellerstein
(UC Berkeley and Intel Research Berkeley), Garrett Jacobson (UC Berkeley)
Sharing has emerged
as a key idea of static and adaptive stream query processing systems.
Inherent in these systems is a tension between sharing common work and
avoiding unnecessary work. Increased sharing has generally led to more
unnecessary work. Our approach of precision sharing aims to share aggressively
without unnecessary work. We show why "adaptive" tuple lineage
is more generally applicable and use it for precisely shared static dataflows.
We also show how "static" ordering constraints can be used for
precision sharing in adaptive systems. Finally, we report an experimental
study of precision sharing.
INDUSTRIAL
SESSION 8: ISSUES IN DATA WAREHOUSING
Trends
in Data Warehousing (invited)
William O'Connell (IBM Toronto Laboratory)
This talk will
present emerging data warehousing reference architectures, and focus on
trends and directions that are shaping these enterprise installations.
Implications will be highlighted, including both of new and old technology.
Stack seamless integration is also pivotal to success, which also has
significant implications on things such as Metadata.
Data Warehouse
Technology Challenges (invited)
Ramesh Bhashyam (Teradata Corporation)
This presentation
will discuss several database technology challenges that are faced when
building a data warehouse. It will touch on the challenges posed by high
capacity drives and the mechanisms in Teradata DBMS to address that. It
will consider the features and capabilities required of a database in
a mixed application environment of a warehouse and some solutions to address
that.
Sybase IQ Multiplex
– Designed For Analytics (invited)
Roger MacNicol, Blaine French (Sybase Inc.)
The internal design
of database systems has traditionally given primacy to the needs of transactional
data. A radical re-evaluation of the internal design giving primacy to
the needs of complex analytics shows clear benefits in large databases
for both single servers and in multi-node shared-disk grid computing.
This design supports the trend to keep more years of more finely grained
data online by ameliorating the data explosion problem.
DEMO
GROUP 1: DATA MINING
GPX: Interactive
Mining of Gene Expression Data
Daxin Jiang, Jian Pei and Aidong Zhang (State University of New York at
Buffalo, USA)
Discovering co-expressed
genes and coherent expression patterns in gene expression data is an important
data analysis task in bioinformatics research and biomedical applications.
Although various clustering methods have been proposed, two tough challenges
still remain on how to integrate the users' domain knowledge and how to
handle the high connectivity in the data. Recently, we have systematically
studied the problem and proposed an effective approach. In this paper,
we describe a demonstration of GPX (for Gene Pattern eXplorer), an integrated
environment for interactive exploration of coherent expression patterns
and co-expressed genes in gene expression data. GPX integrates several
novel techniques, including the coherent pattern index graph, a gene annotation
panel, and a graphical interface, to adopt users' domain knowledge and
support explorative operations in the clustering procedure. The GPX system
as well as its techniques will be showcased, and the progress of GPX will
be exemplified using several real-world gene expression data sets.
Computing Frequent Itemsets Inside Oracle 10G
Wei Li, and Ari Mozes (Oracle Corporation, USA)
Frequent itemset counting
is the first step for most association rule algorithms and some classification
algorithms. It is the process of counting the number of occurrences of
a set of items that happen across many transactions. The goal is to find
those items which occur together most often. Expressing this functionality
in RDBMS engines is difficult for two reasons. First, it leads to extremely
inefficient execution when using existing RDBMS operations since they
are not designed to handle this type of workload. Second, it is difficult
to express the special output type of itemsets. In Oracle 10G, we introduce
a new SQL table function which encapsulates the work of frequent itemset
counting. It accepts the input dataset along with some user-configurable
information, and it directly produces the frequent itemset results. We
present examples of typical computations with frequent itemset counting
inside Oracle 10G. We also describe how Oracle dynamically adapts during
frequent itemset execution as a result of changes in the nature of the
data as well as changes in the available system resources.
StreamMiner:
A Classifier Ensemble-based Engine to Mine Concept-drifting Data Streams
Wei Fan (IBM T.J. Watson Research, USA)
We demonstrate StreamMiner,
a random decision-tree ensemble based engine to mine data streams. A fundamental
challenge in data stream mining applications (e.g., credit card transaction
authorization, security buy-sell transaction, and phone call records,
etc) is concept-drift or the discrepancy between the previously learned
model and the true model in the new data. The basic problem is the ability
to judiciously select data and adapt the old model to accurately match
the changed concept of the data stream. StreamMiner uses several techniques
to support mining over data streams with possible concept-drifts. We demonstrate
the following two key functionalities of StreamMiner: Detecting possible
concept-drift on the fly when the trained streaming model is used to classify
incoming data streams without knowing the ground truth. Systematic data
selection of old data and new data chunks to compute the optimal model
that best fits on the changing data streams.
Semantic Mining
and Analysis of Gene Expression Data
Xin Xu, Gao Cong, Beng Chin Ooi, Kian-Lee Tan, and Anthony K.H.Tung (National
University of Singapore)
Association rules
can reveal biological relevant relationship between genes and environments
/ categories. However, most existing association rule mining algorithms
are rendered impractical on gene expression data, which typically contains
thousands or tens of thousands of columns (gene expression levels), but
only tens of rows (samples). The main problem is that these algorithms
have an exponential dependence on the number of columns. Another shortcoming
is evident that too many associations are generated from such kind of
data. To this end, we have developed a novel depth-first row-wise algorithm
FARMER that is specially designed to efficiently discover and cluster
association rules into interesting rule groups (IRGs) that satisfy user-specified
minimum support, confidence and chi-square value thresholds on biological
datasets as opposed to finding association rules individually. Based on
FARMER, we have developed a prototype system that integrates semantic
mining and visual analysis of IRGs mined from gene expression data.
HOS-Miner: A
System for Detecting Outlying Subspaces of High-dimensional Data
Ji Zhang, Meng Lou (University of Toronto, Canada), Tok Wang Ling (National
University of Singapore), Hai Wang (University of Toronto, Canada)
We identify a new
and interesting high-dimensional outlier detection problem in this paper,
that is, detecting the subspaces in which given data points are outliers.
We call the subspaces in which a data point is an outlier as its Outlying
Subspaces. In this paper, we will propose the prototype of a dynamic subspace
search system, called HOS-Miner (HOS stands for High-dimensional Outlying
Subspaces), that utilizes a sample-based learning process to effectively
identify the outlying subspaces of a given point.
VizTree: a Tool
for Visually Mining and Monitoring Massive Time Series Databases
Jessica Lin, Eamonn Keogh, Stefano Lonardi (University of California,
Riverside, USA), Jeffrey P. Lankford, and Donna M. Nystrom (The Aerospace
Corporation, USA)
Moments before the
launch of every space vehicle, engineering discipline specialists must
make a critical go/no-go decision. The cost of a false positive, allowing
a launch in spite of a fault, or a false negative, stopping a potentially
successful launch, can be measured in the tens of millions of dollars,
not including the cost in morale and other more intangible detriments.
The Aerospace Corporation is responsible for providing engineering assessments
critical to the go/no-go decision for every Department of Defense (DoD)
launch vehicle. These assessments are made by constantly monitoring streaming
telemetry data in the hours before launch. For this demonstration, we
will introduce VizTree, a novel time-series visualization tool to aid
the Aerospace analysts who must make these engineering assessments. VizTree
was developed at the University of California, Riverside and is unique
in that the same tool is used for mining archival data and monitoring
incoming live telemetry. Unlike other time series visualization tools,
VizTree can scale to very large databases, giving it the potential to
be a generally useful data mining and database tool.
DEMO
GROUP 2: DISTRIBUTED DATABASES
An Electronic
Patient Record ``on Steroids'': Distributed, Peer-to-Peer, Secure and
Privacy-conscious
Serge Abiteboul (INRIA, France), Bogdan Alexe (Bell Labs, Lucent Technologies,
USA), Omar Benjelloun, Bogdan Cautis (INRIA, France), Irini Fundulaki
(Bell Labs, Lucent Technologies, USA), Tova Milo (INRIA, France, and Tel-Aviv
University, Israel), and Arnaud Sahuguet (Tel-Aviv University, Israel)
We demonstrate a novel
solution for the privacy-conscious integration of distributed data, that
relies on the combination of two key technologies: Active XML, that provides
a highly flexible peer-to-peer paradigm for data integration, and GUPster,
that unifies the enforcement of access control and source descriptions.
While each of these two technologies has been demonstrated separately
before, we show here that their synergy yields a powerful generic platform
that seamlessly handles data integration and privacy enforcement tasks
in a highly distributed setting.
Queries and
Updates in the coDB Peer to Peer Database System
Enrico Franconi (Free University of Bozen-Bolzano, Italy), Gabriel Kuper
(University of Trento, Italy), Andrei Lopatenko (University of Bozen-Bolzano,
Italy, and University of Manchester, UK), and Ilya Zaihrayeu (University
of Trento, Italy)
In this short paper
we present the coDB P2P DB system. A network of databases, possibly with
different schemas, are interconnected by means of GLAV coordination rules,
which are inclusions of conjunctive queries, with possibly existential
variables in the head; coordination rules may be cyclic. Each node can
be queried in its schema for data, which the node can fetch from its neighbors,
if a coordination rule is involved.
A-ToPSS: A Publish/Subscribe
System Supporting Imperfect Information Processing
Haifeng Liu and Hans-Arno Jacobsen (University of Toronto)
In the publish/subscribe
paradigm, information providers disseminate publications to all consumers
who have expressed interest by registering subscriptions with the publish/subscribe
system. This paradigm has found wide-spread applications, ranging from
selective information dissemination to network management. In all existing
publish/subscribe systems, neither subscriptions nor publications can
capture uncertainty inherent to the information underlying the application
domain. However, in many situations, exact knowledge of either specific
subscriptions, or publications, is not available. To address this problem,
we demonstrate a new publish/subscribe model based on possibility theory
and fuzzy set theory to process imperfect information for, either expressing
subscriptions, or publications, or both combined. Furthermore, a solid
system is developed to experiment the new model.
Efficient Constraint
Processing for Highly Personalized Location Based Services
Zhengdao Xu, and Hans-Arno Jacobsen (University of Toronto, Canada)
Recently, with the
advances in wireless communications and location positioning technology,
the potential for tracking, correlating, and filtering information about
moving entities has greatly increased. In this demonstration, we define
two types of the location constraints, n-body and n-body (static) constraints,
which model the correlation among a set of moving objects, and demonstrate
an algorithm that efficiently evaluates those location constraints. We
will show that our algorithm using Kd-tree indexing outperform the naïve
approach even with little overhead for the partition update.
LH*RS: A Highly
Available Distributed Storage System
Witold Litwin, Rim Moussa (Universit'e Paris Dauphine, France), and Thomas
Schwarz (Santa Clara University, USA)
The ideal storage
system is always available and incrementally expandable. Existing storage
systems fall far from this ideal. Affordable computers and high-speed
networks allow us to investigate storage architectures closer to the ideal.
Our demo, present a prototype implementation of LH*RS: a highly available
scalable and distributed data structure.
DEMO
GROUP 3: XML
Semantic Query
Optimization in an Automata-Algebra Combined XQuery Engine over XML Streams
Hong Su, Elke A. Rundensteiner and Murali Mani (Worcester Polytechnic
Institute, USA)
Our raindrop system
tackles challenges of stream processing that are particular to XML. This
demo demonstrates two major aspects. First, it demonstrates the modeling
issues, i.e., how to take advantage of both token-based automata paradigm
and tuple-based algebraic paradigm for processing XQuery over XML streams.
Second, it demonstrates the optimization issues, i.e., how to use schema
knowledge to optimize an XQuery over XML streams based on our modeling.
ShreX: Managing
XML Documents in Relational Databases
Fang Du (OGI/OHSU, USA), Sihem Amer-Yahia (AT&T Labs, USA), and Juliana
Freire (OGI/OHSU, USA)
We describe ShreX,
a freely-available system for shredding, loading and querying XML documents
in relational databases. ShreX supports all mapping strategies proposed
in the literature as well as strategies available in commercial RDBMSs.
It provides generic (mapping-independent) functions for loading shredded
documents into relations and for translating XML queries into SQL. ShreX
is portable and can be used with any relational database backend.
A Uniform System
for Publishing and Maintaining XML Data
Byron Choi, Wenfei Fan, Xibei Jia (University of Edinburgh, UK), and Arek
Kasprzyk (European Bioinformatics Institute)
Taking real-life data
from Gene Ontology (GO), this demonstration shows how a uniform system
can efficiently publish the GO data in XML with respect to predefined
recursive target DTDs, and how it incrementally updates the target XML
data in response to changes to the underlying GO database.
An Injection of Tree Awareness: Adding Staircase Join to PostgreSQL
Sabine Mayer, Torsten Grust (University of Konstanz, Germany), Maurice
van Keulen (University of Twente, The Netherlands), and Jens Teubner (University
of Konstanz, Germany)
The syntactic well
formedness constraints of XML (opening and closing tags nest properly)
imply that XML processors face the challenge to efficiently handle data
that takes the shape of ordered, unranked trees. Although RDBMSs have
originally been designed to manage table-shaped data, we propose their
use as XML and XPath processors. In our setup, the database system employs
a relational XML document encoding, the XPath accelerator, which maps
information about the XML node hierarchy to a table, thus making it possible
to evaluate XPath expressions on SQL hosts. Conventional RDBMSs, nevertheless,
remain ignorant of many interesting properties of the encoded tree data,
and were thus found to make no or poor use of these properties. This is
why we devised a new join algorithm, staircase join, which incorporates
the tree-specific knowledge required for an efficient SQL-based evaluation
of XPath expressions. In a sense, this demonstration delivers the promise
we have made at VLDB 2003: a notion of tree awareness can be injected
into a conventional disk-based RDBMS kernel in terms of staircase join.
The demonstration features a side-by-side comparison of both, an original
and a staircase-join enhanced instance of PostgreSQL. The required changes
to PostgreSQL were local, the achieved effect, however, is significant:
the demonstration proves that this injection of tree awareness turns PostgreSQL
into a high-performance XML processor that closely adheres to the XPath
semantics.
FluXQuery: An
Optimizing XQuery Processor for Streaming XML Data
C. Koch (TU Wien, Austria), S. Scherzinger (University of Passau, Germany),
N. Schweikardt (Humboldt University Berlin, Germany), and B. Stegmaier
(University of Passau, Germany)
We present the FluXQuery
engine, the first optimizing XQuery engine for XML streams. Optimization
in FluXQuery is based on a new internal query language called FluX which
slightly extends XQuery by a construct for event-based query processing.
By allowing for the conscious use of main memory buffers, it supports
reasoning over the employment of buffers during query optimization and
evaluation.
DEMO
GROUP 4: WEB AND WEB-SERVICES
COMPASS: A
Concept-based Web Search Engine for HTML, XML, and Deep Web Data
Jens Graupmann, Michael Biwer, Christian Zimmer, Patrick Zimmer, Matthias
Bender, Martin Theobald, and Gerhard Weikum (Max-Planck Institute for
Computer Science, Saarbruecken, Germany)
Today's web search
engines are still following the paradigm of keyword-based search. Although
this is the best choice for large scale search engines in terms of throughput
and scalability, it inherently limits the ability to accomplish more meaningful
query tasks. XML query engines (e.g., based on XQuery or XPath), on the
other hand, have powerful query capabilities; but at the same time their
dedication to XML data with a global schema is their weakness, because
most web information is still stored in diverse formats and does not conform
to common schemas. Typical web formats include static HTML pages or pages
that are generated dynamically from underlying database systems, accessible
only through portal interfaces. We have developed an expressive style
of concept-based and context-aware querying with relevance ranking that
encompasses different, non-schematic data formats and integrates Web Services
as well as Deep Web sources. Coined COMPASS (Context-Oriented Multi-Format
Portal-Aware Search System), our system features this new language that
combines the simplicity of web search engines with the expressiveness
of (simple forms of) XML query languages.
Discovering
and Ranking Semantic Associations over a Large RDF Metabase
Chris Halaschek, Boanerges Aleman-Meza, I. Budak Arpinar, and Amit P.
Sheth (University of Georgia, Athens, USA)
Information retrieval
over semantic metadata has recently received a great amount of interest
in both industry and academia. In particular, discovering complex and
meaningful relationships among this data is becoming an active research
topic. Just as ranking of documents is a critical component of today's
search engines, the ranking of relationships will be essential in tomorrow's
analytics engines. Building upon our recent work on specifying these semantic
relationships, which we refer to as Semantic Associations, we demonstrate
a system where these associations are discovered among a large semantic
metabase represented in RDF. Additionally we employ ranking techniques
to provide users with the most interesting and relevant results.
An Automatic Data Grabber for Large Web Sites
Valter Crescenzi (University of Roma, Italy), Giansalvatore Mecca (University
of Potenza, Italy), Paolo Merialdo , and Paolo Missier (University of
Roma, Italy)
We demonstrate a system
to automatically grab data from data intensive web sites. The system first
infers a model that describes at the intentional level the web site as
a collection of classes; each class represents a set of structurally homogeneous
pages, and it is associated with a small set of representative pages.
Based on the model a library of wrappers, one per class, is then inferred,
with the help an external wrapper generator. The model, together with
the library of wrappers, can thus be used to navigate the site and extract
the data.
WS-CatalogNet:
An Infrastructure for Creating, Peering, and Querying e-Catalog Communities
Karim Baina, Boualem Benatallah, Hye-young Paik (University of New South
Wales, Australia), Farouk Toumani, Christophe Rey (ISIMA, France), Agnieszka
Rutkowska, and Bryan Harianto (University of New South Wales, Australia)
Given that e-catalogs
are often autonomous and heterogeneous, effectively integrating and querying
them is a delicate and time-consuming task. More importantly, the number
of e-catalogs to be integrated and queried may be large and continuously
changing. We present the WS-CatalogNet system: a Web services based information
sharing middleware infrastructure whose aims is to enhance the potential
of e-catalogs by focusing on scalability and flexible aspects of their
sharing and access. WS-CatalogNet builds upon lessons learned in our previous
work on Web information integration in order to provide a peer-to-peer
and semantic-based e-catalogs sharing middleware infrastructure through
which: (i) e-catalogs can be categorized and described using domain ontologies,
(ii) heterogeneous service ontologies can be linked via peer relationships,
(iii) e-catalogs selection caters for flexible matching between user queries
and e-catalogs descriptions.
Trust-Serv:
A Lightweight Trust Negotiation Service
Halvard Skogsrud, Boualem Benatallah (University of New South Wales, Australia),
Fabio Casati (Hewlett-Packard Labs, USA), and Manh Q. Dinh (University
of Technology, Sydney, Australia)
Trust negotiation
is an approach to access control that does not require the provider to
know the requester a priori. Instead, trust is established on-the-fly
in a negotiation. However, specifying and maintaining policies is hard
in existing systems. The reason is usually that policy specification requires
time-consuming and error-prone low-level programming. We present Trust-Serv,
a model-driven trust negotiation system for Web services. Our system addresses
the policy management problem by modeling trust negotiation policies as
extended state machines. Trust-Serv has been implemented as a middleware
that is transparent to the Web services and to the developers of Web services,
simplifying Web service development and management as well as enabling
scalable deployments. In our demo, we will demonstrate policy specification
and management, as well as how trust negotiations are automated using
our system.
DEMO
GROUP 5: QUERY OPTIMIZATION AND DATABASE INTEGRITY
Green Query
Optimization: Taming Query Optimization Overheads through Plan Recycling
Parag Sarda, and Jayant R. Haritsa (Indian Institute of Science, Bangalore,
India)
PLASTIC is a recently-proposed
tool to help query optimizers significantly amortize optimization overheads
through a technique of plan recycling. The tool groups similar queries
into clusters and uses the optimizer-generated plan for the cluster representative
to execute all future queries assigned to the cluster. An earlier demo
had presented a basic prototype implementation of PLASTIC. We have now
significantly extended the scope, usability, and efficiency of PLASTIC,
by incorporating a variety of new features, including an enhanced query
feature vector, variable-sized clustering and a decision-tree-based query
classifier. The demo of the upgraded PLASTIC tool is shown on commercial
database platforms (IBM DB2 and Oracle 9i).
Progressive
Optimization in Action
Vijayshankar Raman, Volker Markl, David Simmen, Guy Lohman, and Hamid
Pirahesh (IBM Almaden Research Center, USA)
Progressive Optimization
(POP) is a technique to make query plans robust, and minimize need for
DBA intervention, by repeatedly re-optimizing a query during runtime if
the cardinalities estimated during optimization prove to be significantly
incorrect. POP works by carefully calculating validity ranges for each
plan operator under which the overall plan can be optimal. POP then instruments
the query plan with checkpoints that validate at runtime that cardinalities
do lie within validity ranges, and re-optimizes the query otherwise. In
this demonstration we showcase POP implemented for a research prototype
version of IBM a mix of real-world and synthetic benchmark databases and
workloads. For selected queries of the workload we display the query plans
with validity ranges as well as the placement of the various kinds of
CHECK operators using the DB2 graphical plan explain tool. We also execute
the queries, showing how and where re-optimization is triggered through
the CHECK operators, the new plan generated upon re-optimization, and
the extent to which previously computed intermediate results are reused.
CORDS: Automatic Generation of Correlation Statistics in DB2
Ihab F. Ilyas (Purdue University, USA), Volker Markl, Peter J. Haas, Paul
G. Brown, and Ashraf Aboulnaga (IBM Almaden Research Center, USA)
When query optimizers
erroneously assume that database columns are statistically independent,
they can underestimate the selectivities of conjunctive predicates by
orders of magnitude. Such underestimation often leads to drastically suboptimal
query execution plans. We demonstrate cords, an efficient and scalable
tool for automatic discovery of correlations and soft functional dependencies
between column pairs. We apply cords to real, synthetic, and TPC-H benchmark
data, and show that cords discovers correlations in an efficient and scalable
manner. The out-put of cords can be visualized graphically, making cords
a useful mining and analysis tool for database administrators. cords ranks
the discovered correlated column pairs and recommends to the optimizer
a set of statistics to collect for the "most important" of the
pairs. Use of these statistics speeds up processing times by orders of
magnitude for a wide range of queries.
CHICAGO: A Test
and Evaluation Environment for Coarse-Grained Optimization
Tobias Kraft and Holger Schwarz (University of Stuttgart, Germany)
Relational OLAP tools
and other database applications generate sequences of SQL statements that
are sent to the database server as result of a single information request
issued by a user. Coarse-Grained Optimization is a practical approach
for the optimization of such statement sequences based on rewrite rules.
In this demonstration we present the CHICAGO test and evaluation environment
that allows to assess the effectiveness of rewrite rules and control strategies.
It includes a lightweight heuristic optimizer that modifies a given statement
sequence using a small and variable set of rewrite rules.
SVT: Schema
Validation Tool for Microsoft SQL-Server
Ernest Teniente, Carles Farre, Toni Urpi, Carlos Beltran, and David Ganan
(University of Catalunya, Spain)
We present SVT, a
tool for validating database schemas in SQL Server. This is done by means
of testing desirable properties that a database schema should satisfy.
To our knowledge, no commercial relational DBMS provides yet a tool able
to perform such kind of validation.
DEMO
GROUP 6: STREAMING DATA AND SPATIAL AND MULTIMEDIA DATABASES
CAPE: Continuous
Query Engine with Heterogeneous-Grained Adaptivity
Elke A. Rundensteiner, Luping Ding, Timothy Sutherland, Yali Zhu, Brad
Pielech, and Nishant Mehta
In the demonstration,
we will present our continuous query engine named CAPE which is designed
to function effectively in highly dynamic stream environments. The core
foundation of CAPE is an optimization framework with heterogeneous-grained
adaptivity. In particular, the following aspects of the CAPE system will
be shown: (1) highly reactive and communicative query operators, (2) adaptive
operator scheduling, (3) runtime plan reoptimization and migration even
between sub-plans containing stateful operators, and (4) adaptive query
plan distribution across multiple machines. In summary, CAPE is shown
to be truly reactive and adaptive in a rich diversity of stream environments. HiFi: A Unified
Architecture for High Fan-in Systems
Owen Cooper, Anil Edakkunni, Michael J. Franklin (Berkeley, USA), Wei
Hong (Intel Research Berkeley), Shawn R. Jeffery, Sailesh Krishnamurthy,
Fredrick Reiss, Shariq Rizvi, and Eugene Wu (Berkeley, USA)
Advances in data acquisition
and sensor technologies are leading towards the development of "High
Fan-in" architectures: widely distributed systems whose edges consist
of numerous receptors such as sensor networks and RFID readers and whose
interior nodes consist of traditional host computers organized using the
principle of successive aggregation. Such architectures pose significant
new data management challenges. The HiFi system, under development at
UC Berkeley, is aimed at addressing these challenges. We demonstrate an
initial prototype of HiFi that uses data stream query processing to acquire,
filter, and aggregate data from multiple devices including sensor motes,
RFID readers, and low power single-board computer gateways organized as
a High Fan-in system. An Integration
Framework for Sensor Networks and Data Stream Management Systems
Daniel J. Abadi, Wolfgang Lindner, Samuel Madden (MIT, USA), Jorg Schuler
(Tufts University, USA)
This demonstration
shows an integrated query processing environment where users can seamlessly
query both a data stream management system and a sensor network with one
query expression. By integrating the two query processing systems, the
optimization goals of the sensor network (primarily power) and server
network (primarily latency and quality) can be unified into one quality
of service metric. The demo shows various steps of the unified optimization
process for a sample query where the effects of each step that the optimizer
takes can be directly viewed using a quality of service monitor. Our demo
includes sensors deployed in the demo area in a tiny mockup of a factory
application. QStream: Deterministic
Querying of Data Streams
Sven Schmidt, Henrike Berthold and Wolfgang Lehner (Dresden University
of Technology, Germany)
Current developments
in processing data streams are based on the best-effort principle and
therefore not adequate for many application areas. When sensor data is
gathered by interface hardware and is used for triggering data-dependent
actions, the data has to be queried and processed not only in an efficient
but also in a deterministic way. Our streaming system prototype embodies
novel data processing techniques. It is based on an operator component
model and runs on top of a real-time capable environment. This enables
us to provide real Quality-of-Service for data stream queries.
AIDA: an Adaptive
Immersive Data Analyzer
Mehdi Sharifzadeh, Cyrus Shahabi, Bahareh Navai, Farid Parvini, and Albert
A. Rizzo (University of Southern California, USA)
In this demonstration,
we show various querying capabilities of an application called AIDA. AIDA
is developed to help the study of attention disorder in kids. In a different
study [1], we collected several immresive sensory data streams from kids
monitored in an immersive application called the virtual classroom. This
dataset, termed immersidata is used to analyze the behavior of kids in
the virtual classroom environment. AIDA's database stores all the geometry
of the objects in the virtual classroom environment and their spatio-temporal
behavior. In addition, it stores all the immersidata collected from the
kids experimenting with the application. AIDA's graphical user interface
then supports various spatio-temporal queries on these datasets. Moreover,
AIDA replays the immersidata streams as if they are collected in real-time
and on which supports various continuous queries. This demonstration is
a proof-of-concept prototype of a typical design and development of a
domain-specific query and analysis application on the users' interaction
data with immersive environments. BilVideo Video
Database Management System
Ozgur Ulusoy, Ugur Gudukbay, Mehmet Emin Donderler, Ediz Saykol, and Cemil
Alper (Bilkent University, Turkey)
A prototype video
database management system, which we call BilVideo, is presented. BilVideo
provides an integrated support for queries on spatio-temporal, semantic
and low-level features (color, shape, and texture) on video data. BilVideo
does not target a specific application, and thus, it can be used to support
any application with video data. An example application, news archives
search system, is presented with some sample queries. PLACE: A Query
Processor for Handling Real-time Spatio-temporal Data Streams
Mohamed F. Mokbel, Xiaopeng Xiong, Walid G. Aref, Susanne E. Hambrusch,
Sunil Prabhakar, Moustafa A. Hammad (Purdue University, USA)
The emergence of location-aware
services calls for new real-time spatio-temporal query processing algorithms
that deal with large numbers of mobile objects and queries. In this demo,
we present PLACE (Pervasive Location-Aware Computing Environments); a
scalable location-aware database server developed at Purdue University.
The PLACE server addresses scalability by adopting an incremental evaluation
mechanism for answering concurrently executing continuous spatiotemporal
queries. The PLACE server supports a wide variety of stationery and moving
continuous spatio-temporal queries through a set of pipelined spatio-temporal
operators. The large numbers of moving objects generate real-time spatio-temporal
data streams.
|
