Finitely Representable Databases

We study classes of infinite but finitely representable databases based onconstraints, motivated by new database applications such as geographicaldatabases. We formally define these notions and introduce the concept of querywhich generalizes queries over classical relational databases. We prove thatin this context the basic properties of queries (satisfiability, containment,equivalence, etc.) are nonrecursive.We investigate the theory of finitely representable models and prove that itdiffers strongly from both classical model theory and finite model theory. Inparticular, we show that most of the well known theorems of either one fail(compactness, completeness, locality, 0/1 laws, etc.). An immediateconsequence is the lack of tools to consider the definability of queries in therelational calculus over finitely representable databases. We illustrate thisvery challenging problem through classical examples.We then mainly concentrate on dense order databases, and exhibit some newtechniques to prove non first-order definability results. The techniquesinclude complexity theoretical arguments and Ehrenfueucht-Fraisse games. Inparticular, we show that queries over finite relations such as parity and graphconnectivity, as well as topological queries such as region connectivity,existence of a hole, Eulerian traversal, homeomorphism, etc. are notfirst-order definable. We also show that inflationary Datalog with negationcaptures exactly all dense order queries computable in PTIME.