基于示例编程的层次模型到关系模型的数据转换

将多个数据源中的数据结合起来并统一存储，建立数据仓库的过程是web数据集成中的一个重要步骤。数据集成通过数据转换从而达到集成，主要解决数据的分布性和异构性的问题。许多应用程序使用层次结构存储和传输数据，这种基于树结构的层次模型非常适合底层数据，因此分层数据格式很流行用于导出数据并在不同应用程序之间传输数据。为了便于存储和查询通常需要将此类层次结构数据转换为关系表示，但由于层次结构数据和关系结构数据的特点以及需要处理的数据源可能很大，给这一转换过程带来了不少的工作量。为了解决这个问题，本文采用了一种基于示例编程的方法，用于将层次结构的文档迁移到关系格式。通过提出一种程序合成算法将合成关系表的任务分解为列提取和行提取这两个子任务，从输入输出示例学习目标转换，实现XML文档或JSON文档转换为关系表。实验结果表明，本文的方法可以为从层次结构数据到关系数据的转换任务生成所需的程序，实现数据集中的数据转换。

许多应用程序使用层次结构格式(例如XML 或JSON 文档)存储和传输数据。这种层次结构的数据模型非常适合本质上是分层的底层数据。

此外， 由于XML 和JSON 文档不仅包含数据还包含描述数据属性信息的元数据，因此，这类文档具有自我描述性和可移植性，很大程度提高了以不同的操作系统去使用相同数据集或文件的可能性。由于这些原因，分层的数据格式很流行用于导出数据并在不同应用程序之间传输它们。

尽管分层数据模型很方便，但仍有许多情况需要将它们转换为关系格式。例如，存储在XML 文档中的数据可能需要由与关系数据库交互的现有应用程序进行查询。此外，因为分层数据模型通常不太适合高效的数据查询，当查询性能很重要时，将分层数据格式转换为关系格式是很有必要的。但在转换过程中，存在以下问题： 1) 由于源数据和目标数据的表示完全不同，所需的转换通常比结构相似的数据之间的转换更复杂。

2) 由于目标表中的每一行都对应着输入层次结构树中节点之间的关系，所以合成关系表过程中需要发现树节点之间的这些“隐藏链接”。

因此，本文采用了一种基于示例编程的方法，由一组简单的输入输出示例说明所需要的转换，这种方法通过学习生成所需任务的转换程序， 并可在尽可能少的用户操作下实现将XML 文档或JSON 文档转换为关系数据表。

本文提出一种程序合成算法来解决层次结构数据向关系结构数据转换过程中存在的问题，该算法将层次结构数据转换成关系表的任务分解为两个子问题，列学习和行学习。目的是分别学习列和行的构造逻辑：