FIRST-ORDER QUERIES ON DATABASES EMBEDDED IN AN INFINITE STRUCTURE

Authors
OTTO M VANDENBUSSCHE J
Citation
M. Otto et J. Vandenbussche, FIRST-ORDER QUERIES ON DATABASES EMBEDDED IN AN INFINITE STRUCTURE, Information processing letters, 60(1), 1996, pp. 37-41
Citations number
11
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
60
Issue
1
Year of publication
1996
Pages
37 - 41
Database
ISI
SICI code
0020-0190(1996)60:1<37:FQODEI>2.0.ZU;2-A
Abstract
We consider ''generic'' (isomorphism-invariant) queries on relational databases embedded in an infinite background structure. Assume a gener ic query is expressible by a first-order formula over the embedded dom ain that may involve both the relations of the database and the relati ons and functions of the background structure. Then this query is alre ady expressible by a first-order formula involving just an auxiliary l inear ordering as background structure. We present an elementary proof of this fact.