(Inspired by a letter to the editor in The New Yorker by Alexander George from 24 December 2007.) Steve Martin, the great comedian, reports in Born Standing Up: A Comic’s Life that, inspired by Lewis...

(Inspired by a letter to the editor in The New Yorker by Alexander George from 24 December 2007.) Steve Martin, the great comedian, reports in Born Standing Up: A Comic’s Life that, inspired by Lewis Carroll, he started closing his shows with the following line.11 (It got big laughs.)

Steve Martin describes the joke as a contradiction—but, in fact, these two true things are not contradictory! Describe how it is possible for both “all chairs in Bananaland are green” and “no chairs in Bananaland are green” to be simultaneously true.

As a rough approximation, we can think of a database as a two-dimensional table, where rows correspond to individual entities, and columns correspond to fields (data about those entities). A database query defines a predicate Q(x) that consists of tests of the values from various columns, joined by the basic logical connectives. The database system then returns a list of rows/entities for which the predicate is true. We can think of this type of database access as involving predicates: in response to query Q, the system returns the list of all rows x for which Q(x) is true.