ACM SIGMOD City, Country, Year
sigmod pods logo

PODS Invited Talks


A Theory of Regular Queries

Moshe Y. Vardi (Rice University)


A major theme in relational database theory is navigating the tradeoff between expressiveness and tractability for query languages, where the query-containment problem is considered a benchmark of tractability. The query class UCQ, consisting off unions of conjunctive queries, is a fragment of first-order logic that has a decidable query-containment problem, but its expressiveness is limited. Extending UCQ with recursion yields Datalog, an expressive query language that has been studied extensively and has recently become popular in application areas such as declarative networking. Unfortunately, Datalog has an undecidable query-containment problem. Identifying a fragment of Datalog that is expressive enough for applications but has a decidable query-containment problem has been an open problem for several years.

In the area of graph database, there has been a similar search for a query language that combines expressiveness and tractability. Because of the need to navigate along graph paths of unspecified length, transitive closure has been considered a fundamental operation. Query classes of increasing complexity -- built from atomic queries, using the operations of disjunction, conjunction, projection, and transitive closure -- have been studied, but the classes lacked natural closure properties. The class RQ of regular queries has emerged only recently as a natural query class that is closed under all of its operations and has a decidable query-containment problem.

RQ turned out to be a fragment of Datalog where recursion can be used only to express transitive closure. Furthermore, it turns out that applying this idea to Datalog, that is, restricting recursion to the expression of transitive closure, does yield the long-sought goal -- an expressive fragment of Datalog with a decidable query-optimization problem.


Moshe Y. Vardi is the George Distinguished Service Professor in Computational Engineering and Director of the Ken Kennedy Institute for Information Technology at Rice University. He is the recipient of three IBM Outstanding Innovation Awards, the ACM SIGACT Goedel Prize, the ACM Kanellakis Award, the ACM SIGMOD Codd Award, the Blaise Pascal Medal, the IEEE Computer Society Goode Award, the EATCS Distinguished Achievements Award, and the Southeastern Universities Research Association's Distinguished Scientist Award. He is the author and co-author of over 500 papers, as well as two books: Reasoning about Knowledge and Finite Model Theory and Its Applications. He is a Fellow of the Association for Computing Machinery, the American Association for Artificial Intelligence, the American Association for the Advancement of Science, the European Association for Theoretical Computer Science, the Institute for Electrical and Electronic Engineers, and the Society for Industrial and Applied Mathematics. He is a member of the US National Academy of Engineering and National Academy of Science, the American Academy of Arts and Science, the European Academy of Science, and Academia Europaea. He holds honorary doctorates from the Saarland University in Germany, Orleans University in France, and UFRGS in Brazil. He is the Editor-in-Chief of the Communications of the ACM.

Tutorial 1

Data Management for Social Networking

Sara Cohen (Hebrew University of Jerusalem


Social networks are fascinating and valuable datasets, which can be leveraged to better understand society, and to make inter-personal choices. This tutorial explores fundamental issues that arise when storing and querying social data. The discussion is divided into three main parts. First, we consider some of the key computational problems that arise over the social graph structure, e.g., node centrality, link prediction and community detection. Second, we consider algorithmic problems that leverage both the textual content and the graph structure of a social network, such as, social search and querying, and team formation. Finally, we consider critical aspects of implementing a social network database management system, and discuss existing systems. Some gaps between the state-of-the-art and desired features of a data management system for social networking are pointed out, and open research challenges are discussed.


Sara Cohen received her PhD in 2004 from the Hebrew University of Jerusalem. From 2004-2007 she was a faculty member at the Technion - Israel Institue of Technology. In 2007, she joined Hebrew University, where she is currently an associate professor. Sara's research is focused on theoretical and practical issues in databases, and in particular, query equivalence and rewriting, enumeration of large query results, and graphs and social networks.

Tutorial 2

Logical Aspects of Massively Parallel and Distributed Systems

Frank Neven (Hasselt University)


Database research has witnessed a renewed interest for data processing in distributed and parallel settings. While distributed and parallel data management systems have been around for quite some time, it is the rise of cloud computing and the advent of Big Data that presents the community with new challenges. This talk highlights recent research concerning the logical foundations of massively parallel and distributed systems. The first part of the talk concerns massively parallel systems where computation proceeds in a number of synchronized rounds. Here, the focus is on evaluation algorithms for conjunctive queries as well as on reasoning about correctness and optimization of such algorithms. The second part addresses a distributed asynchronous setting where eventual consistency comes into play. Here, the focus is on coordination-free computation and its relationship to logical monotonicity and Datalog programs.


Frank Neven is a full professor at Hasselt University (Belgium) where he also received his PhD in 1999 under the supervision of Jan Van den Bussche. His research interests include the theory and practice of databases with a strong interest in automata and logic. He received three PODS best paper awards and currently is the editor of the Database Principles Column of SIGMOD Record.

Follow our progress: FacebookTwitter