Annotated relations and databases
Lax392996.AnnotatedDatabases · concepts/Lax392996/AnnotatedDatabases.lean · lax-392996
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
For an m-semiring , a -relation of arity is a finite multiset of -tuples each carrying an annotation in , and a -instance maps each relation name, at its arity, to a -relation: the two claims record that the definitions are these ones. An annotated tuple of arity also reads as a plain tuple of arity over , its annotation in the last column, which extends to relations and instances, and a composite tuple reads back as an annotated one; this composite reading is what the rewriting of the paper targets. For it, is made a value type, with data values below annotations and the annotations compared through the alternative linear order of .
Concept map
Evidence
In the paper
- page 3 of this submission's paper
Lean source view on GitHub
| 1 | import Mathlib.Data.Prod.Lex |
| 2 | import Mathlib.Data.Fin.Tuple.Basic |
| 3 | import Mathlib.Data.Fin.VecNotation |
| 4 | import Mathlib.Data.Multiset.Basic |
| 5 | import Lax392996.Databases |
| 6 | import Lax392996.SemiringsWithMonus |
| 7 | |
| 8 | /-! |
| 9 | --- |
| 10 | title: Annotated relations and databases |
| 11 | type: definition |
| 12 | --- |
| 13 | For an m-semiring , a -relation of arity is a |
| 14 | finite multiset of -tuples each carrying an annotation in , |
| 15 | and a -instance maps each relation name, at its arity, to a |
| 16 | -relation: the two claims record that the definitions are these |
| 17 | ones. An annotated tuple of arity also reads as a plain tuple of arity |
| 18 | over , its annotation in the last |
| 19 | column, which extends to relations and instances, and a composite tuple |
| 20 | reads back as an annotated one; this composite reading is what the |
| 21 | rewriting of the paper targets. For it, |
| 22 | is made a value type, with data values below annotations and |
| 23 | the annotations compared through the alternative linear order of |
| 24 | . |
| 25 | -/ |
| 26 | |
| 27 | namespace Lax392996.AnnotatedDatabases |
| 28 | |
| 29 | open Lax392996.Databases Lax392996.SemiringsWithMonus |
| 30 | |
| 31 | universe u |
| 32 | |
| 33 | variable {T : Type} [ValueType T] {K : Type} [Zero K] {n : ℕ} |
| 34 | |
| 35 | /-- An annotated tuple: a tuple paired with an annotation, ordered |
| 36 | lexicographically. -/ |
| 37 | abbrev AnnotatedTuple (T : Type) (K : Type u) (n: ℕ) := Tuple T n ×ₗ K |
| 38 | |
| 39 | /-- A `K`-relation of arity `arity`: a finite multiset of annotated tuples. -/ |
| 40 | def AnnotatedRelation (T : Type) (K : Type u) (arity: ℕ) := Multiset (AnnotatedTuple T K arity) |
| 41 | |
| 42 | instance instAddAnnotatedRelation {arity : ℕ} : Add (AnnotatedRelation T K arity) := by |
| 43 | show Add (Multiset (AnnotatedTuple T K arity)) |
| 44 | infer_instance |
| 45 | |
| 46 | /-- A `K`-instance: a list of named annotated relations, each with its arity. -/ |
| 47 | def AnnotatedDatabase (T : Type) (K : Type u) := List (String × Σ n, AnnotatedRelation T K n) |
| 48 | |
| 49 | /-- The annotated relation named `s` of arity `n` in a `K`-instance, if any. -/ |
| 50 | def AnnotatedDatabase.find (n: ℕ) (s: String) (d: AnnotatedDatabase T K) : |
| 51 | Option (AnnotatedRelation T K n) := |
| 52 | let rec f |
| 53 | | [] => none |
| 54 | | (s',rn)::tl => if h: n = rn.fst ∧ s =s' then some (Eq.mp (by rw[h.left]) rn.snd) else f tl |
| 55 | f d |
| 56 | |
| 57 | /-- The composite reading of an annotated tuple: the annotation becomes a |
| 58 | last column over `T ⊕ K`. -/ |
| 59 | def AnnotatedTuple.toComposite (p: AnnotatedTuple T K n) := |
| 60 | Fin.append (λ k: Fin n ↦ Sum.inl (p.fst k)) ![Sum.inr p.snd] |
| 61 | |
| 62 | /-- The annotated tuple a composite tuple reads as: the data values from |
| 63 | its first `n` columns, the annotation from its last one. -/ |
| 64 | def Tuple.fromComposite (t: Tuple (T⊕K) (n+1)) : AnnotatedTuple T K n := |
| 65 | ( |
| 66 | λ (k: Fin n) ↦ match t (k.castLE (by simp)) with | Sum.inl x => x | Sum.inr _ => 0, |
| 67 | match t (Fin.last n) with | Sum.inl _ => 0 | Sum.inr x => x |
| 68 | ) |
| 69 | |
| 70 | /-- The composite reading of an annotated relation. -/ |
| 71 | def AnnotatedRelation.toComposite (ar: AnnotatedRelation T K n): |
| 72 | Relation (T⊕K) (n+1) := |
| 73 | ar.map λ p ↦ p.toComposite |
| 74 | |
| 75 | /-- The composite reading of a `K`-instance: a plain database over `T ⊕ K`. -/ |
| 76 | def AnnotatedDatabase.toComposite (d: AnnotatedDatabase T K): Database (T⊕K) := |
| 77 | d.map λ (s, ⟨n',r⟩) ↦ (s, ⟨n'+1,r.toComposite⟩) |
| 78 | |
| 79 | /-- `V ⊕ K` is a value type: data values are below annotations, and |
| 80 | annotations are compared through the alternative linear order of `K`. -/ |
| 81 | instance instValueTypeSumOfHasAltLinearOrderOfSemiringWithMonus {V K : Type} |
| 82 | [ValueType V] [HasAltLinearOrder K] [SemiringWithMonus K] : ValueType (V⊕K) where |
| 83 | zero := Sum.inr 0 |
| 84 | |
| 85 | add a b := match a,b with |
| 86 | | Sum.inl a', Sum.inl b' => Sum.inl (a'+b') |
| 87 | | Sum.inr a', Sum.inr b' => Sum.inr (a'+b') |
| 88 | | Sum.inl a', Sum.inr b' => Sum.inl (a') |
| 89 | | Sum.inr a', Sum.inl b' => Sum.inl (b') |
| 90 | |
| 91 | sub a b := match a,b with |
| 92 | | Sum.inl a', Sum.inl b' => Sum.inl (a'-b') |
| 93 | | Sum.inr a', Sum.inr b' => Sum.inr (a'-b') |
| 94 | | Sum.inl a', Sum.inr b' => Sum.inl (a') |
| 95 | | Sum.inr a', Sum.inl b' => Sum.inl (b') |
| 96 | |
| 97 | mul a b := match a,b with |
| 98 | | Sum.inl a', Sum.inl b' => Sum.inl (a'*b') |
| 99 | | Sum.inr a', Sum.inr b' => Sum.inr (a'*b') |
| 100 | | Sum.inl a', Sum.inr b' => Sum.inl (a') |
| 101 | | Sum.inr a', Sum.inl b' => Sum.inl (b') |
| 102 | |
| 103 | add_assoc a b c := by |
| 104 | cases a <;> cases b <;> cases c <;> simp[(· + ·)] <;> exact add_assoc _ _ _ |
| 105 | |
| 106 | add_comm a b := by |
| 107 | cases a <;> cases b <;> simp[(· + ·)] <;> exact add_comm _ _ |
| 108 | |
| 109 | le a b := match a,b with |
| 110 | | Sum.inl a', Sum.inl b' => a'≤b' |
| 111 | | Sum.inr a', Sum.inr b' => HasAltLinearOrder.altOrder.le a' b' |
| 112 | | Sum.inl a', Sum.inr b' => True |
| 113 | | Sum.inr a', Sum.inl b' => False |
| 114 | |
| 115 | le_refl a := by |
| 116 | cases a <;> simp |
| 117 | |
| 118 | le_antisymm a b := by |
| 119 | cases a <;> cases b <;> simp |
| 120 | . exact le_antisymm |
| 121 | . exact HasAltLinearOrder.altOrder.le_antisymm _ _ |
| 122 | |
| 123 | le_trans a b c := by |
| 124 | cases a <;> cases b <;> cases c <;> simp |
| 125 | . exact le_trans |
| 126 | . exact HasAltLinearOrder.altOrder.le_trans _ _ _ |
| 127 | |
| 128 | le_total a b := by |
| 129 | cases a <;> cases b <;> simp |
| 130 | . exact le_total _ _ |
| 131 | . next x y => |
| 132 | exact HasAltLinearOrder.altOrder.le_total x y |
| 133 | |
| 134 | toDecidableLE := |
| 135 | λ a b ↦ match a, b with |
| 136 | | Sum.inl a', Sum.inl b' => inferInstance |
| 137 | | Sum.inr a', Sum.inr b' => inferInstance |
| 138 | | Sum.inl a', Sum.inr b' => isTrue (trivial) |
| 139 | | Sum.inr a', Sum.inl b' => isFalse (id) |
| 140 | |
| 141 | /-- A `K`-relation of arity `n` is a multiset of `n`-tuples paired with an |
| 142 | annotation. -/ |
| 143 | axiom annotated_relation_eq : AnnotatedRelation T K n = Multiset (Tuple T n ×ₗ K) |
| 144 | |
| 145 | /-- A `K`-instance answers a relation name, at an arity, with a `K`-relation. -/ |
| 146 | axiom annotated_database_lookup : |
| 147 | ∀ (R : String) (d : AnnotatedDatabase T K), |
| 148 | (AnnotatedDatabase.find n R d : Option (AnnotatedRelation T K n)) = d.find n R |
| 149 | |
| 150 | end Lax392996.AnnotatedDatabases |
| 151 |
Used by
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments