SIGMOD Record: Database Principles Column

The Database Principles Column of SIGMOD Record publishes surveys of recent results that appear in database theory conferences (such as ACM PODS or ICDT) in a form suitable for a larger audience.

Leonid Libkin edited the column since its inception in 1999 until June 2011, then the column was edited by Pablo Barcelo (June 2011 - December 2015), Frank Neven(December 2015 - September 2019), and Dan Olteanu (September 2019 - December 2023).

Starting from January 2024, Benny Kimelfeld is the editor of the column. Some of the best database theoreticians (and not only database theoreticians) contributed  papers on many different aspects of databases. All of the papers published in the column can be found below and at its source at the SIGMOD Record: here.



Serge Abiteboul

  On views and XML (pdf)



Guozhu Dong, Juanwen Su

    Incremental Maintenance of Recursive Views Using Relational Calculus/SQL (ps)



Jan Van den Bussche

    Constraint Databases: A Tutorial Introduction (pdf)



Alon Halevy

    Theory of Answering Queries Using Views (pdf) 



Peter Buneman, Wenfei Fan, Jerome Simeon, Scott Weinstein

    Constraints for Semi-structured Data and XML (ps)



Luca Cardelli

    Describing Semistructured Data (pdf)



Dan Suciu

    The XML Typechecking Problem (ps)



Ronald Fagin

    Combining Fuzzy Information: an Overview (ps)



Frank Neven

    Automata theory for XML researchers (pdf)



Martin Grohe

    Parameterized Complexity for the Database Theorist (pdf)



Victor Vianu

    From Codd to XML (ps)



Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Vardi

    Regular path queries (pdf)



Thomas Schwentick

    XPath Query Containment (pdf)



Georg Gottlob, Christoph Koch

    Logic-based Web Information Extraction (pdf)



Sara Cohen

     Containment of Aggregate Queries (pdf)



Rick Hull, Jianwen Su

     Tools for Composite Web Services: A Short Overview (pdf)



Francesco Scarcello

     Query Answering Exploiting Structural Properties (pdf)



Alin Deutsch, Lucian Popa, Val Tannen

     Query Reformulation with Constraints (pdf)



Leopoldo Bertossi

     Consistent Query Answering in Databases (pdf)



Marcelo Arenas

     Normalization Theory for XML (pdf)



Luc Segoufin

     Static Analysis of XML Processing with Data Values (pdf)



Wim Martens,   Frank Neven,   Thomas Schwentick

     Simple off the shelf abstractions for XML schema (pdf)



Maarten Marx, Balder ten Cate

     Navigational XPath: calculus and algebra (pdf)



Christoph Koch

     On Query Algebras for Probabilistic Databases (pdf)



Benny Kimelfeld, Yehoshua Sagiv

     Modeling and Querying Probabilistic XML Data (pdf)



Pablo Barcelo

     Logical Foundations of Relational Data Exchange (pdf)



Nicole Schweikardt

     Machine Models for Query Processing (pdf)



Marcelo Arenas, Jorge Perez, Juan Reutter, Cristian Riveros

     Composition and Inversion of Schema Mappings (pdf)



Daniel Deutsch, Tova Milo

     On Models and Query Languages for Probabilistic Processes (pdf)



Andrea Cali, Georg Gottlob, Thomas Lukasiewicz, Andreas Pieris

     A Logical Toolbox for Ontological Reasoning (pdf)



Peter Wood

     Query Languages for Graph Databases (pdf)



Mikolaj Bojanczyk

     Algorithms for Regular Languages that Use Algebra (pdf)



Grigoris Karvounarakis, Todd J. Green

     Semiring-Annotated Data: Queries and Provenance Algebras (pdf)



Marcelo Arenas, Claudio Gutierrez, Daniel Miranker, Jorge Perez, Juan Sequeda

     Querying Semantic Data on the Web (pdf)



Graham Cormode

     The Continuous Distributed Monitoring Model (pdf)



Jan Chomicki, Paolo Ciaccia, Niccolo Meneghetti

     Skyline Queries, Front and Back (pdf)



Hung Q. Ngo, Christopher Re, Atri Rudra

     Skew Strikes Back: New Developments in the Theory of Join Algorithms (pdf)



Andrew Mcgregor.

     Graph Streams Algorithms: A Survey (pdf)



