While this submission is a draft, it cannot be used by other submissions.

Annotated relations and databases

Lax392996.AnnotatedDatabases · concepts/Lax392996/AnnotatedDatabases.lean · lax-392996

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

    Definition

    For an m-semiring K\mathbb{K}, a K\mathbb{K}-relation of arity kk is a finite multiset of kk-tuples each carrying an annotation in K\mathbb{K}, and a K\mathbb{K}-instance maps each relation name, at its arity, to a K\mathbb{K}-relation: the two claims record that the definitions are these ones. An annotated tuple of arity kk also reads as a plain tuple of arity k+1k+1 over V⊎K\mathcal{V} \uplus \mathbb{K}, 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, V⊎K\mathcal{V} \uplus \mathbb{K} is made a value type, with data values below annotations and the annotations compared through the alternative linear order of K\mathbb{K}.

    Concept map
    3 concepts; 7 descendants hidden
    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 annotated_database_lookup proven

    2 annotated_relation_eq proven

    In the paper

    • page 3 of this submission's paper

    Lean source view on GitHub

    1import Mathlib.Data.Prod.Lex
    2import Mathlib.Data.Fin.Tuple.Basic
    3import Mathlib.Data.Fin.VecNotation
    4import Mathlib.Data.Multiset.Basic
    5import Lax392996.Databases
    6import Lax392996.SemiringsWithMonus
    7
    8/-!
    9---
    10title: Annotated relations and databases
    11type: definition
    12---
    13For an m-semiring K\mathbb{K}, a K\mathbb{K}-relation of arity kk is a
    14finite multiset of kk-tuples each carrying an annotation in K\mathbb{K},
    15and a K\mathbb{K}-instance maps each relation name, at its arity, to a
    16K\mathbb{K}-relation: the two claims record that the definitions are these
    17ones. An annotated tuple of arity kk also reads as a plain tuple of arity
    18k+1k+1 over V⊎K\mathcal{V} \uplus \mathbb{K}, its annotation in the last
    19column, which extends to relations and instances, and a composite tuple
    20reads back as an annotated one; this composite reading is what the
    21rewriting of the paper targets. For it, V⊎K\mathcal{V} \uplus \mathbb{K}
    22 is made a value type, with data values below annotations and
    23the annotations compared through the alternative linear order of
    24K\mathbb{K}.
    25-/
    26
    27namespace Lax392996.AnnotatedDatabases
    28
    29open Lax392996.Databases Lax392996.SemiringsWithMonus
    30
    31universe u
    32
    33variable {T : Type} [ValueType T] {K : Type} [Zero K] {n : ℕ}
    34
    35/-- An annotated tuple: a tuple paired with an annotation, ordered
    36lexicographically. -/
    37abbrev 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. -/
    40def AnnotatedRelation (T : Type) (K : Type u) (arity: ℕ) := Multiset (AnnotatedTuple T K arity)
    41
    42instance 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. -/
    47def 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. -/
    50def 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
    58last column over `T ⊕ K`. -/
    59def 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
    63its first `n` columns, the annotation from its last one. -/
    64def 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. -/
    71def 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`. -/
    76def 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
    80annotations are compared through the alternative linear order of `K`. -/
    81instance 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
    142annotation. -/
    143axiom 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. -/
    146axiom 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
    150end Lax392996.AnnotatedDatabases
    151
    Show ProofShow Proof

    Discussion

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

    Loading discussion…