Document Open Access Logo

Property Testing for Bounded Degree Databases

Authors Isolde Adler, Frederik Harwath

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.6.pdf
  • Filesize: 479 kB
  • 14 pages

Document Identifiers

Author Details

Isolde Adler
Frederik Harwath

Cite As Get BibTex

Isolde Adler and Frederik Harwath. Property Testing for Bounded Degree Databases. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.6

Abstract

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.

Subject Classification

Keywords
  • logic and databases
  • property testing
  • logical meta-theorems
  • bounded degree model
  • sublinear algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Martin Aigner and Eberhard Triesch. Realizability and uniqueness in graphs. Discrete Mathematics, 136(1-3):3-20, 1994. URL: http://dx.doi.org/10.1016/0012-365X(94)00104-Q.
  2. Noga Alon, Michael Krivelevich, Ilan Newman, and Mario Szegedy. Regular languages are testable with a constant number of queries. SIAM J. Comput., 30(6):1842-1862, 2000. URL: http://dx.doi.org/10.1137/S0097539700366528.
  3. Michael A. Bender and Dana Ron. Testing properties of directed graphs: acyclicity and connectivity. Random Struct. Algorithms, 20(2):184-205, 2002. URL: http://dx.doi.org/10.1002/rsa.10023.
  4. Surajit Chaudhuri, Bolin Ding, and Srikanth Kandula. Approximate query processing: No silver bullet. In Semih Salihoglu, Wenchao Zhou, Rada Chirkova, Jun Yang, and Dan Suciu, editors, Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD Conference 2017, Chicago, IL, USA, May 14-19, 2017, pages 511-519. ACM, 2017. URL: http://dx.doi.org/10.1145/3035918.3056097.
  5. Hana Chockler and Orna Kupferman. w-regular languages are testable with a constant number of queries. Theor. Comput. Sci., 329(1-3):71-92, 2004. URL: http://dx.doi.org/10.1016/j.tcs.2004.08.004.
  6. B. Courcelle. Graph rewriting: An algebraic and logic approach. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science (Vol. B), pages 193-242. MIT Press, Cambridge, MA, USA, 1990. URL: http://dl.acm.org/citation.cfm?id=114891.114896.
  7. B. Courcelle and J. Engelfriet. Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Cambridge University Press, New York, NY, USA, 1st edition, 2012. Google Scholar
  8. B. Courcelle and J. Engelfriet. Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Cambridge University Press, New York, NY, USA, 1st edition, 2012. Google Scholar
  9. Artur Czumaj, Pan Peng, and Christian Sohler. Relating two property testing models for bounded degree directed graphs. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 1033-1045. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897575.
  10. H.-D. Ebbinghaus and J. Flum. Finite model theory. Springer, 2005. Google Scholar
  11. Friedrich Eisenbrand. Fast integer programming in fixed dimension. In Giuseppe Di Battista and Uri Zwick, editors, Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings, volume 2832 of Lecture Notes in Computer Science, pages 196-207. Springer, 2003. URL: http://dx.doi.org/10.1007/978-3-540-39658-1_20.
  12. Wenfei Fan, Floris Geerts, and Leonid Libkin. On scale independence for querying big data. In Richard Hull and Martin Grohe, editors, Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS'14, Snowbird, UT, USA, June 22-27, 2014, pages 51-62. ACM, 2014. URL: http://dx.doi.org/10.1145/2594538.2594551.
  13. Eldar Fischer and Johann A. Makowsky. On spectra of sentences of monadic second order logic with counting. J. Symb. Log., 69(3):617-640, 2004. URL: http://dx.doi.org/10.2178/jsl/1096901758.
  14. Oded Goldreich. On promise problems: A survey. In Oded Goldreich, Arnold L. Rosenberg, and Alan L. Selman, editors, Theoretical Computer Science, Essays in Memory of Shimon Even, volume 3895 of Lecture Notes in Computer Science, pages 254-290. Springer, 2006. URL: http://dx.doi.org/10.1007/11685654_12.
  15. Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. Algorithmica, 32(2):302-343, 2002. URL: http://dx.doi.org/10.1007/s00453-001-0078-7.
  16. W. Hanf. The Theory of Models, chapter Model-theoretic methods in the study of elementary logic, pages 132-145. North Holland, 1965. Google Scholar
  17. L. Hella, L. Libkin, and J. Nurmonen. Notions of locality and their logical characterizations over finite models. Journal of Symbolic Logic, 64(4):1751-1773, 1999. Google Scholar
  18. H. W. Lenstra Jr. Integer programming with a fixed number of variables. Mathematics of Operations Research., 8(4):538-548, 1983. Google Scholar
  19. L. Libkin. Elements Of Finite Model Theory (Texts in Theoretical Computer Science. An Eatcs Series). Springer, 2004. Google Scholar
  20. Frédéric Magniez and Michel de Rougemont. Property testing of regular tree languages. Algorithmica, 49(2):127-146, 2007. URL: http://dx.doi.org/10.1007/s00453-007-9028-3.
  21. I. Newman and C. Sohler. Every property of hyperfinite graphs is testable. SIAM Journal on Computing, 42(3):1095-1112, 2013. Conference version published at STOC 2011. Google Scholar
  22. Rohit Parikh. On context-free languages. J. ACM, 13(4):570-581, 1966. URL: http://dx.doi.org/10.1145/321356.321364.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact