Convergence of Datalog over (Pre-)Semirings

• PDF
• Authors
  • Mahmoud Abo Khamis
  • Hung Q. Ngo
  • Reinhard Pichler
  • Dan Suciu
  • Yisu Remy Wang

Notes

• Explores Datalog convergence over an arbitrary semiring
• Define a variant called ${\text{Datalog}}^o$ (“datalogo”)
  • Combines datalog with tensor ops
    • Makes it a good candidate for ML and optimisation problems
  • Datalog is a union over conjunctive queries
  • ${\text{Datalog}}^o$ does (sum-)sum-product queries on (pre-)semirings
    • Can perform e.g. gradient descent
• Instead of requiring that a Datalog be over partial orders, they use semirings
  • Some semirings are not partially ordered
  • They give the example $(\mathbb{R},+,\times ,0,1)$
  • So, the authors define a partially-ordered pre-semiring
    • They call this “POPS”
  • Requires that $\oplus$ and $\otimes$ are monotone
  • They also define a $\ominus$ operator that acts like set difference