TCS-TR-B-09-6Date: Tue Apr 28 17:31:42 2009 Title: Master's Thesis: The Classification Problem in Relational Property Testing Authors: Charles Harold Jordan Contact:
Abstract. In property testing, we desire to distinguish between objects that have a given property and objects that are far from the property by examining only a small, randomly selected portion of the objects. Property testing arose in the study of formal verification, however much of the recent work has been focused on testing graph properties. In this thesis we introduce a generalization of property testing which we call relational property testing. Because property testers examine only a very small portion of their "inputs," there are potential applications to efficiently testing properties of massive structures. Relational databases provide perhaps the most obvious example of such massive structures, and our framework is a natural way to characterize this problem. We introduce a number of variations of our generalization and prove the relationships between them. The second major topic of this thesis is the classification problem for testability. Using the general framework developed in previous chapters, we consider the testability of various syntactic fragments of first-order logic. This problem is inspired by the classical problem for decidability. We compare the current classification for testability with early results in the classification for testability, and then prove an additional class to be testable. ©Copyright 2009 Authors |