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
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.