Session 2: Machine Models and Data Structures

Invited Tutorial 1: Machine Models and Lower Bounds for Query Processing  (Page 41)
N. Schweikardt (Humboldt-Universität zu Berlin)

Decision Trees for Entity Identification: Approximation Algorithms and Hardness Results  (Page 53)
V. T. Chakaravarthy (IBM India Research Laboratory)
V. Pandit (IBM India Research Laboratory)
S. Roy (IBM India Research Laboratory)
P. Awasthi (IBM India Research Laboratory)
M. Mohania (IBM India Research Laboratory)

Session 3: XML 1

Best Newcomer Award: XML Transformation by Tree-Walking Transducers with Invisible Pebbles  (Page 63)
J. Engelfriet (Leiden University)
H. J. Hoogeboom (Leiden University)
B. Samwel (Leiden University)

The Complexity of Query Containment in Expressive Fragments of XPath 2.0  (Page 73)
B. ten Cate (Universiteit van Amsterdam)
C. Lutz (Dresden University of Technology)

Expressiveness and Complexity of XML Publishing Transducers  (Page 83)
W. Fan (University of Edinburgh & Bell Laboratories)
F. Geerts (University of Edinburgh, Hasselt University & Transnational University of Limburg)
F. Neven (Hasselt University & Transnational University of Limburg)

Session 4: Randomization

Maintaining Bernoulli Samples over Evolving Multisets  (Page 93)
R. Gemulla (Technische Universitat Dresden)
W. Lehner (Technische Universitat Dresden)
P. J. Haas (IBM Almaden Research Center)

Finding Near Neighbors Through Cluster Pruning  (Page 103)
F. Chierichetti (University of Rome "La Sapienza")
A. Panconesi (University of Rome "La Sapienza")
P. Raghavan (Yahoo! Research)
M. Sozio (University of Rome "La Sapienza")
A. Tiberi (University of Rome "La Sapienza")
E. Upfal (Brown University)

Session 5: Data Exchange and Schema Mappings

CWA-Solutions for Data Exchange Settings with Target Dependencies  (Page 113)
A. Hernich (Humboldt-Universität)
N. Schweikardt (Humboldt-Universität)

Quasi-inverses of Schema Mappings  (Page 123)
R. Fagin (IBM Almaden Research Center)
P. G. Kolaitis (IBM Almaden Research Center)
L. Popa (IBM Almaden Research Center)
W.-C. Tan (University of California at Santa Cruz)

On Reconciling Data Exchange, Data Integration, and Peer Data Management  (Page 133)
G. De Giacomo (Sapienza Università di Roma)
D. Lembo (Sapienza Università di Roma)
M. Lenzerini (Sapienza Università di Roma)
R. Rosati (Sapienza Università di Roma)

Session 6: Types and Schemas

Invited Tutorial 2: A Crash Course on Database Queries  (Page 143)
J. Van den Bussche (Hasselt University)
D. Van Gucht (Indiana University)
S. Vansummeren (Hasselt University)

The Complexity of Reasoning about Pattern-based XML Schemas  (Page 155)
G. Kasneci (Max-Planck-Institut für Informatik)
T. Schwentick (Universitat Dortmund)

Session 7: Query Languages

Monadic Datalog over Finite Structures with Bounded Treewidth  (Page 165)
G. Gottlob (Oxford University)
R. Pichler (Technische Universitat Wien)
F. Wei (Technische Universitat Wien)

Index-Based Multidimensional Array Queries: Safety and Equivalence  (Page 175)
R. Machlin 

Non-Linear Prefixes in Query Languages  (Page 185)
A. Badia (University of Louisville)
S. Vansummeren (Hasselt University & Transnational University of Limburg)

Session 8: XML 2

Reasoning about XML Update Constraints  (Page 195)
B. Cautis (INRIA Futurs & University Paris Sud)
S. Abiteboul (INRIA Futurs & University Paris Sud)
T. Milo (Tel Aviv University)

Polynomial Time Fragments of XPath with Variables  (Page 205)
E. Filiot (INRIA Futurs)
J. Niehren (INRIA Futurs)
J.-M. Talbot (University of Provence)
S. Tison (University of Lille)

Session 9: Data Streams

Optimization of Continuous Queries with Shared Expensive Filters  (Page 215)
K. Munagala (Duke University)
U. Srivastava (Yahoo! Research)
J. Widom (Stanford University)

Variance Estimation over Sliding Windows  (Page 225)
L. Zhang (Iowa State University)
Y. Guan (Iowa State University)

Session 10: Sequences, Streams, Events

Marrying Words and Trees  (Page 233)
R. Alur (University of Pennsylvania)

Estimating Statistical Aggregates on Probabilistic Data Streams  (Page 243)
T. S. Jayram (IBM Almaden Research Center)
A. McGregor (University of California at San Diego)
S. Muthukrishan (Google Research)
E. Vee (Yahoo! Research)

Sketching Unaggregated Data Streams for Subpopulation-size Queries  (Page 253)
E. Cohen (AT&T Laboratories-Research)
N. Duffield (AT&T Laboratories-Research)
H. J. Kaplan (Tel Aviv University)
C. Lund (AT&T Laboratories-Research)
M. Thorup (AT&T Laboratories-Research)

What is "Next" in Event Processing?  (Page 263)
W. White (Cornell University)
M. Riedewald (Cornell University)
J. Gehrke (Cornell University)
A. Demers (Cornell University)

Session 11: Privacy, Probabilistic Databases

Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release  (Page 273)
B. Barak (Princeton University)
K. Chaudhuri (University of California at Berkeley)
C. Dwork (Microsoft Research, SVC)
S. Kale (Princeton University)
F. McSherry (Microsoft Research, SVC)
K. Talwar (Microsoft Research, SVC)

On the Complexity of Managing Probabilistic XML Data  (Page 283)
P. Senellart (INRIA Futurs & Université Paris Sud)
S. Abiteboul (INRIA Futurs & Université Paris Sud)

The Dichotomy of Conjunctive Queries on Probabilistic Structures  (Page 293)
N. Dalvi (University of Washington)
D. Suciu (University of Washington)

Maximally Joining Probabilistic Data  (Page 303)
B. Kimelfeld (The Hebrew University of Jerusalem)
Y. Sagiv (The Hebrew University of Jerusalem)