Title: Extracting Syntactic Patterns from Databases,
Abstract: Many database columns contain string or numerical data that conforms to a
pattern, such as phone numbers, dates, addresses, product identifiers, and
employee ids. These patterns are useful in a number of data processing
applications, including understanding what a specific field represents when
field names are ambiguous, identifying outlier values, and finding similar
fields across data sets. One way to express such patterns would be to learn
regular expressions for each field in the database. Unfortunately, exist- ing
techniques on regular expression learning are slow, taking hundreds of seconds
for columns of just a few thousand values. In contrast, we develop XSystem, an
efficient method to learn patterns over database columns in significantly less
time. We show that these patterns can not only be built quickly, but are
expressive enough to capture a number of key applications, including detecting
outliers, measuring column similarity, and assigning semantic labels to columns
(based on a library of regular expressions). We evaluate these applications
with datasets that range from chemical databases (based on a collaboration with
a pharmaceutical company), our university data warehouse, and open data from
MassData.gov.