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

PODS 2000
Dallas, Texas
May 15 -- 17, 2000

Foreword

This volume contains an invited paper, two invited tutorials and 26 contributed papers that were selected for presentation at the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), which was held May 15--17, 2000 in Dallas, USA in conjunction with the 2000 ACM SIGMOD International Conference on Management of Data.

The contributed papers were selected by the Program Committee out of 119 submissions. Most of these papers present preliminary reports of continuing research; they have been read by the Program Committee but not formally refereed. It is anticipated that most of them will appear in a more polished form in scientific journals.

For the PODS'2000 Best Paper Award the Program Committee selected the paper ``Auditing Boolean Attributes'' by Jon Kleinberg, Christos Papadimitriou and Prabhakar Raghavan. For the PODS'2000 Best Newcomer Paper Award we selected the paper ``Verification of Relational Transducers for Electronic Commerce'' by Marc Spielmann. My warmest congratulations to the authors.

The Program Committee would like to thank all those who submitted extended abstracts for consideration, those colleagues who helped in the evaluation (listed separately), and the sponsoring organizations for their assistance and support. I would like to thank the members of the Program Committee for their hard and conscientious work. The Program Committee meeting was held in electronic form. The software used was ConfMan, an excellent PC management package designed and implemented by Pal Halvorsen, Ketil Lund and Thomas Preuss (see http://confman.unik.no). We thank the authors of ConfMan for making the system available to us. We also thank the Austrian Science Fund FWF (Project N Z29-INF) for financially supporting essential PC tasks. Finally, special thanks go to the PC Assistant Katrin Seyr and to the Proceedings Chair Bertram Ludäscher.

Georg Gottlob, Program Committee Chair

Conference Organization

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 '00 Dallas Texas. Copyright ACM 2000.

Session 1: PODS Invited Talk

• The Web as a Graph. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tomkins (IBM Almaden), and Eli Upfal (Brown University) [.ps.gz] [.pdf]

Session 2: XML Technology

• Typechecking for XML Transformers. Tova Milo (Tel Aviv University), Dan Suciu (AT&T Labs), and Victor Vianu (UC San Diego) [.ps.gz] [.pdf]
• Integrity Constraints for XML. Wenfei Fan (Temple University), and Jérôme Siméon (Bell Labs) [.ps.gz] [.pdf]
• DTD Inference for Views of XML Data. Yannis Papakonstantinou (UC San Diego), and Victor Vianu (UC San Diego) [.ps.gz] [.pdf]

Session 3: Views / Query Containment

• On the Content of Materialized Aggregate Views. Stéphane Grumbach (INRIA), and Leonardo Tininini (CNR-IASI, Rome) [.ps.gz] [.pdf]
• View-Based Query Processing for Regular Path Queries with Inverse. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini (Università di Roma ``La Sapienza''), and Moshe Y. Vardi (Rice University) [.ps.gz] [.pdf]
• Query Containment for Data Integration Systems. Todd Millstein, Alon Levy (University of Washington), and Marc Friedman (Viathan Corporation) [.ps.gz] [.pdf]

Session 4: PODS Invited Tutorial

• Constraint Satisfaction in Database Theory. Moshe Vardi (Rice University) [.ps.gz] [.pdf]

Session 5: Award Talks

• Auditing Boolean Attributes. Jon Kleinberg (Cornell University), Christos Papadimitriou (UC Berkeley), and Prabhakar Raghavan (IBM Almaden) [.ps.gz] [.pdf]
• Verification of Relational Transducers for Electronic Commerce. Marc Spielmann (RWTH Aachen) [.ps.gz] [.pdf]

Session 6: Spatial and Constraint Databases

• Reachability and Connectivity Queries in Constraint Databases. Michael Benedikt (Bell Labs), Martin Grohe (Universität Freiburg), Leonid Libkin (Bell Labs), and Luc Segoufin (INRIA) [.ps.gz] [.pdf]
• Fixed-Point Query Languages for Linear Constraint Databases. Stephan Kreutzer (RWTH Aachen) [.ps.gz] [.pdf]
• Linear Approximation of Planar Spatial Databases Using Transitive-Closure Logic. Floris Geerts, and Bart Kuijpers (Limburgs Universitair Centrum) [.ps.gz] [.pdf]

Session 7: Semistructured Data

• Computational Aspects of Resilient Data Extraction from Semistructured Sources. Hasan Davulcu, Guizhen Yang, Michael Kifer, and I.V. Ramakrishnan (SUNY at Stony Brook) [.ps.gz] [.pdf]
• Expressive and Efficient Pattern Languages for Tree-Structured Data. Frank Neven (Limburgs Universitair Centrum), and Thomas Schwentick (Universität Mainz) [.ps.gz] [.pdf]
• Expressive Power and Data Complexity of Query Languages for Trees and Lists. Evgeny Dantsin (University of Manchester), and Andrei Voronkov (University of Manchester) [.ps.gz] [.pdf]

Session 8: Indexing / Transactions

• Indexing the Edges -- A Simple and yet Efficient Approach to High-Dimensional Indexing. Beng Chin Ooi, Kian-Lee Tan, Cui Yu, and Stéphane Bressan (National University of Singapore) [.ps.gz] [.pdf]
• Indexing Moving Points. Pankaj K. Agarwal (Duke University), Lars Arge (Duke University), and Jeff Erickson (University of Illinois) [.ps.gz] [.pdf]
• On Herbrand Semantics and Conflict Serializability of Read-Write Transactions. Jens Lechtenbörger, and Gottfried Vossen (Universität Münster) [.ps.gz] [.pdf]

Session 9: Invited Tutorial

• Entrepreneurship for Information Systems Researchers. Ashish Gupta (Amazon.com) [.ps.gz] [.pdf]

Session 10: Range Queries / Selectivity Estimation

• Optimal Histograms for Hierarchical Range Queries. Nick Koudas, S. Muthukrishnan, and Divesh Srivastava (AT&T Labs) [.ps.gz] [.pdf]
• (Almost) Optimal Parallel Block Access for Range Queries. Mikhail J. Atallah (CERIAS and Purdue University), Sunil Prabhakar (Purdue University) [.pdf]
• Selectivity Estimation for Boolean Queries. Zhiyuan Chen (Cornell University), Flip Korn (AT&T Labs), Nick Koudas (AT&T Labs), and S. Muthukrishnan (AT&T Labs) [.ps.gz] [.pdf]

Session 11: Data Mining / Information Dependencies

• Traversing Itemset Lattices with Statistical Metric Pruning. Shinichi Morishita (University of Tokyo), and Jun Sese (University of Tokyo) [.pdf]
• Computational Properties of Metaquerying Problems. Fabrizio Angiulli (Università della Calabria), Rachel Ben-Eliyahu-Zohary (Ben-Gurion University), Giovambattista Ianni (Università della Calabria), and Luigi Palopoli (Università della Calabria) [.ps.gz] [.pdf]
• Information Dependencies. Mehmet M. Dalkilic (Indiana University), and Edward L. Robertson (Indiana University) [.ps.gz] [.pdf]

Session 12: Sampling

• Uniform Generation in Spatial Constraint Databases and Applications. David Gross (Université Paris-Sud), and Michel De Rougemont (Université Paris II) [.ps.gz] [.pdf]
• Analysis and Application of Adaptive Sampling. James F. Lynch (Clarkson University) [.ps.gz] [.pdf]
• Towards Estimation Error Guarantees for Distinct Values. Moses Charikar (Stanford University), Surajit Chaudhuri (Microsoft Research), Rajeev Motwani (Stanford University), and Vivek Narasayya (Microsoft Research) [.ps.gz] [.pdf]