Packaged evaluation instances, their encoding and decoding

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

definition

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

    Definition

    A concrete Boolean conjunctive query over variables and constants is a list of binary atoms with arguments in their disjoint union, and a concrete graph database a list of facts over the constants; the query holds in the database when some assignment of the variables to constants sends every atom to a fact. A packaged instance fixes the numbers of variables and of constants, at least one constant, with finite sets of atoms and of facts; its size is the textbook one, elements plus atoms plus facts. The encoder computes the structure of an instance, on its variables and constants as universe, and a concrete query and database give a structure on their disjoint union directly. A presentation is a raw relation table on a finite universe; an instance is well-formed when some element is a constant, which a first-order sentence states, and the decoder reads a packaged instance off a well-formed presented structure by numbering its variables and its constants in order. Well-formed evaluation is evaluation restricted to well-formed instances.

    Concept map
    9 concepts; 8 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Mathlib.SetTheory.Cardinal.Finite
    2import Mathlib.ModelTheory.Semantics
    3import Mathlib.ModelTheory.Complexity
    4import Mathlib.Tactic.FinCases
    5import Mathlib.ModelTheory.Order
    6import Mathlib.Data.Fintype.Lattice
    7import Mathlib.Data.Set.Finite.Lemmas
    8import Mathlib.Order.PiLex
    9import Mathlib.Data.Prod.Lex
    10import Mathlib.Data.Fintype.EquivFin
    11import Mathlib.Logic.Equiv.Fin.Basic
    12import Mathlib.Data.Finite.Sigma
    13import Mathlib.ModelTheory.Syntax
    14import Mathlib.ModelTheory.Graph
    15import Mathlib.Combinatorics.SimpleGraph.Coloring.Vertex
    16import Lax420092.QueryDatabases
    17import Mathlib.Data.Finset.Sort
    18import Lax904597.Classes
    19import Lax799700.Problems
    20import Lax420092.Evaluation
    21
    22/-!
    23---
    24title: Packaged evaluation instances, their encoding and decoding
    25type: definition
    26---
    27A concrete Boolean conjunctive query over variables and constants is a list
    28of binary atoms with arguments in their disjoint union, and a concrete graph
    29database a list of facts over the constants; the query holds in the
    30database when some assignment of the variables to constants sends every
    31atom to a fact. A packaged instance fixes the numbers of variables and of
    32constants, at least one constant, with finite sets of atoms and of facts;
    33its size is the textbook one, elements plus atoms plus facts. The encoder
    34computes the structure of an instance, on its variables and constants as
    35universe, and a concrete query and database give a structure on their
    36disjoint union directly. A presentation is a raw relation table on a finite
    37universe; an instance is well-formed when some element is a constant, which
    38a first-order sentence states, and the decoder reads a packaged instance off
    39a well-formed presented structure by numbering its variables and its
    40constants in order. Well-formed evaluation is evaluation restricted to
    41well-formed instances.
    42-/
    43
    44namespace Lax420092.PackagedInstances
    45
    46open Lax420092.QueryDatabases
    47
    48open FirstOrder
    49
    50open Language Structure
    51
    52
    53/-- A concretely presented finite `L`-structure: a size and a computable
    54relation table. This is the input type of decoders – the “raw bytes” a
    55decoding computation reads. -/
    56structure FinPresentation (L : Language.{0, 0}) where
    57 /-- The number of elements. -/
    58 card : ℕ
    59 /-- The relations, as computations on `Fin card`. -/
    60 relBool : ∀ {n}, L.Relations n → (Fin n → Fin card) → Bool
    61
    62/-- The `L`-structure a presentation presents. -/
    63instance FinPresentation.str {L : Language.{0, 0}} [L.IsRelational] (S : FinPresentation L) :
    64 L.Structure (Fin S.card) where
    65 funMap f := isEmptyElim f
    66 RelMap R x := S.relBool R x = true
    67
    68section Concrete
    69
    70variable {V C : Type}
    71
    72/-- The textbook semantics of a concrete Boolean conjunctive query `q` (a
    73list of binary atoms with arguments in `V ⊕ C`: variables to the left,
    74constants to the right) on a concrete graph database `D` (a list of facts
    75over the constants): some assignment of the variables to constants sends
    76every atom to a fact. -/
    77def ConcreteQueryHolds (q : List ((V ⊕ C) × (V ⊕ C))) (D : List (C × C)) : Prop :=
    78 ∃ v : V → C, ∀ p ∈ q, (Sum.elim v id p.1, Sum.elim v id p.2) ∈ D
    79
    80end Concrete
    81
    82/-- A packaged concrete evaluation instance: `n` query variables, `m + 1`
    83database constants, a finite set of query atoms over them, and a finite set
    84of database facts on the constants. -/
    85structure CQInstance where
    86 /-- The number of query variables. -/
    87 vars : ℕ
    88 /-- The number of constants, minus one: constants are `Fin (consts + 1)`,
    89 so the database domain is never empty. -/
    90 consts : ℕ
    91 /-- The query atoms, over variables and constants. -/
    92 atoms : Finset ((Fin vars ⊕ Fin (consts + 1)) × (Fin vars ⊕ Fin (consts + 1)))
    93 /-- The database facts, over the constants. -/
    94 facts : Finset (Fin (consts + 1) × Fin (consts + 1))
    95 deriving DecidableEq
    96
    97/-- The textbook size of a packaged instance: elements (variables and
    98constants) plus atoms plus facts. This is the one audited line of the
    99encoding – everything else is checked against it. -/
    100def cqSize : CQInstance → ℕ
    101 | ⟨n, m, q, D⟩ => n + (m + 1) + q.card + D.card
    102
    103/-- The textbook semantics of a packaged instance: `ConcreteQueryHolds`, with
    104the finite sets in place of lists. -/
    105def ConcreteCQHolds : CQInstance → Prop
    106 | ⟨n, m, q, D⟩ => ∃ v : Fin n → Fin (m + 1),
    107 ∀ p ∈ q, (Sum.elim v id p.1, Sum.elim v id p.2) ∈ D
    108
    109open FirstOrder
    110
    111open Language Structure BoundedFormula
    112
    113/-- The encoder itself, standalone rather than inline in the bundle, so that
    114it can be audited in isolation: it elaborates as a plain `def` – an encoder
    115deciding an undecidable predicate could not, the compiler would demand
    116`noncomputable` – and it genuinely runs (the `#guard`s below). Its
    117`#print axioms` still cites the classical axioms, harmlessly: `Finset`
    118membership is decided through `Multiset` quotients, whose instances cite them
    119in *proof* positions only – executability is witnessed by execution, not by
    120the axiom report. -/
    121def cqRelBool (i : CQInstance) {n : ℕ} (R : queryDb.Relations n) :
    122 (Fin n → (Fin i.vars ⊕ Fin (i.consts + 1))) → Bool :=
    123 match n, R with
    124 | _, .isVar => fun x => (x 0).isLeft
    125 | _, .atom => fun x => decide ((x 0, x 1) ∈ i.atoms)
    126 | _, .fact => fun x =>
    127 match x 0, x 1 with
    128 | Sum.inr a, Sum.inr b => decide ((a, b) ∈ i.facts)
    129 | _, _ => false
    130
    131/-- The structure a packaged instance encodes: variables and constants as
    132universe, the relations the encoder's computations read as propositions. -/
    133instance cqStructure (i : CQInstance) :
    134 queryDb.Structure (Fin i.vars ⊕ Fin (i.consts + 1)) where
    135 funMap f := isEmptyElim f
    136 RelMap R x := cqRelBool i R x = true
    137
    138section Concrete
    139
    140variable {V C : Type}
    141
    142/-- The `Language.queryDb`-structure encoding a concrete instance: universe
    143`V ⊕ C`, the variables being the left summands, with the atoms of `q` and
    144the facts of `D`. -/
    145@[reducible]
    146def queryDbStructure (q : List ((V ⊕ C) × (V ⊕ C))) (D : List (C × C)) :
    147 queryDb.Structure (V ⊕ C) where
    148 funMap f := isEmptyElim f
    149 RelMap {n} R :=
    150 match n, R with
    151 | _, .isVar => fun x =>
    152 match x 0 with
    153 | Sum.inl _ => True
    154 | Sum.inr _ => False
    155 | _, .atom => fun x => (x 0, x 1) ∈ q
    156 | _, .fact => fun x =>
    157 match x 0, x 1 with
    158 | Sum.inr a, Sum.inr b => (a, b) ∈ D
    159 | _, _ => False
    160
    161end Concrete
    162
    163/-- Well-formedness of an evaluation instance: some element is a constant.
    164The one condition the decoder needs. -/
    165noncomputable def cqWFSentence : queryDb.Sentence :=
    166 FirstOrder.Language.Formula.iExs (Fin 1)
    167 (FirstOrder.Language.BoundedFormula.not
    168 (FirstOrder.Language.Relations.formula₁ qdbIsVar (FirstOrder.Language.Term.var (Sum.inr 0))))
    169
    170section Decoder
    171
    172variable (S : FinPresentation queryDb)
    173
    174/-- The variable elements of a presented instance. -/
    175def cqVars : Finset (Fin S.card) :=
    176 Finset.univ.filter fun x => S.relBool qdbIsVar ![x]
    177
    178/-- The constant elements of a presented instance. -/
    179def cqConsts : Finset (Fin S.card) :=
    180 Finset.univ.filter fun x => ¬S.relBool qdbIsVar ![x]
    181
    182/-- The elements of a presented instance read back from their numbers:
    183variables in order on the left, constants in order on the right. -/
    184def cqUnnumber {m : ℕ} (h : (cqConsts S).card = m + 1) :
    185 Fin (cqVars S).card ⊕ Fin (m + 1) → Fin S.card :=
    186 Sum.elim (fun a => (((cqVars S).orderIsoOfFin rfl) a : Fin S.card))
    187 fun b => (((cqConsts S).orderIsoOfFin rfl) (Fin.cast h.symm b) : Fin S.card)
    188
    189/-- The decoder: the packaged instance whose variables, constants, atoms and
    190facts are those of the presented structure, read through the numbering, or
    191`none` when the structure has no constant. -/
    192def cqDecode : Option CQInstance :=
    193 match h : (cqConsts S).card with
    194 | 0 => none
    195 | m + 1 => some ⟨(cqVars S).card, m,
    196 Finset.univ.filter fun p => S.relBool qdbAtom
    197 ![cqUnnumber S h p.1, cqUnnumber S h p.2],
    198 Finset.univ.filter fun p => S.relBool qdbFact
    199 ![cqUnnumber S h (Sum.inr p.1), cqUnnumber S h (Sum.inr p.2)]⟩
    200
    201end Decoder
    202
    203open Lax904597.Problems Lax799700.Problems Lax420092.Evaluation
    204
    205/-- Evaluation on well-formed instances: those with at least one constant,
    206the ones the decoder handles. -/
    207def WFCQEval : DecisionProblem queryDb :=
    208 DecisionProblem.ofPred fun (A : Type) [queryDb.Structure A] =>
    209 A ⊨ cqWFSentence ∧ QueryHolds A
    210
    211end Lax420092.PackagedInstances
    212

    Discussion

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

    Loading discussion…