Lax Lean Archive

Evaluation and containment reduce to each other

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

proven

Loading review…

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

    Containment reduces to evaluation by a first-order reduction, the Chandra–Merlin theorem in reduction form, and evaluation reduces to containment by a first-order reduction, a database being a conjunctive query without variables.

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

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

    1 cqContainment_reduces_to_cqEval proven

    2 cqEval_reduces_to_cqContainment 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: Evaluation and containment reduce to each other
    13type: theorem
    14---
    15Containment reduces to evaluation by a first-order reduction, the Chandra–Merlin
    16theorem in reduction form, and evaluation reduces to containment by a
    17first-order reduction, a database being a conjunctive query without
    18variables.
    19-/
    20
    21namespace Lax420092.EvaluationContainmentReductions
    22
    23open FirstOrder FirstOrder.Language
    24open Lax904597.Problems Lax904597.Interpretations Lax904597.Classes Lax799700.Problems
    25open Lax420092.QueryDatabases Lax420092.Evaluation Lax420092.QueryPairs Lax420092.PackagedInstances
    26
    27/-- Containment reduces to evaluation. -/
    28axiom cqContainment_reduces_to_cqEval : Nonempty (FOReduction CQContainment CQEval)
    29
    30/-- Evaluation reduces to containment. -/
    31axiom cqEval_reduces_to_cqContainment : Nonempty (FOReduction CQEval CQContainment)
    32
    33end Lax420092.EvaluationContainmentReductions
    34
    Show ProofShow Proof
    Builds on
    Used by

    none

    From Mathlib

    none

    Discussion

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

    Loading discussion…