[Cache from http://www.cis.upenn.edu/~wfan/PODS2001/proceedings.html; please use this canonical URL/source if possible.]


Proceedings of the
Twentieth
ACM SIGMOD-SIGACT-SIGART
Symposium on
Principles of Database Systems


PODS 2001
Santa Barbara, California
May 21 -- 23, 2001
Special Interest Group for the Management of Data
(SIGMOD)
Special Interest Group for Algorithms and Computation Theory
(SIGACT)
Special Interest Group for Artificial Intelligence
(SIGART)





Foreword

This volume contains the proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on the Principles of Database Systems (PODS), held at Santa Barbara, California on May 21-23, 2001 in conjunction with the 2001 ACM SIGMOD Conference on Management of Data. It contains an invited paper by Victor Vianu, tutorials by Martin Grohe and Tom Leighton, and 26 contributions that were selected by the program committee for presentation at the symposium.

The contributed papers were selected from 99 submissions. Most of the papers are ``extended abstracts'' and are preliminary reports on work in progress. While they have been read by the program committee, they have not been formally refereed. It is expected that much of the research described in these papers will be published in detail in the appropriate journals.

The program committee selected ``Optimal Aggregation Algorithms for Middleware'' by Ronald Fagin, Amnon Lotem and Moni Naor for the PODS 2001 Best Paper Award and ``Relaxed Multi-Way Trees with Group Updates'' by Kim S. Larsen for the Best Newcomer Award. Congratulations to the authors of these papers.

The Program Committee and the PODS Executive Committee thank all those who submitted abstracts for consideration. They thank their colleagues, listed separately, who helped in the reviewing process; and they thank the sponsoring organizations. The program committee did not meet in person, but carried out extensive discussions through the use of the ConfMan software (http://confman.unik.no/~confman), which was ably modified and maintained by Shih-Chang Chen.

As program chair I would like to thank the members of the Program Committee for the hard work they put in both in writing reviews and for their participation in the extensive discussions. I thank Wenfei Fan for his work in preparing the proceedings and in other organizational matters, and I thank Wang-Chiew Tan for her help with the proceedings. Finally, I would like to extend special thanks to Rick Hull, who shouldered a significant part of the program chair's duties during the review process.


Peter Buneman
Program Committee Chair



Conference Organization

Sponsors:
ACM SIGMOD, SIGACT, and SIGART

Executive Committee:
Serge Abiteboul (INRIA)
Peter Buneman (University of Pennsylvania)
Georg Gottlob (TU Wien)
Alberto Mendelzon (University of Toronto)
Christos H. Papadimitriou (UC Berkeley)
Victor Vianu (UC San Diego)

General Chair:
Serge Abiteboul (INRIA)
Program Chair:
Peter Buneman (University of Pennsylvania)
Program Committee:
Foto Afrati (National Technical University of Athens)
Gustavo Alonso (ETH Zurich)
Paolo Atzeni (Università Roma Tre)
Luca Cardelli (Microsoft Research)
Amr El Abbadi (University of California, Santa Barbara)
Michael Franklin (University of California, Berkeley)
Gosta Grahne (Concordia University)
Richard Hull (Bell Laboratories)
Neil Immerman (University of Massachusetts, Amherst)
Phokion G. Kolaitis (University of California, Santa Cruz)
Heikki Mannila (Nokia Research Center & Helsinki University of Technology)
Rajeev Motwani (Stanford University)
Frank Neven (Limburgs Universitair Centrum)
Luc Segoufin (INRIA)
Jianwen Su (University of California, Santa Barbara)
Jennifer Widom (Stanford University)

Proceedings Chair:
Wenfei Fan (Bell Labs & Temple University)


External Referees

Ashraf Aboulnaga Yannis Manolopoulos
Walid Aref Paolo Merialdo
Phillip B. Gibbons Tim Merret
Shivnath Babu Dimitris Metaxas
Elena Baralis Ioannis Milis
Andre Bergholz Max Mintz
Elisa Bertino Jeff Naughton
Philip Bohannon Otto Nurmi
Luca Cabibbo Matti Nykanen
Sirish Chandrasekaran Kevin O'Gorman
Rada Chirkova Banu Ozden
Junghoo Cho Lin Qiao
HaeDon Chon Davood Rafiei
Paolo Ciaccia Sriram Raghavan
Yingwei Cui Mirek Riedewald
Victor Dalmau Philippe Rigaux
Susan Davidson Yehoshua Sagiv
Stefan Decker Arnaud Sahuguet
Ron Fagin Mehul Shah
Hakan Ferhatosmanoglu Eljas Soisalon-Soininen
Michael Fredman Daniel Stamate
Minos Garofalakis Ching Suen
Manolis Gergatsoulis ChengYu Sun
Phil Gibbons Keishi Tajima
Martin Grohe Wang-Chiew Tan
Stephane Grumbach Riccardo Torlone
Dimitrios Gunopulos Jan Van den Bussche
Abhishek Gupta Victor Vianu
Taher Haveliwala Philip Wadler
Sushil Jajodia Scott Weinstein
Izambo Karali Derick Wood
Jon Kleinberg Yi-Leh Wu
Nick Koudas Haiyan Xu
Gabi Kuper Moshe Y. Vardi
Chen Li Jun Yang
Leonid Libkin Fang Yu
Joeseph M. Hellerstein Shlomo Zilberstein
Gurmeet Manku


Copyright Notice

The following notice applies to each paper in this collection.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that all copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists requires prior specific permission and/or a fee. PODS 2001, Santa Barbara, California . Copyright ACM 2001.



Contents


Invited Talk


Research Session 1: Querying Web Data


Research Session 2: Queries / Optimization


Invited Tutorial 1


Research Session 3: Award Talks


Research Session 4: XML


Research Session 5: Partial Information


Research Session 6: Expressiveness / Complexity


Research Session 7: Aggregates


Invited Tutorial 2


Research Session 8: Data Mining


Research Session 9: Indexing / Transactions