The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

An Isaac Newton Institute Workshop

Logic and Databases

A normal form for singulary logic over physically realizable data models

Author: Steven Lindell (Haverford College )


We present a new normal form for first-order logic over bounded-degree structures which relies on the symmetry of labeled connections between elements of the structure. The key idea is to use vocabularies with only monadic predicate and monadic function symbols -- so called singulary logic [Church]. Our proof is effective and syntactic, not relying on games or other semantic characterizations. Linear-time computability of first-order queries becomes a direct corollary of this result. Included will be a discussion of why these data structures are the appropriate models for physically realizable databases.

[Church, A.] Introduction to Mathematical Logic, Princeton University Press, 1956.

Related Links