Database Research Group Events

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 Seminar : Monday, September 22nd, 11:00 am, DC1304
Speaker : Divesh Srivastava, AT&T Labs-Research
Title: Phrase Matching in XML

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

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 Seminar : Monday, October 20, 11:00 am, DC1304
Speaker : Louiqa Raschid, University of Maryland
Title: Efficient Exploration of Links and Paths in Life Sciences Data Sources

DB meeting : Friday, October 24th, 2:00 pm, DC1331
Speaker: Heng Yu
Topic: Investigations in Tree Locking for Compiled Database Applications
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
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 Seminar : Wednesday, November 26th, 10:30 am, DC1304
Speaker : Elke Rundensteiner, Worcester Polytechnic Institute
Title: Raindrop: The WPI Stream Query Engine

DB meeting : Friday, November 28th, 2:00 pm, DC1331
Speaker : Yuhui Wen
Topic: Incremental Similarity Search
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
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
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.

DB Seminar : Monday, December 15th, 11:00 am, DC1304
Speaker : Klemens Böhm, Otto-von-Guericke-Universität Magdeburg
Title: Incentives and Sanctions in Peer-to-Peer Information Systems

This page is maintained by  Ken Salem.