The encoding of evaluation instances is faithful and size-honest

Lax420092.EncodingFaithful · concepts/Lax420092/EncodingFaithful.lean · lax-420092

proven

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural 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 2(e+1)22(e+1)^2 for ee elements. The encoding neither pads nor compresses.

    Concept map
    11 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 4 statements. Each proof establishes one of them relative to its assumptions.

    1 concreteQueryHolds_iff_queryHolds proven

    2 cqEncoding_faithful proven

    Lean source view on GitHub

    1import Lax904597.Problems
    2import Lax904597.Interpretations
    3import Lax904597.Classes
    4import Lax799700.Problems
    5import Lax420092.QueryDatabases
    6import Lax420092.Evaluation
    7import Lax420092.QueryPairs
    8import Lax420092.PackagedInstances
    9
    10/-!
    11---
    12title: The encoding of evaluation instances is faithful and size-honest
    13type: theorem
    14---
    15A concrete query holds in a concrete database, whose domain is nonempty,
    16exactly when the query of the structure they give holds in its database; a
    17packaged instance has a satisfied query exactly when the structure it encodes
    18is a yes-instance of CQEval; the encoded structure has at most as many
    19elements as the size of the instance; and the size of the instance is at
    20most 2(e+1)22(e+1)^2 for ee elements. The encoding neither pads nor
    21compresses.
    22-/
    23
    24namespace Lax420092.EncodingFaithful
    25
    26open FirstOrder FirstOrder.Language
    27open Lax904597.Problems Lax904597.Interpretations Lax904597.Classes Lax799700.Problems
    28open Lax420092.QueryDatabases Lax420092.Evaluation Lax420092.QueryPairs Lax420092.PackagedInstances
    29
    30/-- Semantic faithfulness on concrete queries and databases. -/
    31axiom 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. -/
    36axiom cqEncoding_faithful : ∀ i : CQInstance,
    37 ConcreteCQHolds i ↔ CQEval (Fin i.vars ⊕ Fin (i.consts + 1))
    38
    39/-- No padding. -/
    40axiom cqSize_ge_card : ∀ i : CQInstance, i.vars + (i.consts + 1) ≤ cqSize i
    41
    42/-- No compression. -/
    43axiom cqSize_le_card : ∀ i : CQInstance, cqSize i ≤ 2 * (i.vars + (i.consts + 1) + 1) ^ 2
    44
    45end Lax420092.EncodingFaithful
    46
    Show ProofShow ProofShow ProofShow Proof

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…