Tom Ameloot

     Declarative Networking: Recent Theoretical Work on Coordination, Correctness, and Declarative Semantics (pdf)



Alin Deutsch, Rick Hull, Victor Vianu

     Automatic Verification of Database-Centric Systems (pdf)

Yael Amsterdamer, Tova Milo

     Foundations of Crowd Data Sourcing (pdf)

Luc Segoufin

     Constant Delay Enumeration for Conjunctive Queries (pdf) 

Wenfei Fan

     Data Quality: From Theory to Practice (pdf)

Ron Fagin, Benny Kimelfeld, Frederick Reiss, Stijn Vansummeren

     A Relational Framework for Information Extraction (pdf)

Dan Olteanu, Maximilian Schleich

     Factorized Databases (pdf)

Serge Abiteboul, Marcelo Arenas, Pablo Barceló, Meghyn Bienvenu, Diego Calvanese, Claire David, Richard Hull, Eyke Hüllermeier, Benny Kimelfeld, Leonid Libkin, Wim Martens, Tova Milo, Filip Murlak, Frank Neven, Magdalena Ortiz, Thomas Schwentick, Julia Stoyanovich, Jianwen Su, Dan Suciu, Victor Vianu, Ke Yi

      Research Directions for Principles of Data Management (Abridged) (pdf)

Paraschos Koutris, Dan Suciu

     A Guide to Formal Analysis of Join Processing in Massively Parallel Systems (pdf)

Pablo Barceló, Andreas Pieris, Miguel Romero

    Semantic Optimization in Tractable Classes of Conjunctive Queries (pdf)

Paolo Guagliardo, Leonid Libkin

    Correctness of SQL Queries on Databases with Nulls (pdf)

Pierre Senellart

    Provenance and Probabilities in Relational Databases: From Theory to Practice (pdf)

Michael Benedikt

    Logic-based Perspectives on Query Reformulation over Restricted Interfaces (pdf)

Peter Buneman, Wang-Chiew Tan

    Data Provenance: What next? (pdf)

Angela Bonifati, Stefania Dumbrava

    Graph Queries: From Theory to Practice (pdf)

Jef Wijsen

     Foundations of Query Answering on Inconsistent Databases (pdf)

Saladi Rahul, Yufei Tao

     A Guide to Designing Top-k Indexes (pdf)

Bernardo Cuenca Grau, Ian Horrocks, Mark Kaminski, Egor V. Kostylev, Boris Motik

     Limit Datalog: A Declarative Query Language for Data Analysis (pdf)

Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, Juan-Pablo Silva

     The Expressive Power of Graph Neural Networks as a Query Language (pdf)

Thomas Schwentick, Nils Vortmeier, Thomas Zeume

     Sketches of Dynamic Complexity (pdf)

Xiao Hu, Ke Yi

     Massively Parallel Join Algorithms (pdf)

Johannes Doleschal, Benny Kimelfeld, Wim Martens

     Database Principles and Challenges in Text Analysis (pdf)

Floris Geerts, Thomas Muñoz, Cristian Riveros, Jan Van den Bussche, Domagoj Vrgoc

     Matrix Query Languages (pdf)

Graham Cormode

     Current Trends in Data Summaries (pdf)

Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, Dan Suciu, and Yisu Remy Wang

     Datalog in Wonderland (pdf)

Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros

     Counting the Answers to a Query (pdf)

Bas Ketsman, Frank Neven, Christoph Koch, Brecht Vandevoort

     Concurrency Control for Database Theorists (pdf)

Leopoldo Bertossi, Ester Livshits, Benny Kimelfeld, and Mikaël Monet

The Shapley Value in Database Management (pdf)

Wei Dong and Ke Yi

Query Evaluation under Differential Privacy (pdf)

Balder ten Cate, Maurice Funk, Jean Christoph Jung, Carsten Lutz

Fitting Algorithms for Conjunctive Queries (pdf)

Antoine Amarilli and Florent Capelli

Tractable Circuits in Database Theory (pdf)

Nikolaos Tziavelis, Wolfgang Gatterbauer, and Mirek Riedewald

Ranked Enumeration for Database Queries (pdf)

Mahmoud Abo Khamis, Dan Olteanu, Kyle Deeds, and Dan Suciu

Pessimistic Cardinality Estimation (pdf)

Albert Atserias and Phokion G. Kolaitis

Consistency Witnesses for Annotated Relations (pdf)