Database Theory - ICDT 2005

1. Front Matter

   PDF

2. Invited Papers

   1. Model Checking for Database Theoreticians

      • Moshe Y. Vardi

      Pages 1-16

   2. The Design Space of Type Checkers for XML Transformation Languages

      • Anders Møller, Michael I. Schwartzbach

      Pages 17-36

   3. Semantics of Data Streams and Operators

      • David Maier, Jin Li, Peter Tucker, Kristin Tufte, Vassilis Papadimos

      Pages 37-52

3. Regular Papers

   1. Conjunctive Query Evaluation by Search Tree Revisited

      • Albert Atserias

      Pages 53-67

   2. Which XML Schemas Admit 1-Pass Preorder Typing?

      • Wim Martens, Frank Neven, Thomas Schwentick

      Pages 68-82

   3. The Pipelined Set Cover Problem

      • Kamesh Munagala, Shivnath Babu, Rajeev Motwani, Jennifer Widom

      Pages 83-98

4. Session: Query Languages and Types

   1. Well-Definedness and Semantic Type-Checking in the Nested Relational Calculus and XQuery

      • Jan Van den Bussche, Dirk Van Gucht, Stijn Vansummeren

      Pages 99-113

   2. First Order Paths in Ordered Trees

      • Maarten Marx

      Pages 114-128

   3. An Abstract Framework for Generating Maximal Answers to Queries

      • Sara Cohen, Yehoshua Sagiv

      Pages 129-143

5. Session: Multi-dimensional Data Processing

   1. Optimal Distributed Declustering Using Replication

      • Keith B. Frikken

      Pages 144-157

   2. When Is Nearest Neighbors Indexable?

      • Uri Shaft, Raghu Ramakrishnan

      Pages 158-172

   3. Nonmaterialized Motion Information in Transport Networks

      • Hu Cao, Ouri Wolfson

      Pages 173-188

6. Session: Algorithmic Aspects

   1. Algorithms for the Database Layout Problem

      • Gagan Aggarwal, Tomás Feder, Rajeev Motwani, Rina Panigrahy, An Zhu

      Pages 189-203

   2. Approximately Dominating Representatives

      • Vladlen Koltun, Christos H. Papadimitriou

      Pages 204-214

   3. On Horn Axiomatizations for Sequential Data

      • José L. Balcázar, Gemma Casas-Garriga

      Pages 215-229

7. Session: Privacy and Security

   1. Privacy in Database Publishing

      • Alin Deutsch, Yannis Papakonstantinou

      Pages 230-245

   2. Anonymizing Tables

      • Gagan Aggarwal, Tomás Feder, Krishnaram Kenthapadi, Rajeev Motwani, Rina Panigrahy, Dilys Thomas et al.

      Pages 246-258

   3. Authorization Views and Conditional Query Containment

      • Zheng Zhang, Alberto O. Mendelzon

      Pages 259-273

8. Session: Logic and Databases

   1. PTIME Queries Revisited

      • Alan Nash, Jeff Remmel, Victor Vianu

      Pages 274-288

This volume collects the papers presented at the 10th International Conference on Database Theory, ICDT 2005, held during January 5–7, 2005, in Edinburgh, UK. ICDT (http://alpha.luc.ac.be/~lucp1080/icdt/) has now a long tra- tion of international conferences, providing a biennial scienti?c forum for the communication of high-quality and innovative research results on theoretical - pects of all forms of database systems and database technology. The conference usually takes place in Europe, and has been held in Rome (1986), Bruges (1988), Paris (1990), Berlin (1992), Prague (1995), Delphi (1997), Jerusalem (1999), London (2001), and Siena (2003) so far. ICDT has merged with the Sym- sium on Mathematical Fundamentals of Database Systems (MFDBS), initiated in Dresden in 1987, and continued in Visegrad in 1989 and Rostock in 1991. ICDT had a two-stage submission process. First, 103 abstracts were subm- ted, which were followed a week later by 84 paper submissions. From these 84 submissions, the ICDT Program Committee selected 24 papers for presentation at the conference. Most of these papers were “extended abstracts” and preli- nary reports on work in progress. It is anticipated that most of these papers will appear in a more polished form in scienti?c journals.

• DOM
• Extensible Markup Language (XML)
• XML
• algorithms
• data engineering
• data integration
• database design
• database logic
• database queries
• formal methods
• information systems
• logic
• query rewriting
• security
• semantics

• Institut für Informationssysteme, Technische Universität Wien, Vienna, Austria

  Thomas Eiter

• School of Informatics, University of Edinburgh,  

  Leonid Libkin

Policies and ethics