Comment by bubblyworld
11 hours ago
Very interesting perspective I hadn't heard before on datalog, thanks. How far does it go - can you interpret extensions of datalog (say negation or constrained existentials) in a nice categorical way, for instance? I've given this very little thought but I imagine you'd have issues with uniqueness of these "minimal" database instances, and I'm not sure what that means for these lifting properties.
(if my question even makes sense, pardon the ignorance)
If you're interested in the details, you might want to have a look at papers [1] or [2].
You can add existentials in this framework, which basically means that the lifting problems mentioned above don't need to have unique solutions. But as you say, then the "minimal" databases aren't determined uniquely up to isomorphism anymore. So the result of Datalog evaluation now depends on the order in which you apply rules.
If I recall correctly, then [3] discusses a logic corresponding to accessible categories (Datalog + equality corresponds to locally presentable categories) which includes the the theory of fields. The theory of fields involves the negation 0 != 1, so perhaps that might give you a nicer way to incorporate negations without stratification.
[1] https://www.mbid.me/eqlog-semantics/
[2] https://arxiv.org/abs/2205.02425
[3] Locally presentable and accessible categories, https://www.cambridge.org/core/books/locally-presentable-and...