Re: Tarski school influence on Database Theory

On Monday, July 20, 2015 at 12:51:34 PM UTC-7, Tegiri Nenashi wrote:

> The second one quotes John Etchemendy: "You see those big shiny Oracle towers on Highway 101? They would never have been built without Tarski's work on the recursive definitions of satisfaction and truth".
>
> Do those arguments look compelling?

The quote is just a claim, not an argument. It's a bit much to say it's true.

Tarski is responsible for the most common modern way to give predicate logic semantics. That involves supplying an interpretation/model then determining the truth of a formula in terms of the truth from substitutions of values for variables in it, which is recursively defined in terms of the truth from substitutions of values for variables in its constituent formulas. (This is not clearly expressed by "recursive definitions of satisfaction and truth" but seems to be what is referred to.)

Of course lots of logicians clarified, simplified and made rigorous predicate logic as a tool for thought. But there's nothing in Tarskian semantics that is particularly more applicable to database management than other foundational work. Also, that level of formality is not necessary for understanding or defining relational database theory. (Eg SQL doesn't even have predicate logic style quantification.) Also, relational algebra itself gives an alternate means of describing the semantics for predicate logic! So you don't need Tarskian semantics.

The paper makes clear that Tarski's work on binary relation is relevant to relational database theory in that an n-ary relation can be encoded (ugh) as nested 2-tuples. Also the paper itself uses binary relations for representing headings, tuples and functional dependencies. Hence the paper paraphrases the quote to give credit to Tarski's binary relations rather than his substitution semantics for predicate logic. It's not clear what they mean in terms of historical influence. Maybe the role of binary functions as headings, tuples and FDs.

Tarski's work most relevant to relational databases is on cylindric algebras. (A cylinder is essentially a relational relation with all possible attributes.) It was inspired as an algebraization of predicate logic, ie as a replacement for his earlier semantics presentation. But Tarski didn't particularly investigate that particular case. This work was not well known when Codd developed his relational algebra. The first part of the first full presentation was not until 1971.

www.encyclopedia.com
Tarski's research on relation algebras led to his most ambitious algebraic creation, cylindrical algebras. During the period 1948-1952 he and his student Fred Thompson formulated the notion of cylindrical algebra as an algebraic analogue of first-order logic. That is, the class of cylindrical algebras was to bear the same relation to first-order logic with identity that the class of Boolean algebras bears to propositional logic. From the 1950's until his death, Tarski investigated cylindrical algebras and their representability, first with Leon Henkin and then with his former student Donald Monk as well.

https://en.wikipedia.org/wiki/Alfred_Tarski In the late 1940s, Tarski and his students devised cylindric algebras, which are to first-order logic what the two-element Boolean algebra is to classical sentential logic. This work culminated in the two monographs by Tarski, Henkin, and Monk (1971, 1985).

Besides inventing relational algebra, Codd also initiated and championed query safety, integrity, normal forms and other issues involving application of relational algebra to database management, ie the relational model. What really would have helped the database field but that *didn't* happen is if people had paid more attention to what Codd was saying about being relational.

philip Received on Tue Jul 21 2015 - 01:09:59 CEST