PODS Invited Talks
Keynote
How Can Reasoners Simplify Database Querying (And Why Haven't They Done It Yet)?
Speaker: Michael Benedikt (Oxford University)
Abstract
This talk will be a reflection on the state of tools and algorithms for applying reasoning to simplify database querying. What's been done, and how well did it work? One motivation for this comes from within database theory, where a huge amount of research has been devoted to reasoning problems. The work spans several decades and includes a wide range of problems, including query equivalence, query simplification, and many flavors of query transformation/rewriting. It's a good moment to try to make sense of what's been done, highlighting some accomplishments as well as gaps. A second motivation comes from outside of database management, where there has been enormous progress in the development of reasoning systems. The advances have not only been in theory, but in system building, engineering, and the development of a robust culture of experimental evaluation. It's worthwhile examining how work on reasoning for query simplification and transformation within data management -- the stuff done at database conferences like PODS -- fits within the larger landscape of automated reasoning. It's also useful to consider how the increasing maturity of reasoning systems could be harnessed to solve database querying problems.
Bio
Michael Benedikt is a professor at Oxford University's computer
science department, and a fellow of University College Oxford. He came
to Oxford after a decade in US industrial research laboratories,
including a position as Distinguished Member of Technical Staff at
Bell Laboratories. He has worked extensively in computational logic,
finite model theory, verification, and data management, and
specializes in the interaction between these topics.
He has been a keynote in past meetings on mathematical logic,
computational logic, description logics, and databases.
He has co-authored papers receiving best paper awards and test-of-time
awards in major conferences within databases and theoretical computer
science, and he has served as the program chair of both the ACM Principles of Database Systems conference (2012) and the International Conference on Database Theory (2017).
He currently holds an Established Career Fellowship from the UK's
Engineering and Physical Science's Research Council, and
serves on the steering committees for the Association for
Symbolic Logic, the European Association for Theoretical Computer
Science, and the International Conference on Database Theory.
Tutorial 1
Blockchains: Past, Present, and Future
Speaker: Arvind Narayanan (Princeton University)
Abstract
Blockchain technology is assembled from pieces that have long pedigrees in the academic literature, such as linked timestamping, consensus, and proof of work. In this tutorial, I'll begin by summarizing these components and how they fit together in Bitcoin's blockchain design. Then I'll present abstract models of blockchains; such abstractions help us understand and reason about the similarities and differences between the numerous proposed blockchain designs in a succinct way. Here is one such abstraction. Blockchains can be understood in terms of (1) a log of messages: for example, a ledger of financial transactions; (2) the state that summarizes the result of processing the log: for example, a set of account balances; (3) a set of validity rules for messages/state updates: for example, transactions must spend no more than the available balances, must have verifiable signatures, etc; (4) consistency rules that determine whether two views of the log by different participants on the network are consistent with each other. In the second half of the tutorial I'll describe several research directions, focusing on those likely to be of interest to the PODS community. Here are a few examples.
-- Efficient verification of state. A participant might want to verify a statement about a small part of the global state, such as the inclusion of a particular transaction in the blockchain. While the basics have been worked out, and involve hash pointers, Merkle trees, and other ''authenticated data structures'', many interesting questions remain.
-- Reconciling different views of consensus. In the game theory view of blockchains, all players are rational and follow their incentives; there are no honest, faulty, or malicious players. How do the predictions of this view com pared to those of the traditional consensus literature? Can we come up with hybrid models that reconcile these assumptions?
-- Scaling and sharding. In traditional designs, the blockchain is fully replicated by every node, leading to massive inefficiency and severely limiting transaction throughput. What are the fundamental limits to scaling, and how can we improve scalability without weakening security? In particular, is it possible to shard the blockchain, that is, partition it among subsets of nodes, given the Byzantine setting?
Bio
Arvind Narayanan is an Assistant Professor of Computer Science at Princeton. He leads the Princeton Web Transparency and Accountability Project to uncover how companies collect and use our personal information. Narayanan also leads a research team investigating the security, anonymity, and stability of cryptocurrencies as well as novel applications of blockchains. He co-created a Massive Open Online Course as well as a textbook on Bitcoin and cryptocurrency technologies. His doctoral research showed the fundamental limits of de-identification, for which he received the Privacy Enhancing Technologies Award. Narayanan is an affiliated faculty member at the Center for Information Technology Policy at Princeton and an affiliate scholar at Stanford Law School's Center for Internet and Society.
Tutorial 2
In-memory Representations of Databases via Succinct Data Structures
Speaker: Rajeev Raman (University of Leicester)
Abstract
In recent years, the field of succinct data structures (SDS) has grown rapidly. SDS store data in main memory space that approaches an information-theoretic minimum, and support operations on the data with little or no slow-down compared to their conventional counterparts. In practice, an SDS uses one to two orders of magnitude less main memory than a conventional data structure. For this reason, SDS are becoming a popular approach for storing data that is only somewhat bigger than main memory. This tutorial explores the fundamentals of SDS and their applications to a variety of database problems.
Bio
Rajeev Raman is a Professor at the Department of Informatics, University of Leicester, UK, and served as Head of Department from 2003-06; he is currently Director of Research. He was previously a Lecturer (Assistant Professor) at King's College London, and held post-doc positions at UMIACS, University of Maryland and MPI Informatik. He got his PhD from the University of Rochester in 1993 and his Bachelors' from IIT Delhi in 1986. His research interests are in analysis, design and engineering of data structures and algorithms. He has worked on succinct, or highly space-efficient, data structures since 2001. He is currently investigating applications of succinct data structures in areas such as data mining.
