2026-07-27T16:27:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22970 2025-10-02T12:19:55Z ddc:004 open_access

FC-Datalog as a Framework for Efficient String Querying Bell, Owen M. Day, Joel D. Freydenberger, Dominik D. Information extraction word equations datalog document spanners regex Core spanners are a class of document spanners that capture the core functionality of IBM’s AQL. FC is a logic on strings built around word equations that when extended with constraints for regular languages can be seen as a logic for core spanners. The recently introduced FC-Datalog extends FC with recursion, which allows us to define recursive relations for core spanners. Additionally, as FC-Datalog captures 𝖯, it is also a tractable version of Datalog on strings. This presents an opportunity for optimization. We propose a series of FC-Datalog fragments with desirable properties in terms of complexity of model checking, expressive power, and efficiency of checking membership in the fragment. This leads to a range of fragments that all capture LOGSPACE, which we further restrict to obtain linear combined complexity. This gives us a framework to tailor fragments for particular applications. To showcase this, we simulate deterministic regex in a tailored fragment of FC-Datalog. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Owen M. Bell and Joel D. Day and Dominik D. Freydenberger 2025 Is Part Of LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2025.29 urn:nbn:de:0030-drops-229708 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.29 eng https://creativecommons.org/licenses/by/4.0/legalcode