PODS '16- Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

Full Citation in the ACM Digital Library


A Theory of Regular Queries

SESSION: PODS Award talks + 1 regular paper

2016 ACM PODS Alberto O. Mendelzon Test-of-Time Award

FAQ: Questions Asked Frequently

Shortest Paths and Distances with Differential Privacy

Minimization of Tree Pattern Queries


Optimal Score Aggregation Algorithms

Hypertree Decompositions: Questions and Answers

SESSION: Session 1: Query rewriting, Views, and Join Algorithms

Incremental View Maintenance For Collection Programming

AJAR: Aggregations and Joins over Annotated Relations

Bounded Query Rewriting Using Views

Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable

Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins

On the Complexity of Inner Product Similarity Join


Data Management for Social Networking

SESSION: Session 2: Workflows and Incomplete Information

Verification of Hierarchical Artifact Systems

Recency-Bounded Verification of Dynamic Database-Driven Systems

Making SQL Queries Correct on Incomplete Databases: A Feasibility Study

Designing a Query Language for RDF: Marrying Open and Closed Worlds

SESSION: Session 3: Data Streams and Indexes

Schema Validation via Streaming Circuits

Variability in Data Streams

Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors

Efficient Top-k Indexing via General Reductions

Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries


Logical Aspects of Massively Parallel and Distributed Systems

SESSION: Session 4: Query Evaluation

Counting Answers to Existential Positive Queries: A Complexity Classification

Computing Join Queries with Functional Dependencies

Semantic Acyclicity Under Constraints

Tractable Lineages on Treelike Instances: Limits and Extensions

SESSION: Session 5: Data Streams and Privacy

Towards Tight Bounds for the Streaming Set Cover Problem

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems

Better Algorithms for Counting Triangles in Data Streams

Locating a Small Cluster Privately

SESSION: Session 6: Algorithms and Data Structures

Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures

Space Lower Bounds for Itemset Frequency Sketches

Are Few Bins Enough: Testing Histogram Distributions

Range-Max Queries on Uncertain Data

Fast Algorithms for Parsing Sequences of Parentheses with Few Errors