2026-07-26T05:32:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19798 2024-03-14T08:42:35Z ddc:004 open_access

Optimally Rewriting Formulas and Database Queries: A Confluence of Term Rewriting, Structural Decomposition, and Complexity Chen, Hubie Mengel, Stefan width query rewriting structural decomposition term rewriting A central computational task in database theory, finite model theory, and computer science at large is the evaluation of a first-order sentence on a finite structure. In the context of this task, the width of a sentence, defined as the maximum number of free variables over all subformulas, has been established as a crucial measure, where minimizing width of a sentence (while retaining logical equivalence) is considered highly desirable. An undecidability result rules out the possibility of an algorithm that, given a first-order sentence, returns a logically equivalent sentence of minimum width; this result motivates the study of width minimization via syntactic rewriting rules, which is this article’s focus. For a number of common rewriting rules (which are known to preserve logical equivalence), including rules that allow for the movement of quantifiers, we present an algorithm that, given a positive first-order sentence ϕ, outputs the minimum-width sentence obtainable from ϕ via application of these rules. We thus obtain a complete algorithmic understanding of width minimization up to the studied rules; this result is the first one - of which we are aware - that establishes this type of understanding in such a general setting. Our result builds on the theory of term rewriting and establishes an interface among this theory, query evaluation, and structural decomposition theory. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hubie Chen and Stefan Mengel 2024 Is Part Of LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2024.16 urn:nbn:de:0030-drops-197984 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.16 eng https://creativecommons.org/licenses/by/4.0/legalcode