Testing logically defined properties on relational databases of bounded degree

29^th November 2017, 13:00 Ashton Lecture Theater
Dr. Isolde Adler
School of Computing
University of Leeds

Abstract

Property testing (for a property P) asks for a given input, whether it has property P, or is "far" from having that property. A "testing algorithm" is a probabilistic algorithm that answers this question with high probability correctly, by only looking at small parts of the input. Testing algorithms are thought of as "extremely efficient", making them relevant in the context of big data.

We extend the bounded degree model of property testing from graphs to relational databases, and we show that in this model, every property definable in monadic second-order logic is testable with a constant number of queries in polylogarithmic time on databases of bounded tree-width.

This is joint work with Frederik Harwath.