The encoding of evaluation instances is faithful and size-honest
Lax420092.EncodingFaithful · concepts/Lax420092/EncodingFaithful.lean · lax-420092
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
A concrete query holds in a concrete database, whose domain is nonempty, exactly when the query of the structure they give holds in its database; a packaged instance has a satisfied query exactly when the structure it encodes is a yes-instance of CQEval; the encoded structure has at most as many elements as the size of the instance; and the size of the instance is at most for elements. The encoding neither pads nor compresses.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Lax904597.Problems |
| 2 | import Lax904597.Interpretations |
| 3 | import Lax904597.Classes |
| 4 | import Lax799700.Problems |
| 5 | import Lax420092.QueryDatabases |
| 6 | import Lax420092.Evaluation |
| 7 | import Lax420092.QueryPairs |
| 8 | import Lax420092.PackagedInstances |
| 9 | |
| 10 | /-! |
| 11 | --- |
| 12 | title: The encoding of evaluation instances is faithful and size-honest |
| 13 | type: theorem |
| 14 | --- |
| 15 | A concrete query holds in a concrete database, whose domain is nonempty, |
| 16 | exactly when the query of the structure they give holds in its database; a |
| 17 | packaged instance has a satisfied query exactly when the structure it encodes |
| 18 | is a yes-instance of CQEval; the encoded structure has at most as many |
| 19 | elements as the size of the instance; and the size of the instance is at |
| 20 | most for elements. The encoding neither pads nor |
| 21 | compresses. |
| 22 | -/ |
| 23 | |
| 24 | namespace Lax420092.EncodingFaithful |
| 25 | |
| 26 | open FirstOrder FirstOrder.Language |
| 27 | open Lax904597.Problems Lax904597.Interpretations Lax904597.Classes Lax799700.Problems |
| 28 | open Lax420092.QueryDatabases Lax420092.Evaluation Lax420092.QueryPairs Lax420092.PackagedInstances |
| 29 | |
| 30 | /-- Semantic faithfulness on concrete queries and databases. -/ |
| 31 | axiom concreteQueryHolds_iff_queryHolds : ∀ {V C : Type} [Nonempty C] |
| 32 | (q : List ((V ⊕ C) × (V ⊕ C))) (D : List (C × C)), |
| 33 | ConcreteQueryHolds q D ↔ @QueryHolds (V ⊕ C) (queryDbStructure q D) |
| 34 | |
| 35 | /-- Faithfulness of the packaged encoding. -/ |
| 36 | axiom cqEncoding_faithful : ∀ i : CQInstance, |
| 37 | ConcreteCQHolds i ↔ CQEval (Fin i.vars ⊕ Fin (i.consts + 1)) |
| 38 | |
| 39 | /-- No padding. -/ |
| 40 | axiom cqSize_ge_card : ∀ i : CQInstance, i.vars + (i.consts + 1) ≤ cqSize i |
| 41 | |
| 42 | /-- No compression. -/ |
| 43 | axiom cqSize_le_card : ∀ i : CQInstance, cqSize i ≤ 2 * (i.vars + (i.consts + 1) + 1) ^ 2 |
| 44 | |
| 45 | end Lax420092.EncodingFaithful |
| 46 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments