28. PODS 2009: Providence, Rhode Island, USA

Opening and invited talk

• Nilesh N. Dalvi, Ravi Kumar, Bo Pang, Raghu Ramakrishnan, Andrew Tomkins, Philip Bohannon, Sathiya Keerthi, Srujana Merugu:
  A web of concepts. 1-12
  

Schema mappings

• Bruno Marnette:
  Generalized schema-mappings: from termination to tractability. 13-22
  
• Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, Wang Chiew Tan:
  Reverse data exchange: coping with nulls. 23-32
  
• Shun'ichi Amano, Leonid Libkin, Filip Murlak:
  XML schema mappings. 33-42
  

Awards

• Catriel Beeri, Phokion G. Kolaitis, Christos H. Papadimitriou:
  The ACM PODS Alberto O. Mendelzon test-of-time-award 2009. 43
  
• Georg Gottlob, Stephanie Tien Lee, Gregory Valiant:
  Size and treewidth bounds for conjunctive queries. 45-54
  
• Pawel Parys:
  XPath evaluation in linear time with polynomial combined complexity. 55-64
  

Invited tutorial 1

• Leonid Libkin:
  The finite model theory toolbox of a database theoretician. 65-76
  

Extended models

• Andrea Calì, Georg Gottlob, Thomas Lukasiewicz:
  A general datalog-based framework for tractable query answering over ontologies. 77-86
  
• Serge Abiteboul, Pierre Bourhis, Bogdan Marinoiu:
  Satisfiability and relevance for queries over active documents. 87-96
  
• Wenfei Fan, Floris Geerts:
  Relative information completeness. 97-106
  
• Vibhor Rastogi, Michael Hay, Gerome Miklau, Dan Suciu:
  Relationship privacy: output perturbation for queries with joins. 107-116
  

Data analysis and optimization

• Adam Kirsch, Michael Mitzenmacher, Andrea Pietracaprina, Geppino Pucci, Eli Upfal, Fabio Vandin:
  An efficient rigorous approach for identifying statistically significant frequent itemsets. 117-126
  
• Flavio Chierichetti, Ravi Kumar, Sergei Vassilvitskii:
  Similarity caching. 127-136
  
• Pankaj K. Agarwal, Siu-Wing Cheng, Yufei Tao, Ke Yi:
  Indexing uncertain data. 137-146
  

Stream processing

• Vladimir Braverman, Rafail Ostrovsky, Carlo Zaniolo:
  Optimal sampling from sliding windows. 147-156
  
• Radu Berinde, Graham Cormode, Piotr Indyk, Martin J. Strauss:
  Space-optimal heavy hitters with strong error bounds. 157-166
  
• Ke Yi, Qin Zhang:
  Optimal tracking of distributed heavy hitters and quantiles. 167-174
  

Invited tutorial 2

• Lars Arge:
  Worst-case efficient range search indexing: invited tutorial. 175-176
  

Indexing

• Rasmus Pagh, Srinivasa Rao Satti:
  Secondary indexing in one dimension: beyond b-trees and bitmap indexes. 177-186
  
• Ke Yi:
  Dynamic indexability and lower bounds for dynamic one-dimensional range query indexes. 187-196
  

Query evaluation and optimization

• Diego Figueira:
  Satisfiability of downward XPath with data equality tests. 197-206
  
• David DeHaan:
  Equivalence of nested queries with mixed semantics. 207-216
  
• Rada Chirkova, Michael R. Genesereth:
  Equivalence of SQL queries in presence of embedded dependencies. 217-226
  

XML

• Sara Cohen, Benny Kimelfeld, Yehoshua Sagiv:
  Running tree automata on probabilistic XML. 227-236
  
• Pablo Barceló, Leonid Libkin, Antonella Poggi, Cristina Sirangelo:
  XML with incomplete information: models, properties, and query answering. 237-246
  
• Serge Abiteboul, Georg Gottlob, Marco Manna:
  Distributed XML design. 247-258
  

Uncertain data

• Jian Li, Amol Deshpande:
  Consensus answers for queries over probabilistic databases. 259-268
  
• Sudipto Guha, Kamesh Munagala:
  Exceeding expectations and clustering uncertain data. 269-278
  
• Mikhail J. Atallah, Yinian Qi:
  Computing all skyline probabilities for uncertain data. 279-287