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.