Rule Rewriting Revisited: A Fresh Look at Static Filtering for Datalog and ASP

Philipp HanischPhilipp Hanisch, Markus KrötzschMarkus Krötzsch

Philipp Hanisch, Markus Krötzsch
Rule Rewriting Revisited: A Fresh Look at Static Filtering for Datalog and ASP
In Balder ten Cate, Maurice Funk, eds., Proceedings of the 29th International Conference on Database Theory, volume 365 of LIPIcs, to appear. Dagstuhl Publishing

Details
Bibtex

KurzfassungAbstract
Static filtering is a data-independent optimisation method for Datalog, which generalises algebraic query rewriting techniques from relational databases. In spite of its early discovery by Kifer and Lozinskii in 1986, the method has been overlooked in recent research and system development, and special cases are being rediscovered independently. We therefore recall the original approach, using updated terminology and more general filter predicates that capture features of modern systems, and we show how to extend its applicability to answer set programming (ASP). The outcome is strictly more general but also more complex than the classical approach: double exponential in general and single exponential even for predicates of bounded arity. As a solution, we propose tractable approximations of the algorithm that can still yield much improved logic programs in typical cases, e.g., it can improve the performance of rule systems over real-world data in the order of magnitude.
Weitere Informationen unter:Further Information: Link
Projekt:Project: CPEC, CeTI, SECAI, ScaDS.AI
Verknüpfte Tools:Related Tools: Nemo
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{HK2026,
  author    = {Philipp Hanisch and Markus Kr{\"{o}}tzsch},
  title     = {Rule Rewriting Revisited: A Fresh Look at Static Filtering for
               Datalog and {ASP}},
  editor    = {Balder ten Cate and Maurice Funk},
  booktitle = {Proceedings of the 29th International Conference on Database
               Theory},
  series    = {LIPIcs},
  volume    = {365},
  publisher = {Dagstuhl Publishing},
  year      = {2026},
  doi       = {10.4230/LIPIcs.ICDT.2026.5}
}