Rule Rewriting Revisited: A Fresh Look at Static Filtering for Datalog and ASP
Philipp Hanisch, Markus Krötzsch · 2026
Read Rule Rewriting Revisited: A Fresh Look at Static Filtering for Datalog and ASP by Philipp Hanisch, Markus Krötzsch (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-05108.txt.
Introduction
Philipp Hanisch and Markus Krötzsch dust off an old trick for fast rule-based queries in a 2026 paper. The trick, called static filtering, trims a Datalog query ere any data are seen. Datalog is a tongue for rules over facts, used in stores of facts and in code checks. The trick dates back to 1986, yet fresh work has passed it by. Parts of it keep being found a new, in weaker forms, by teams who do not know the old work.
The authors restate the old approach in modern terminology and generalize its filter predicates to capture features of current systems. They also extend the method to answer set programming, strictly widening its reach. Recovering a forgotten, more general technique can save implementers from reinventing partial versions, and it speeds rule engines used in knowledge bases and program analysis.
Catalog record
| CREATOR | Philipp Hanisch, Markus Krötzsch |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 101 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-05108
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Rule Rewriting Revisited: A Fresh Look at Static Filtering for Datalog and ASP Philipp Hanisch, Markus Krötzsch Abstract 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. Knowledge-Based Systems Group, TU [email protected]://orcid.org/0000-0003-3115-7492 Knowledge-Based Systems Group, TU [email protected]://orcid.org/0000-0002-9172-2601 This work is partly supported by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) in project number 389792660 (TRR 248, Center for Perspicuous Systems ) and 390696704 (CeTI Cluster of Excellence) and by the Bundesministerium für Forschung, Technologie und Raumfahrt (BMFTR, Federal Ministry of Research, Technology and Space) in the Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI) and in DAAD project 57616814 ( SECAI, School of Embedded Composite AI ) as part of the program Konrad Zuse Schools of Excellence in Artificial Intelligence. ccs Theory of computation Logic and databases ccs Theory of computation Constraint and logic programming ccs Theory of computation Equational logic and rewriting keywords Rule rewriting, static optimisation, static filtering, Datalog, Answer Set Programming † † runningauthor: P. Hanisch and M. Krötzsch † † copyright: Philipp Hanisch and Markus Krötzsch † † related-version: This paper is the technical report for the paper with the same title appearing in the Proceedings of the 29th International Conference on Database Theory (ICDT 2026) : https://doi.org/10.4230/LIPIcs.ICDT.2026.5 † † editors: Balder ten Cate and Maurice Funk † † event-title: 29th International Conference on Database Theory (ICDT 2026) † † event-shorttitle: ICDT 2026 † † event-acronym: ICDT † † year: 2026 † † event-date: March 24–27, 2026 † † event-location: Tampere, Finland † † series-volume: 365 † † articleno: 5 1 Introduction Besides its many other advantages, the declarative nature of logic-based rule languages also enables effective optimisation through logically equivalent rewritings. Of course, already for plain Datalog, logical equivalence is undecidable, and highly complex in decidable special cases [ 6 ] . But many concrete transformations that guarantee logical equivalence have been proposed, ranging from the popular magic sets [ 3 , 28 , 29 ] to recent proposals [ 31 , 32 , 35 , 37 ] . Like these examples, many rule rewritings are static optimisations, which do not depend on the concrete set of facts (data) that is to be processed. One of the classical proposals of this kind is static filtering , the generalisation of selection pushing methods from relational databases to Datalog, introduced by Kifer and Lozinskii [ 22 , 23 , 24 ] . The underlying principle of enforcing restrictions (“filters”) on intermediate results as early as possible in the computation is a tried and tested paradigm in databases, and does – in contrast to, e.g., magic sets – not change the general structure of derivations fundamentally. Moreover, static filtering strongly increases the effectivity of the related method of projection pushing [ 24 ] . Static filtering can enable polynomial (data complexity) or exponential (combined complexity) performance improvements (see Examples 1 and 23 ). Surprisingly, the journal paper of Kifer and Lozinskii has attracted less than 50 citations in the past 35 years. 1 1 1 Google Scholar, https://scholar.google.com/scholar?cites=13499523163799224695 , retrieved 8 September 2025 Actual uses of the method are rarely reported [ 5 , 11 , 26 ] , while most mentions consider it distantly related work. Is this basic optimisation approach maybe so fundamental that it is not even mentioned by implementers? Or is it known and used under another name? Example 1 . We ran a small experiment to find out, using the following Datalog rules (see Section 2 for a formal introduction to Datalog, and the literature for more details [ 25 , 27 ] ): \displaystyle p(0,\ldots,0,0,\mathtt{a}). \displaystyle\qquad p(1,\ldots,1,0,\mathtt{b}). (1) \displaystyle p(x_{1},\ldots,x_{i},1,0,\ldots,0,y) \displaystyle\textstyle\leftarrow p(x_{1},\ldots,x_{i},0,1,\ldots,1,y)\hskip 22.76228pt\text{for all $i\in\{1,\ldots,\ell\}$} (2) \displaystyle\textit{out}(y) \displaystyle\leftarrow p(x_{1},\ldots,x_{\ell},y)\wedge y\mathrel{\overset{\cdot}{=}}\mathtt{b} (3) where p is an (\ell+1) -ary predicate with \ell\geq 1 , \mathrel{\overset{\cdot}{=}} denotes equality, y and x_{k} are variables, and 0 , 1 , \mathtt{a} , and \mathtt{b} are constants. Rules ( 2 ) implement a binary counter over \ell bits, so exponentially many p -facts are inferred from the facts ( 1 ). Optimisation is possible if we are only interested in inferences for predicate out : then the precondition y\mathrel{\overset{\cdot}{=}}\mathtt{b} can be added to the rules ( 2 ), so that just one new p -fact follows. Static filtering produces this rewriting. Table 1 : Runtimes for example program ( 1 )–( 3 ) with \ell=19 (median of five runs, timeout at 5min, evaluation system: Linux, AMD Ryzen 7 PRO 5850U, 16 GiB RAM) Soufflé v2.5 Nemo v0.8.1 Clingo v5.8.0 DLV v2.1.2 Original 1214ms > 5min 1104ms 74579ms Rewritten 24ms 99ms 8ms 3ms Many modern rule systems let users specify output predicates. For our experiment, we considered Datalog engines Soufflé [ 20 ] (syntax .output out ) and Nemo [ 18 ] (syntax @export out :- csv{}. ), and ASP engines Clingo [ 13 ] and DLV [ 2 ] (syntax #show out/1. for both). Table 1 shows runtimes for the original program and the optimised version. Evidently, each tool benefits from the optimisation, yet none implements it by default. Why is such a natural optimisation, considered standard in relational query optimisation, ignored in modern rule systems? Research culture may be a reason. Typical benchmarks for comparing systems are already optimised, so static optimisations offer no benefits. They are likely more effective with less polished user inputs, especially during development and experimentation. Moreover, static filtering has not attained the popularity of other approaches, especially magic sets and semi-naive evaluation, and may not be known to many implementers. The original description relies on system graphs as an auxiliary concept that many readers may not know today, yet we are not aware of modern accounts or textbook explanations of the method. Another reason might be practicality. Kifer and Lozinskii found the method to be exponential in the worst case – as hard as the Datalog reasoning task it aims to optimise – and did not suggest tractable variants. It is also left open how static filtering generalises to further filter expressions (Kifer and Lozinskii only consider binary relations like = , \neq , and \leq ), and to non-monotonic negation or ASP. In this work, we therefore revisit static filtering and introduce a generalised rewriting that supports arbitrary filters (Section 3 ). Analysing the complexity of our method (Section 4 ), we find further exponential increases over the prior special case, which motivates our design of a tractable variant that is still reasonably general