Approximate Schemas, Source-Consistency and Query Answering

We use the Edit distance with Moves on words and trees and say that two regular (tree) languages are ε-close if every word (tree) of one language is ε-close to the other. A transducer model is introduced to compare tree languages (schemas) with different alphabets and attributes. Using the statistical embedding of [8], we show that Source-Consistency and Approximate Query Answering are testable on words and trees, i.e. can be approximately decided within ε by only looking at a constant fraction of the input.