| 2016 | 2016 ACM PODS Alberto O. Mendelzon Test-of-Time Award. Marcelo Arenas, Peter Buneman, Jan Van den Bussche |
| 2016 | A Theory of Regular Queries. Moshe Y. Vardi |
| 2016 | AJAR: Aggregations and Joins over Annotated Relations. Manas R. Joglekar, Rohan Puttagunta, Christopher Ré |
| 2016 | An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems. Arnab Bhattacharyya, Palash Dey, David P. Woodruff |
| 2016 | Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries. Michael A. Bender, Jonathan W. Berry, Rob Johnson, Thomas M. Kroeger, Samuel McCauley, Cynthia A. Phillips, Bertrand Simon, Shikha Singh, David Zage |
| 2016 | Are Few Bins Enough: Testing Histogram Distributions. Clément L. Canonne |
| 2016 | Better Algorithms for Counting Triangles in Data Streams. Andrew McGregor, Sofya Vorotnikova, Hoa T. Vu |
| 2016 | Bounded Query Rewriting Using Views. Yang Cao, Wenfei Fan, Floris Geerts, Ping Lu |
| 2016 | Computing Join Queries with Functional Dependencies. Mahmoud Abo Khamis, Hung Q. Ngo, Dan Suciu |
| 2016 | Counting Answers to Existential Positive Queries: A Complexity Classification. Hubie Chen, Stefan Mengel |
| 2016 | Data Management for Social Networking. Sara Cohen |
| 2016 | Designing a Query Language for RDF: Marrying Open and Closed Worlds. Marcelo Arenas, Martín Ugarte |
| 2016 | Efficient Top-k Indexing via General Reductions. Saladi Rahul, Yufei Tao |
| 2016 | FAQ: Questions Asked Frequently. Mahmoud Abo Khamis, Hung Q. Ngo, Atri Rudra |
| 2016 | Fast Algorithms for Parsing Sequences of Parentheses with Few Errors. Arturs Backurs, Krzysztof Onak |
| 2016 | Hypertree Decompositions: Questions and Answers. Georg Gottlob, Gianluigi Greco, Nicola Leone, Francesco Scarcello |
| 2016 | Incremental View Maintenance For Collection Programming. Christoph Koch, Daniel Lupei, Val Tannen |
| 2016 | Locating a Small Cluster Privately. Kobbi Nissim, Uri Stemmer, Salil P. Vadhan |
| 2016 | Logical Aspects of Massively Parallel and Distributed Systems. Frank Neven |
| 2016 | Making SQL Queries Correct on Incomplete Databases: A Feasibility Study. Paolo Guagliardo, Leonid Libkin |
| 2016 | Minimization of Tree Pattern Queries. Wojciech Czerwinski, Wim Martens, Matthias Niewerth, Pawel Parys |
| 2016 | On the Complexity of Inner Product Similarity Join. Thomas Dybdahl Ahle, Rasmus Pagh, Ilya P. Razenshteyn, Francesco Silvestri |
| 2016 | Optimal Score Aggregation Algorithms. Ronald Fagin |
| 2016 | Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures. Pankaj K. Agarwal, Kyle Fox, Kamesh Munagala, Abhinandan Nath |
| 2016 | Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016 Tova Milo, Wang-Chiew Tan |
| 2016 | Range-Max Queries on Uncertain Data. Pankaj K. Agarwal, Nirman Kumar, Stavros Sintos, Subhash Suri |
| 2016 | Recency-Bounded Verification of Dynamic Database-Driven Systems. Parosh Aziz Abdulla, C. Aiswarya, Mohamed Faouzi Atig, Marco Montali, Othmane Rezine |
| 2016 | Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable. Tomasz Gogacz, Jerzy Marcinkowski |
| 2016 | Schema Validation via Streaming Circuits. Filip Murlak, Charles Paperman, Michal Pilipczuk |
| 2016 | Semantic Acyclicity Under Constraints. Pablo Barceló, Georg Gottlob, Andreas Pieris |
| 2016 | Shortest Paths and Distances with Differential Privacy. Adam Sealfon |
| 2016 | Space Lower Bounds for Itemset Frequency Sketches. Edo Liberty, Michael Mitzenmacher, Justin Thaler, Jonathan R. Ullman |
| 2016 | Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors. Vladimir Braverman, Stephen R. Chestnut, David P. Woodruff, Lin F. Yang |
| 2016 | Towards Tight Bounds for the Streaming Set Cover Problem. Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi, Ali Vakilian |
| 2016 | Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins. Xiao Hu, Ke Yi |
| 2016 | Tractable Lineages on Treelike Instances: Limits and Extensions. Antoine Amarilli, Pierre Bourhis, Pierre Senellart |
| 2016 | Variability in Data Streams. David Felber, Rafail Ostrovsky |
| 2016 | Verification of Hierarchical Artifact Systems. Alin Deutsch, Yuliang Li, Victor Vianu |