Queries
Objective: Develop general understanding of query languages and their capabilities.
- A new and formal definition of query as a mapping.
- 3 fundamental assumptions:
1. Well-typedness.
2. Computability.
3. Genericity.
Well-typedness – the schema of the result is fixed for a given query.
Computability – query mappings are computable, using classical models of computation – TM (Turing Machine).
Question: how can input and output instances be represented on a TM tape that has finite alphabet, when the underlying domain dom is infinite?
Answer: Use a standard encoding for dom!
Definition: Let a be an enumeration of dom. A mapping q from inst(R) to inst(S) is computable relative to a if there exists a TM M s.t. for each instance 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.