[Please remove <h1>]
Fall 2003
Note: Events of interest to the
Database Research Group are posted to the uw.cs.database
newsgroup and are mailed to the dbgroup mailing lists: db-faculty
(for DB group faculty), db-grads (for DB group graduate students),
and db-friends (for DB group alumni, visitors, and friends). If
you wish to subscribe to one of these lists, send mail to
majordomo@db
with "subscribe <list>" in the message body, where
<list> is the list you wish to subscribe to. For example,
use "subscribe db-friends" to subscribe to the db-friends list. To
unsubscribe, send "unsubscribe <list>" to the same address.
- DB group
meetings
- The DB group meets most Friday afternoons at 2pm, usually in DC1331.
See the list of current events for
times and locations of upcoming meetings. Each meeting lasts
for an hour and features an informal presentation by one of the
members of the group. Everyone is welcome to attend. These talks are
intended to raise questions and to stimulate discussion rather than
being polished presentations of research results. Speakers are determined
using a rotating speaker list, which can be found on the DB group meeting page
- DB seminar
series
- The DB seminar series features visiting speakers. These seminars are
more-or-less monthly, and are usually scheduled on Monday
mornings at 11am. See the list of current
events for times and locations of upcoming seminars. The
full schedule can be found on the DB seminar
series page.
Recent and Upcoming Events
DB meeting
: |
Friday, September
19th, 2:00 pm, DC1331 |
Speaker : |
Catalin Visinescu
|
Topic: |
Incremental Data Distribution on Internet-Based
Distributed Systems: A Spring System Approach
|
Abstract: |
Efficient data distribution
is critical to enable cost-effective performance and high availability of
data for applications or services. Many replication and allocation strategies
were proposed for data distribution in traditional distributed DBMS, but these
do not scale to the Internet environment. In this thesis we propose an incremental
and dynamic method for replicating and reallocating fragments of database
relations in a highly scalable manner. Our algorithm can execute data redistribution
without requiring prior knowledge of the global environment, does not require
redistribution from scratch when the environment changes, considers the relationship
between relations (fragments), and reacts dynamically to changing access
patterns. The algorithm simulates a ``spring system'' among the fragment
and query objects, where correlations (constraints) between objects
play the role of springs. In a real spring system, the springs pull
the objects in such a way as to approach a stable equilibrium state; similarly,
the constraints cause the fragments and query objects to be relocated until
a stable equilibrium is reached. We show that the locations of the
objects at equilibrium correspond to the optimal arrangement for efficient
allocation.
|
DB meeting
: |
Friday, September 26th, 2:00 pm, MC5136 |
Speaker : |
David Toman
|
Topic: |
The relationship between "data expiration"
and "streaming queries". |
DB meeting
: |
Friday, October
3rd, 2:00 pm, DC1331 |
Speaker : |
David DeHaan
|
Topic: |
Synopsis Structures for Semi-Structured
and XML Data |
Abstract: |
Cardinality estimation for intermediate results of queries is an
important pre-requisite for performing cost-based query optimization in
a database system. In most modern relational database systems, cardinality
estimation uses using a variety of statistics, usually including succinct
histogram-based approximations of the value distributions of relevant columns.
With the emergence of semi-structured and XML databases, cardinality estimation
is compounded by variations and correlations not only in value distributions,
but also in the structuring of the data; thus, new synopsis techniques are
required that summarize both structure and value information.
In this talk I will present a critical review of a variety of strategies
that have been proposed for estimating the cardinality of path queries within
graph-structured or tree-structured databases. The structures discussed
will include those based upon Markov assumptions (Markov tables, XPathLearner),
local graph stability (Path trees, XSketch), set hashing (Correlated Subpath
Trees), document geometry (Position Histograms), and integrating histograms
with schema typing (StatiX).
|
DB meeting
: |
Friday, October
17th, 2:00 pm, DC1331 MC5136 |
Speaker: |
Bin Yao
|
Topic: |
A Survey of Indexing Techniques for Native XML DBMSs
|
Abstract: |
Since XML started
becoming a dominant standard for representing data and
documents on the World Wide Web, it is desirable to have a database
management system (DBMS) to efficiently manage XML documents. Among several
existing technologies, a native XML DBMS is a promising approach to address
this issue. The talk will cover indexing techniques that have
been using or can be adapted for native XML DBMSs to facilitate efficient
querying and, possibly, updating.
|
DB meeting
: |
Friday, October
24th, 2:00 pm, DC1331 |
Speaker: |
Heng Yu
|
Topic: |
Investigations in Tree Locking for Compiled Database Applications
|
Abstract:
|
We report on initial experiments in tree locking schemes for
compiled database applications. Such applications have a
repository style of architecture in which a collection of software
modules or subsystems operate on a common database in terms of a
predefined set of transaction types, and are very often at the
core of embedded systems. Since the tree locking protocol is
deadlock free, it becomes possible to decouple recovery mechanisms
from concurrency control, a property that we believe is critical
to the successful deployment of database technology to this new
application area. Our experiments show that the performance of
tree locking can compete with two phase locking for cases such as
the above in which a great deal can be known at the time of system
generation about workloads.
|
DB meeting
: |
Friday, October
31st, 2:00 pm, DC1331 |
Speaker : |
Ken Salem
|
Topic: |
Tomorrow's database management systems
|
Abstract:
|
I will sketch a picture of a database management
system of the not-so-distant future and, in so doing,
identify a couple of trends that I think are important.
My focus will be on systems issues: management, configuration,
and performance.
|
DB meeting
: |
Friday, November
7th, 2:00 pm, DC1331 |
Speaker: |
Dan Farrar
|
Topic: |
An overview of the view selection problem
|
Abstract: |
The view selection problem is the problem of deciding what views to
materialize for a given database, given a workload of queries to optimize
and a maximum size constraint. My talk will be based on a paper from PODS
2002 by Chirkova that describes the view selection problem and determines a
lower bound on the number of optimal views for common instances of the
problem. I will also discuss the similarity between the view selection
problem and the index selection problem, both in terms of research
approaches and possible implementations.
|
DB meeting
: |
Friday, November
14th, 2:00 pm, DC1331 |
Speaker : |
Frank Tompa
|
Topic: |
Another tree encoding for XML |
Abstract: |
At the XSYM Symposium in September,
there was an interesting paper entitled
Tree Signatures for XML Querying and Navigation
presented by Pavel Zezula, Giuseppe Amato, Franca Debole, and Fausto Rabitti.
In their basic encoding, a tree is represented by an array of nodes in prefix order,
where for each node they store the tag name and the postfix order for that node.
With this encoding, they show how to check whether one tree in weakly included
in another (i.e., children in the pattern tree can map to descendents in
the target tree).
They also present an extended encoding which additionally has pointers to the
following sibling and to the parent nodes.
With this larger encoding, they show how to support XPath queries and navigation.
I will present an alternative encoding that is based on their basic one,
but stores the number of descendents instead of the postfix number for each node.
|
DB meeting
: |
Friday, November
21st, 2:00 pm, DC1331 |
Topic:: |
coffee break (no talk today) |
DB meeting
: |
Friday, November
28th, 2:00 pm, DC1331 |
Speaker : |
Yuhui Wen
|
Topic: |
Incremental Similarity Search |
Abstract:
|
The goal of incremental similarity search is to return the neighbours of a
query object in increasing order of distance from that object. I will talk
about some previous work on this topic, incremental-LAESA from Hjaltason and
Samet, and a new proposal based on it. Comparing to the incremental LAESA,
the new approach is aiming for large scale data set.
|
DB meeting
: |
Friday, December
5th, 2:00pm
11:00 am, DC1331 |
Speaker : |
Sam Lightstone
|
Topic: |
The Multi-dimensional Clustering Advisor |
Abstract:
|
This talk will present a model for automating the design of
multi-dimensional clustering keys (clustering design) for a
multi-dimensional relational database that uses a cell/block storage
structure. The talk will include an introduction to autonomic computing,
motivation for automating the physical design problem for multi-dimensional
clustering, a description of the proposed model, experimental results, and
future research.
|
DB meeting
: |
Friday, December
12th, 2:00 pm, DC1331 |
Speaker : |
Hossein S. Attar
|
Topic: |
Alternative Architectures and Protocols for Providing Strong
Consistency in Dynamic Web Caching
|
Abstract:
|
I will talk about alternative architectures for Web applications that
need strong consistency (i.e., cannot tolerate serving of stale data).
We have compared the performance of three architectures, including one
that uses a database cache, which we have designed and implemented.
The talk also includes an overview of previous work in caching
dynamic Web applications.
|
This page is maintained by
Ken
Salem.