25. PODS 2006: Chicago, Illinois, USA

Keynote

• Alon Y. Halevy, Michael J. Franklin, David Maier:
  Principles of dataspace systems. 1-9
  

PODS award papers

• Mikolaj Bojanczyk, Claire David, Anca Muscholl, Thomas Schwentick, Luc Segoufin:
  Two-variable logic on data trees and XML reasoning. 10-19
  
• Michael A. Bender, Haodong Hu:
  An adaptive packed-memory array. 20-29
  

Data exchange

• Phokion G. Kolaitis, Jonathan Panttaja, Wang Chiew Tan:
  The complexity of data exchange. 30-39
  
• Georg Gottlob, Alan Nash:
  Data exchange: computing cores in polynomial time. 40-49
  
• Ronald Fagin:
  Inverting schema mappings. 50-59
  
• Leonid Libkin:
  Data exchange and incomplete information. 60-69
  

Analysis of queries and workflows

• Sara Cohen:
  Equivalence of queries combining set and bag-set semantics. 70-79
  
• T. S. Jayram, Phokion G. Kolaitis, Erik Vee:
  The containment problem for REAL conjunctive queries with inequalities. 80-89
  
• Alin Deutsch, Liying Sui, Victor Vianu, Dayou Zhou:
  Verification of communicating data-driven web services. 90-99
  
• Toon Calders, Stijn Dekeyser, Jan Hidders, Jan Paredaens:
  Analyzing workflows implied by instance-dependent access rules. 100-109
  

Invited Tutorial 1

• Joseph Y. Halpern:
  From statistical knowledge bases to degrees of belief: an overview. 110-113
  

Database design

• Solmaz Kolahi, Leonid Libkin:
  On redundancy vs dependency preservation in normalization: an information-theoretic study of 3NF. 114-123
  
• Georg Gottlob, Reinhard Pichler, Fang Wei:
  Tractable database design through bounded treewidth. 124-133
  

Popularity and privacy

• Rajeev Motwani, Ying Xu:
  Evolution of page popularity under random web graph models. 134-142
  
• Nina Mishra, Mark Sandler:
  Privacy via pseudorandom sketches. 143-152
  
• Gagan Aggarwal, Tomás Feder, Krishnaram Kenthapadi, Samir Khuller, Rina Panigrahy, Dilys Thomas, An Zhu:
  Achieving anonymity via clustering. 153-162
  
• Ashwin Machanavajjhala, Johannes Gehrke:
  On the efficiency of checking perfect privacy. 163-172
  

Query optimization

• Benny Kimelfeld, Yehoshua Sagiv:
  Finding and approximating top-k answers in keyword proximity search. 173-182
  
• Guizhen Yang, Michael Kifer, Vinay K. Chaudhri:
  Efficiently ordering subgoals with access constraints. 183-192
  
• Anne Condon, Amol Deshpande, Lisa Hellerstein, Ning Wu:
  Flow algorithms for two pipelined filter ordering problems. 193-202
  
• Ashish Goel, Sudipto Guha, Kamesh Munagala:
  Asking the right questions: model-driven optimization using probes. 203-212
  

Invited Tutorial 2

• Christoph Koch:
  Processing queries on tree-structured data efficiently. 213-224
  

Query processing

• Anna Pagh, Rasmus Pagh:
  Scalable computation of acyclic joins. 225-232
  
• Michael A. Bender, Martin Farach-Colton, Bradley C. Kuszmaul:
  Cache-oblivious string B-trees. 233-242
  

Stream algorithms and complexity

• Martin Grohe, André Hernich, Nicole Schweikardt:
  Randomized computations on large data sets: tight lower bounds. 243-252
  
• Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, Christian Sohler:
  Counting triangles in data streams. 253-262
  
• Graham Cormode, Flip Korn, S. Muthukrishnan, Divesh Srivastava:
  Space- and time-efficient deterministic algorithms for biased quantiles over data streams. 263-272
  
• Sudipto Guha, Andrew McGregor:
  Approximate quantiles and the order of the stream. 273-279
  

Frequency counting and aggregation

• Sumit Ganguly, Anirban Majumder:
  Deterministic k-set structure. 280-289
  
• Lap-Kei Lee, H. F. Ting:
  A simpler and more efficient deterministic scheme for finding frequent items over sliding windows. 290-297
  
• Qi Zhao, Mitsunori Ogihara, Haixun Wang, Jun Xu:
  Finding global icebergs over distributed data sets. 298-307
  
• Srinivas R. Kashyap, Supratim Deb, K. V. M. Naidu, Rajeev Rastogi, Anand Srinivasan:
  Efficient gossip-based aggregate computation. 308-317
  

Query, update, and mining languages

• Marc Gyssens, Jan Paredaens, Dirk Van Gucht, George H. L. Fletcher:
  Structural characterizations of the semantics of XPath as navigation tool on a document. 318-327
  
• Balder ten Cate:
  The expressivity of XPath with transitive closure. 328-337
  
• Aaron Bohannon, Benjamin C. Pierce, Jeffrey A. Vaughan:
  Relational lenses: a language for updatable views. 338-347
  
• Sreenivas Gollapudi, Ravi Kumar, D. Sivakumar:
  Programmable clustering. 348-354
  

Invited Tutorial 3

• Enrico Franconi, Sergio Tessaris:
  The logic of RDF and SPARQL: a tutorial. 355
  

Incomplete information

• Riccardo Rosati:
  On the decidability and finite controllability of query processing in databases with incomplete information. 356-365