Genericity – A query depends only on information provided by the input instance and not on the encoding of dom used.
Intuition: consider a database that consists of a binary relation specifying the edges of directed graph.
Lets look at the following 3 queries:
1. Returns all vertexes with positive in-degree.
2. Returns all vertexes belonging to some cycle and
3. Returns the first vertex of the graph as presented in the TM tape representation.
It is clear that queries 1 and 2 are independent of the internal representation we use, while query 3 depends on it.
Genericity states that the query is insensitive to renaming of the constants in the database using the permutation P.
Now we can generalize our last definition:
Definition: A generic mapping q from inst(R) to inst(S) is computable if there exists a TM M s.t. for each instance I over R and each enumeration a of adom(I):
a. If q(I) is undefined, then M does not terminate on input enca(I).
b. If q(I) is defined, then M halts on input enca(I) with output enca(q(I)) on the tape.