2026-07-21T19:27:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8528 2024-03-06T10:42:15Z ddc:004 open_access

Property Testing for Bounded Degree Databases Adler, Isolde Harwath, Frederik logic and databases property testing logical meta-theorems bounded degree model sublinear algorithms Aiming at extremely efficient algorithms for big data sets, we introduce property testing of relational databases of bounded degree. Our model generalises the bounded degree model for graphs (Goldreich and Ron, STOC 1997). We prove that in this model, if the databases have bounded tree-width, then every query definable in monadic second-order logic with modulo counting is testable with a constant number of oracle queries and polylogarithmic running time. This is the first logical meta-theorem in property testing of sparse models. Furthermore, we discuss conditions for the existence of uniform and non-uniform testers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Isolde Adler and Frederik Harwath 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.6 urn:nbn:de:0030-drops-85288 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.6 eng https://creativecommons.org/licenses/by/3.0/legalcode