Packaged evaluation instances, their encoding and decoding
Lax420092.PackagedInstances · concepts/Lax420092/PackagedInstances.lean · lax-420092
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural 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
Lean source view on GitHub
| 1 | import Mathlib.SetTheory.Cardinal.Finite |
| 2 | import Mathlib.ModelTheory.Semantics |
| 3 | import Mathlib.ModelTheory.Complexity |
| 4 | import Mathlib.Tactic.FinCases |
| 5 | import Mathlib.ModelTheory.Order |
| 6 | import Mathlib.Data.Fintype.Lattice |
| 7 | import Mathlib.Data.Set.Finite.Lemmas |
| 8 | import Mathlib.Order.PiLex |
| 9 | import Mathlib.Data.Prod.Lex |
| 10 | import Mathlib.Data.Fintype.EquivFin |
| 11 | import Mathlib.Logic.Equiv.Fin.Basic |
| 12 | import Mathlib.Data.Finite.Sigma |
| 13 | import Mathlib.ModelTheory.Syntax |
| 14 | import Mathlib.ModelTheory.Graph |
| 15 | import Mathlib.Combinatorics.SimpleGraph.Coloring.Vertex |
| 16 | import Lax420092.QueryDatabases |
| 17 | import Mathlib.Data.Finset.Sort |
| 18 | import Lax904597.Classes |
| 19 | import Lax799700.Problems |
| 20 | import Lax420092.Evaluation |
| 21 | |
| 22 | /-! |
| 23 | --- |
| 24 | title: Packaged evaluation instances, their encoding and decoding |
| 25 | type: definition |
| 26 | --- |
| 27 | A concrete Boolean conjunctive query over variables and constants is a list |
| 28 | of binary atoms with arguments in their disjoint union, and a concrete graph |
| 29 | database a list of facts over the constants; the query holds in the |
| 30 | database when some assignment of the variables to constants sends every |
| 31 | atom to a fact. A packaged instance fixes the numbers of variables and of |
| 32 | constants, at least one constant, with finite sets of atoms and of facts; |
| 33 | its size is the textbook one, elements plus atoms plus facts. The encoder |
| 34 | computes the structure of an instance, on its variables and constants as |
| 35 | universe, and a concrete query and database give a structure on their |
| 36 | disjoint union directly. A presentation is a raw relation table on a finite |
| 37 | universe; an instance is well-formed when some element is a constant, which |
| 38 | a first-order sentence states, and the decoder reads a packaged instance off |
| 39 | a well-formed presented structure by numbering its variables and its |
| 40 | constants in order. Well-formed evaluation is evaluation restricted to |
| 41 | well-formed instances. |
| 42 | -/ |
| 43 | |
| 44 | namespace Lax420092.PackagedInstances |
| 45 | |
| 46 | open Lax420092.QueryDatabases |
| 47 | |
| 48 | open FirstOrder |
| 49 | |
| 50 | open Language Structure |
| 51 | |
| 52 | |
| 53 | /-- A concretely presented finite `L`-structure: a size and a computable |
| 54 | relation table. This is the input type of decoders – the “raw bytes” a |
| 55 | decoding computation reads. -/ |
| 56 | structure 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. -/ |
| 63 | instance 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 | |
| 68 | section Concrete |
| 69 | |
| 70 | variable {V C : Type} |
| 71 | |
| 72 | /-- The textbook semantics of a concrete Boolean conjunctive query `q` (a |
| 73 | list of binary atoms with arguments in `V ⊕ C`: variables to the left, |
| 74 | constants to the right) on a concrete graph database `D` (a list of facts |
| 75 | over the constants): some assignment of the variables to constants sends |
| 76 | every atom to a fact. -/ |
| 77 | def 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 | |
| 80 | end Concrete |
| 81 | |
| 82 | /-- A packaged concrete evaluation instance: `n` query variables, `m + 1` |
| 83 | database constants, a finite set of query atoms over them, and a finite set |
| 84 | of database facts on the constants. -/ |
| 85 | structure 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 |
| 98 | constants) plus atoms plus facts. This is the one audited line of the |
| 99 | encoding – everything else is checked against it. -/ |
| 100 | def 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 |
| 104 | the finite sets in place of lists. -/ |
| 105 | def 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 | |
| 109 | open FirstOrder |
| 110 | |
| 111 | open Language Structure BoundedFormula |
| 112 | |
| 113 | /-- The encoder itself, standalone rather than inline in the bundle, so that |
| 114 | it can be audited in isolation: it elaborates as a plain `def` – an encoder |
| 115 | deciding 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` |
| 118 | membership is decided through `Multiset` quotients, whose instances cite them |
| 119 | in *proof* positions only – executability is witnessed by execution, not by |
| 120 | the axiom report. -/ |
| 121 | def 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 |
| 132 | universe, the relations the encoder's computations read as propositions. -/ |
| 133 | instance 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 | |
| 138 | section Concrete |
| 139 | |
| 140 | variable {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 |
| 144 | the facts of `D`. -/ |
| 145 | @[reducible] |
| 146 | def 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 | |
| 161 | end Concrete |
| 162 | |
| 163 | /-- Well-formedness of an evaluation instance: some element is a constant. |
| 164 | The one condition the decoder needs. -/ |
| 165 | noncomputable 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 | |
| 170 | section Decoder |
| 171 | |
| 172 | variable (S : FinPresentation queryDb) |
| 173 | |
| 174 | /-- The variable elements of a presented instance. -/ |
| 175 | def cqVars : Finset (Fin S.card) := |
| 176 | Finset.univ.filter fun x => S.relBool qdbIsVar ![x] |
| 177 | |
| 178 | /-- The constant elements of a presented instance. -/ |
| 179 | def 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: |
| 183 | variables in order on the left, constants in order on the right. -/ |
| 184 | def 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 |
| 190 | facts are those of the presented structure, read through the numbering, or |
| 191 | `none` when the structure has no constant. -/ |
| 192 | def 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 | |
| 201 | end Decoder |
| 202 | |
| 203 | open Lax904597.Problems Lax799700.Problems Lax420092.Evaluation |
| 204 | |
| 205 | /-- Evaluation on well-formed instances: those with at least one constant, |
| 206 | the ones the decoder handles. -/ |
| 207 | def WFCQEval : DecisionProblem queryDb := |
| 208 | DecisionProblem.ofPred fun (A : Type) [queryDb.Structure A] => |
| 209 | A ⊨ cqWFSentence ∧ QueryHolds A |
| 210 | |
| 211 | end Lax420092.PackagedInstances |
| 212 |
Used by
From Mathlib
Mathlib.Combinatorics.SimpleGraph.Coloring.VertexMathlib.Data.Finite.SigmaMathlib.Data.Finset.SortMathlib.Data.Fintype.EquivFinMathlib.Data.Fintype.LatticeMathlib.Data.Prod.LexMathlib.Data.Set.Finite.LemmasMathlib.Logic.Equiv.Fin.BasicMathlib.ModelTheory.ComplexityMathlib.ModelTheory.GraphMathlib.ModelTheory.OrderMathlib.ModelTheory.SemanticsMathlib.ModelTheory.SyntaxMathlib.Order.PiLexMathlib.SetTheory.Cardinal.FiniteMathlib.Tactic.FinCases
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments