We will also describe a novel index structure (Spindex) and associated algorithms suitable for implementing FIDS, and we will survey a commercial system based on Spindex.

• Location: BA1180
• Time: 11:00AM

In order to achieve this, we will briefly introduce parameterized complexity, define a notion of tree likeness also known as tree width and then prove that the more the query and|or the database looks like a tree, the most efficient the evaluation will be.

• Location: PT378
• Time: 12:00AM

• Location: PT378
• Time: 12:00AM

This talk discusses some of the developments related to the Web from the viewpoint of database theory. As will be argued, the Web scenario requires revisiting some of the basic assumptions of the area. We discuss some of the challenges and contributions of database theory to the formal foundations of the Web, with special focus on XML. In particular, we exhibit a powerful (and elegant) connection between XML Schemas and tree automata, and between XML queries and tree transducers, and show how this can be used in the static analysis of XML queries in the context of data exchange and data integration.

• Location: BA1180
• Time: 11:00AM

• Location: BA5256
• Time: 11:00AM

We define a very strong notion of optimality, which we call "instance optimality". An algorithm is instance optimal if, up to a constant factor, its performance is as good as every other (correct) algorithm, on every instance (in our case, on every database). We give an elegant and remarkably simple algorithm that is instance optimal for our problem (under some natural restrictions).

This research, which is joint with Amnon Lotem and Moni Naor, won the Best Paper Award for the 2001 ACM Symposium on Principles on Database Systems. The talk will be completely self-contained.

He has published around 100 papers, and has coauthored a book on "Reasoning about Knowledge". He is a Fellow of the Institute of Electrical and Electronic Engineers, and a Fellow of the Association for Computing Machinery. He was named Docteur Honoris Causa by the University of Paris.

• Location: BA1180
• Time: 11:00AM

• Location: BA1180
• Time: 11:00AM

In this paper we propose a simple semantics for reification and anonymous resources in F-logic --- a frame-based logic language, which is a popular formalism for representing and reasoning about semantic information on the Web.

The choice of F-logic (over RDF) as a basis for our semantics is motivated by the fact that F-logic provides a comprehensive solution for the problem of integrating frames, rules, and deduction, and it has been shown to provide an effective inference service for RDF.

Dr. Kifer's interests include database systems, knowledge representation, and Web information systems. He has published two text books and numerous articles in these areas. In 1999 and 2002 he was a recipient of the ACM-SIGMOD "Test of Time" awards for his works on object-oriented database languages.

• Location: BA5256
• Time: 2:00PM

XML is becoming the predominant data exchange format in a variety of application domains (supply-chain, scientific data processing, telecommunication infrastructure, etc.). By relying on relational engines for storage purposes, XML developers can benefit from a complete set of data management services (including concurrency control, crash recovery, and scalability) and from the highly optimized relational query processors. However, due to the mismatch between the XML and the relational models and the many different ways to map an XML document into relations, it is very hard to tune a relational engine and ensure that XML queries will be evaluated efficiently.

LegoDB is a cost-based XML storage mapping engine that automatically explores a space of possible XML-to-relational mappings and selects the best mapping for a given application. LegoDB leverages current XML and relational technologies: 1) it models the target application with an XML Schema, XML data statistics, and an XQuery workload; 2) the space of configurations is generated through XML-Schema rewritings; and 3) the best among the derived configurations is selected using cost estimates obtained through a standard relational optimizer. In this talk, I will give an overview of the LegoDB storage engine and present experimental results that demonstrate the effectiveness of this approach. I will also discuss recent work on two important facets of the LegoDB system: building statistical summaries of XML documents; and new efficient algorithms for searching the space of XML-to-relational mappings.

• Location: BA5256
• Time: 11:00AM

Content Based Image Retrieval (CBIR) is a challenging task. Current research works attempt to obtain and use the semantics of image to perform better retrieval. Towards this goal, segmentation of an image into regions has been used in recent years, since local properties of regions can help matching objects between images and thereby contribute towards a more effective CBIR. Our work improves on a CBIR technique, called SNL, that utilizes the regional properties of the images. In SNL each image is segmented and features including the color, shape, size and spatial position of the obtained regions are extracted. Regions are then compared using the Integrated Region Matching (IRM) distance measure, which is not a metric, which prevents the use of metric access structures or filtering techniques based on the triangle inequality. We overcome this issue, by using MiCRoM, a true metric distance to compare segmented images. This resulting approach, called SNL*, can be used in conjunction with a filtering technique to reduce substantially the number of images compared. Albeit metric-based, SNL* is computationally expensive. We address this drawback, in the SNL+ approach, where we replace the expensive metric distance in SNL* by the inexpensive original (non-metric) IRM distance. We found that one can still make use of the same filtering technique, at the expense of little loss in retrieval effectiveness. Thus, the main contribution of this work is SNL+, a very effective and highly efficient region-based image retrieval technique.

• Location: BA5256
• Time: 11:00AM

Estimating the result size of complex queries that involve selection on multiple attributes and the join of several relations is a difficult but fundamental task in database query processing. It arises in cost-based query optimization, query profiling, and approximate query answering. In this work, we show how probabilistic graphical models can be effectively used for this task as an accurate and compact approximation of the joint frequency distribution of multiple attributes across multiple relations. Statistical Relational Models (SRMs) are a recent development that extends graphical statistical models such as Bayesian Networks to relational domains. They represent the statistical dependencies between attributes within a table, and between attributes across foreign-key joins. We provide an efficient algorithm for constructing an SRM from a database, and show how an SRM can be used to compute selectivity estimates for a broad class of queries. One of the major contributions of this work is a unified framework for the estimation of queries involving both select and foreign-key join operations. Furthermore, our approach is not limited to answering a small set of predetermined queries; a single model can be used to effectively estimate the sizes of a wide collection of potential queries across multiple tables. We present results for our approach on several real-world databases. For both single-table multi-attribute queries and a general class of select-join queries, our approach produces more accurate estimates than standard approaches to selectivity estimation, using comparable space and time.

• Location: BA5256
• Time: 11:00AM