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 \textsf{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
  • \textsf{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