The undecidability of Hilbert's tenth problem (H10) about Diophantine equations turned out to be a powerful tool for establishing the undecidability of many other decision problems. The technique developed for proving the undecidability of H10 gave the possibility to find unexpected relationships between Diophantine equations and some other classical mathematical problems.

We revisit one of the most basic questions of database theory: the equivalence of first-order logic (FO), relational algebra (RA), and the core of SQL. Despite being at the heart of relational theory, these questions do not have satisfactory answers in the literature. The well known equivalence of FO and RA, and existing translations from SQL to RA, work only for simple models that fall short of what real databases use. Proving results about real SQL, rather than a theoretical reconstruction, is hampered by the lack of formal SQL semantics: the Standard is too vague for the purpose, and previous attempts at formalizing SQL's semantics made many simplifying assumptions that do not hold in real life. On the logic side, SQL mixes Boolean and 3-valued logics in a way that has never been properly studied.

Our goal is to fill these surprising gaps in basic database theory. We provide a formal semantics of the core of SQL that captures the real language and accounts for many of its idiosyncrasies. To justify it as the correct semantics, we validate it experimentally on a large number of randomly generated queries. With this semantics, we formally prove the equivalence of core SQL and RA, as well as the extension of 3-valued FO with an operator that accounts for SQL's ability to switch back and forth between Boolean and 3-valued logics. Then, somewhat surprisingly, we show that this additional operator does not add expressiveness, and - even more surprisingly - that 3-valued logic does not add expressiveness even in the presence of nulls.

Based on joint work with with Paolo Guagliardo.

Probabilistic programming is en vogue. It is used to describe complex Bayesian networks, quantum programs, security protocols and biological systems. Programming languages like C, C#, Java, Prolog, Scala, etc. all have their probabilistic version. Key features are random sampling and means to adjust distributions based on obtained information from measurements and system observations. We show some semantic intricacies, argue that termination is more involved than the halting problem, and discuss recursion and run-time analysis.