ICDE2018-Extracting Syntactic Patterns from Databases

title：Extracting Syntactic Patterns from Databases

标题：从数据库中提取语法模式

摘要-许多数据库列包含符合模式的字符串或数字数据，例如电话号码，日期，地址，产品标识符和员工ID。这些模式在许多数据处理应用程序中很有用，包括了解字段名称不明确时特定字段表示什么，识别异常值以及在数据集中查找相似的字段。

一种表示这种模式的方法是学习数据库中每个字段的正则表达式。不幸的是，现有的技术来学习在常规的表达式上学习很慢，只有几千个值的列就需要花费数百秒的时间。

相比之下，我们开发了XSYSTEM，这是一种高效的方法，可以在很短的时间内学习数据库列上的模式。

我们展示了这些模式不仅可以快速构建，而且具有足够的表现力，可以捕获许多关键应用程序，包括检测异常值，测量列相似性以及为列分配语义标签（基于正则表达式库）。我们使用数据集评估这些应用程序，这些数据集包括化学数据库（基于与制药公司的合作），我们的大学数据仓库以及MassData.gov的开放数据。

介绍：

现代企业将数据存储在各种不同的系统中，包括事务性DBMS，数据仓库，数据湖，电子表格和平面文件。数据分析师经常需要合并来自这些不同数据集的数据，并经常合并来自甚至更多来源的外部数据。在这种情况下的一个关键挑战是找到可以组合起来以回答某些关注问题的相关数据集。

例如，制药公司默克公司的分析师经常需要连接包含化学化合物的表。不幸的是，默克内部至少使用了三种标识符格式（例如，图1所示的InChI，InChIKey和SMILES），更不用说可以在外部数据源中使用的其他格式（举个例子就是：CO2也可以写成OCO或者COO）。由于ID格式的多样性，简单的文本搜索不足以找到相关的表-属性名称不同。实际上，由于这些标识符不具有可比性，因此他们甚至无法执行近似搜索来找到相似的内容。手动在不同格式的标识符之间建立映射并创建查找表是一种昂贵的选择。

更好的选择是使用有用的元数据标记相关属性，例如，将化学标识符标签分配给表中表示的所有标识符列。不幸的是，在拥有大量数据的公司中，手动标记也是不可行的：它需要大量时间，并且容易出错，因为它可能会丢失许多包含相关信息的表，尤其是在考虑外部数据时。

为了解决此问题，我们注意到企业数据库中的许多相关属性都是高度结构化的，即它们遵循简单的语法模式。例如，在图1中，InChi编号始终以模式InChI =开头，并且InChiKey是14个字符，后跟一个连字符，然后是10个字符，后跟另一个连字符和一个附加字符[1]。结构化属性的更常见示例是日期，产品标识符，电话号码，枚举类型（性别等）等。通常，这些列以字符串形式存储在数据库中，但是如果可以用关于值格式，索引，搜索和比较值以及查找异常值或异常值的更丰富的结构信息标记它们，则可以更有效地完成。

在本文中，我们介绍了XSYSTEM，这是一种从数据集中提取语法模式到称为XTRUCTUREs的数据结构的方法。 XTRUCTURE代表语法模式，可以与其他XTRUCTURE和正则表达式进行比较。一旦XSYSTEM学习了模式的集合，分析人员就可以使用它们来执行几个通常执行的任务，包括：自动标签分配，其中通过将数据项与已知类库（写为正则表达式或XTRUCTUREs）进行比较，为数据项分配一个类； 查找语法上相似的内容，比较学习到的XTRUCTURE，以查看它们是否相似，以及异常检测，将单个项目的学习到的XTRUCTURE与其他XTRUCTURE比较，以检查其结构是否不同。这些应用程序有两个共同的要求：（i）XTRUCTURE必须能够快速合成，并且（ii）XTRUCTURE必须彼此可比并且与正则表达式可比。

除了支持这些要求之外，XSYSTEM还必须：i）无需人工干预即可工作，因为半自动或交互式工具都无法扩展大量数据； ii）快速学习句法模式，这需要渐近有效的模型和可并行实现； iii）仅提供原始数据集即可快速合成和处理，因为这是许多分析人员最初可以访问的全部。学习速度对于现实世界的场景至关重要，因为并非所有的数据分析任务都能处理陈旧的数据。

XSYSTEM。我们的方法从示例中逐步学习语法。对于每个示例，它利用已知实体中定界符的存在来将提取模式的问题分解为学习由那些定界符分隔的每个标记的语法。用于学习每个令牌的基础数据结构是一个分支线性分布序列，它等效于确定性非循环有限状态自动机（DAFSA），比起最小确定性有限自动机（DFA）而言，它在渐近性上更容易学习，后者通常用于正则表达式学习中。学习过程依赖于分支和合并策略，该策略使我们能够逐步适应新观察到的实例。这使我们可以捕获出现在同一列中的不同语法结构。这种分支和合并策略也是XSYSTEM中使用的并行化方法的核心。

我们在上面提到的三个应用程序上对XSYSTEM进行了评估，这些应用程序来自我们大学的数据仓库，开放的政府数据和公共化学数据库的真实数据集。

我们发现XSYSTEM可以比给定的DFA学习者更快地形成给定数据的语法表示形式，并且我们可以将其有效地用于目标应用程序。