led to more powerful constructs being added to database query languages, such as recursive WITH in SQL:1999. More expressive logics, like fixpoint logics, have therefore been studied in finite model theory because of their relevance to database theory and applications. Querying and search Narrative data contains no defined relations. Thus the logical structure of text search queries can be expressed in propositional logic, like in: ("Java" AND NOT "island") OR ("C#" AND NOT "music") Note that the challenges in full text search are different from database querying, like ranking of results. History Trakhtenbrot 1950: failure of completeness theorem in first-order logic Scholz 1952: characterisation of spectra in first-order logic Fagin 1974: the set of all properties expressible in existential second-order logic is precisely the complexity class NP Chandra, Harel 1979/80: fixed-point first-order logic extension for database query languages capable of expressing transitive closure -> queries as central objects of FMT Immerman, Vardi 1982: fixed-point logic over ordered structures captures PTIME -> descriptive complexity (Immerman–Szelepcsényi theorem) Ebbinghaus, Flum 1995: first comprehensive book "Finite Model Theory" Abiteboul, Hull, Vianu 1995: book "Foundations of Databases" Immerman 1999: book "Descriptive Complexity" Kuper, Libkin, Paredaens 2000: book "Constraint Databases" Darmstadt 2005/ Aachen 2006: first international workshops on "Algorithmic Model Theory" Citations References Glebskiĭ, Yu V., D. I. Kogan, M. I. Liogon'kiĭ, and V. A. Talanov. "Volume and fraction of satisfiability of formulae of the first-order predicate calculus." Kibernetika 2 (1969): 17-27. Further reading External links Also suitable as a general introduction and overview. Leonid Libkin. Introductory chapter of "Elements of Finite Model Theory" . Motivates three main application areas: databases, complexity and formal languages. Jouko Väänänen. A Short Course on Finite Model Theory. Department of Mathematics, University of Helsinki. Based on lectures from 1993-1994. Anuj Dawar. Infinite and Finite Model Theory, slides, University of Cambridge, 2002. Includes a list of open FMT problems.