模式是数据库应用中的一类特定的元数据模型，是实现异构数据和应用系统互操作中不可缺少的基本元素。对于模式，最基本的操作就是匹配，其目的在于获得模式元素之间的对应。模式匹配在许多数据库应用中起到关键性的作用，例如电子商务、数据仓库、科学数据共享、元模型／数据管理、XML消息交换等。 对于模式匹配问题，建立相应的形式化匹配框架是非常重要的，它有助于分析模式匹配问题的结构，建立模式匹配的算法模型和评价模式匹配算法。然而，目前对于模式匹配研究的工作主要集中在基于特定应用领域的匹配算法研究，而没有对模式匹配问题的代数学基础进行过深入研究。因此，论文研究工作首先着重于建立一个模式匹配的泛代数描述框架： 1．基于泛代数的观点，本文将模式定义为一类特定的有限结构(代数)，称之为多标记模式，其最显著的特点就是可以形式化地描述任何类型的模式，并将这些模式转换为基于特定基调的有限结构，基调中包含各种可以用于匹配操作的信息。基于多标记模式，运用泛代数学研究方法，可以对模式这类有限结构的映射操作进行深入分析和研究。 2．为了刻画多对多的匹配，基于多标记模式，提出了个体匹配和多价匹配的概念。利用多价匹配，可以形式化地描述多对多的模式匹配。 3．基于多标记模式，提出了模式同态的概念，它可以用数学的方法来描述模式的多价匹配。 4．基于多价匹配和模式同态，证明了模式匹配问题与模式同态的等价性：模式匹配问题等价于寻找两个模式之间最强的模式同态。这样，就建立了模式匹配问题的泛代数描述框架：模式同态。 由于同态是一个典型的组合优化问题，基于模式同态，论文首次将模式匹配问题形式化为一个组合优化问题，得到模式匹配的算法模型。基于模式匹配的算法模型，论文进行了模式匹配算法的研究： 1．将多标记模式实例化为一种描述异构模式的元模型，称之为多标记图模型，它可以很好地描述模式中元素的语义性质，以及元素之间的各种关系。多标记图模型实质上是一种基于图模型的语义数据模型。 2．由于使用多标记图模型来表示各种异构的模式，因此，自然而然地将模式匹配问题归约为多标记图同态，即多标记图匹配的问题，它是经典的组合优化问题。 3．基于对比模型，研究了多标记图相似性计算方法，建立了基于对比模型的多标记图匹配的优化目标函数。由此，综合已有的模式相似性度量方法，可以设计各种优化搜索算法来求解模式匹配问题。 4．多空间搜索是解决NP难解问题的有效的算法设计思想，论文采用贪婪策略和局部搜索技术，设计了基于多空间搜索的多空间匹配算法。使用若干模式样本对多空间匹配算法进行测试，实验结果证明了多空间匹配算法的有效性，以及模式同态算法模型的正确性。 5．由于图匹配是一个经典的NP难解问题，论文研究了模式匹配问题及其子问题的计算复杂性问题。