Open Collections

Description

The standard approach to algorithm development is to focus on a specific problem and develop for it a specific algorithm. Coddʼs introduction of the relational model in 1970 included two fundamental ideas: (1) relations provide a universal data representation formalism, and (2) relational databases can be queried using first-order logic. Realizing these ideas required the development of a meta-algorithm, which takes a declarative query and executes it with respect to a database. In this talk, I will describe this approach, which I call Logical Algorithmics, in detail, and trace a decades-long path from the computational complexity theory of relational queries to recent tools for Boolean reasoning.