Finitely Representable Databases.

摘要: We study infinite but finitely representable databases based on constraints, motivated by new database applications such as those involving spatio-temporal information. introduce a general definition of finite representation and define the concept query generalization over relational databases. investigate theory models prove that it differs from both classical model theory. In particular, we show failure most well-known theorems logic (compactness, completeness, etc.). An important consequence is properties satisfiability containment are undecidable. illustrate use Ehrenfeucht?Frai?sse games expressive power languages As case study, focus queries dense order constraint consider in particular “order-generic” which mappings closed under order-preserving bijections topological queries, homeomorphisms. many interesting connectivity not first-order definable with constraints. then an inflationary fixpoint language, captures exactly all PTIME order-generic queries. Finally, give rapid survey recent results for more contexts, polynomial