Selected Papers from Datalog 2.0 2022

The four papers following this introduction were originally presented at the 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog 2.0 2022). The workshop Program Committee chairs in collaboration with the editor-in-chief of Theory and Practice of Logic Programming journal invited the authors of these papers to extend them and submit the full versions for publication in the journal.

The Workshop

The 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog 2.0 2022; https://sites.google.com/unical.it/datalog20-2022) was held in Genova Nervi, Italy, on September 5, 2022, marking another significant milestone in the world of logic programming. Hosted by the 16th International Conference on Logic Programming and Non-monotonic Reasoning (LPNMR 2022), the workshop aimed to unite Datalog researchers, implementors, and users, fostering an environment of shared experiences, collaboration, and the identification of avenues for joint future research.

Datalog, a formal query language with roots dating back to the early 1970s, has experienced a remarkable resurgence in recent years. Its applications have expanded across various domains in computer science and industry, making it a dynamic and vital area of research. The evolution of Datalog has been chronicled through the Datalog 2.0 workshop series, which began as an invitation-only event in Oxford, UK, in 2010. As the interest in Datalog continued to grow, the workshop opened its doors for submissions in the second edition held in Vienna, Austria, in 2012. The third edition took place in Philadelphia, PA (USA), in 2019, signaling the workshop’s global reach and relevance.

The 4th edition of Datalog 2.0, with its doors wide open for submissions, received an impressive response from the research community. Twenty-four groups of researchers submitted their articles for peer review. Each submission underwent a rigorous evaluation process, with at least three program committee members meticulously assessing the technical merit and potential for stimulating discussions. Ultimately, 21 papers were accepted, showcasing the depth and breadth of ongoing research in the field.

One of the highlights of Datalog 2.0 2022 was an enlightening invited talk by Reinhard Pichler, adding a valuable perspective to the workshop’s discussions. The inclusion of distinguished speakers ensures that participants benefit from diverse insights and further enriches the collaborative atmosphere that defines the workshop.

In conclusion, Datalog 2.0 2022 stands as a testament to the vibrant and collaborative nature of the Datalog community. As the workshop continues to evolve, it serves as a hub for the exchange of ideas, the cultivation of partnerships, and the charting of new territories in the ever-expanding realm of logic programming. We eagerly anticipate the fruits of the collaborations sparked at Datalog 2.0 2022, confident that they will contribute to the ongoing resurgence and innovation in Datalog research.

Articles in the Special Issue

CNL2ASP: Converting Controlled Natural Language Sentences into ASP – by Simone Caruso, Carmine Dodaro, Marco Maratea, Marco Mochi, and Francesco Riccio. Answer Set Programming (ASP) is a popular extension of Datalog with linguistic constructs to ease the representation of complex combinatorial problems. This article aims at expanding the user base of ASP by introducing a higher level language closely resembling natural language for specifying ASP programs. The proposed language, named CNL2ASP, is a pioneering tool designed to translate English sentences expressed in a controlled natural language (CNL) into ASP.

Dyadic Existential Rules – by Georg Gottlob, Marco Manna, and Cinzia Marte. Ontological reasoning can be expressed in Datalog by extending the language with existential quantification over variables occurring in rule heads, which, however, has the downside of making querying answering undecidable in general. Several decidable fragments of the extended language have been identified in the last two decades, often by taking advantage of different properties. These differences make it difficult or impossible the sharing of tools developed for preexisting classes. In this article, the authors introduce a syntactic condition guaranteeing that any decidable class of existential rules can be extended to incorporate Datalog itself, without increasing the complexity of query answering (the complexity is the smaller between the one of the starting class and the one of Datalog).

Querying Data Exchange Settings Beyond Positive Queries – by Marco Calautti, Sergio Greco, Cristian Molinaro, and Irina Trubitsyna. Data exchange deals with addressing the transfer of data from a source schema to a target schema. This article focuses on queries with negation by introducing a new semantics that aligns with the classical one for positive queries, does not compromise query answering complexity, and is still undecidable in general. However, the new semantics is proven to be coNP-complete for weakly acyclic dependencies, opening the possibility to use ASP for efficient computation of exact answers. Finally, the article introduces a method for computing approximate answers in polynomial time.

Querying Incomplete Data: Complexity and Tractability via Datalog and First-Order Rewritings – by Amélie Gheerbrant, Leonid Libkin, Alexandra Rogova, and Cristina Sirangelo. Databases have mechanisms to express missing data, and queries over incomplete data are usually answered by providing certain answers, that is, those consistently true regardless of how incomplete data is interpreted. The computation of certain answers is efficient for union of conjunctive queries, even in the presence of constraints, if negation is inhibited. This article recast query answering in three different ways, so that a mild form of negation can be still added to the language preserving efficiency of computation for union of conjunctive queries.