Fast Left Kan Extensions Using The Chase
From MaRDI portal
Logic in computer science (03B70) Applications of model theory (03C98) Categorical logic, topoi (03G30) Computational methods for problems pertaining to category theory (18-08) Adjoint functors (universal constructions, reflective subcategories, Kan extensions, etc.) (18A40) Theories (e.g., algebraic theories), structure, and semantics (18C10) Database theory (68P15)
Abstract: We show how computation of left Kan extensions can be reduced to computation of free models of cartesian (finite-limit) theories. We discuss how the standard and parallel chase compute weakly free models of regular theories and free models of cartesian theories, and compare the concept of "free model" with a similar concept from database theory known as "universal model". We prove that, as algorithms for computing finite free models of cartesian theories, the standard and parallel chase are complete under fairness assumptions. Finally, we describe an optimized implementation of the parallel chase specialized to left Kan extensions that achieves an order of magnitude improvement in our performance benchmarks compared to the next fastest left Kan extension algorithm we are aware of.
This page was built for publication: Fast Left Kan Extensions Using The Chase
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6398307)
