扩展上下文无关语言上的函数依赖解析

# 扩展上下文无关语言上的函数依赖解析 ## 1. 函数依赖概念概述 在关系数据库中，函数依赖的定义相对直观，因为关系模式的实例是一组元组，可以轻松选择元组对进行比较，以检查实例是否满足给定的函数依赖。然而，在 XML 环境中，定义函数依赖面临着缺乏“元组”概念的问题。XML 世界中没有普遍接受的元组定义，即使选择一组元素并将其声明为“元组”，也很难找到合适的匹配算法。 一些学者提出了不同的解决方案。Arenas 和 Libkin 基于 DTD 模式定义了“树元组”，Vincent 等人描述了“树元组”未涵盖的一些情况，并引入了“最近节点”的概念来处理这些情况。他们在没有任何模式的 XML 树上定义了函数依赖，并使用 DTD 来证明其定义在某些类别的 DTD 中与“树元组”等价。 与关系数据库的经典函数依赖概念相比，所有 XML 函数依赖（XFD）概念都非常复杂，在 XML 数据模型中，它们主要基于路径表达式。为了解决这些问题，提出了一种新的函数依赖概念——正则函数依赖（regular FD），适用于扩展“元组”是正则语言句子的数据模型。其主要动机是为广泛的数据模型找到一个简单而通用的函数依赖定义，唯一的假设是“元组”应该是给定正则语言的句子，即由正则文法生成。 ## 2. 正则表达式与有限状态自动机 ### 2.1 从正则文法到有限状态自动机 要在相应的（非）确定性有限状态自动机（FSA）的图上定义正则语言的正则函数依赖，可以通过以下算法从语言的文法创建自动机： ```plaintext Algorithm 1. Regular Grammar to FSA. Input: G regular grammar, generating the language L(G); Output: M(G) finite state automaton, accepting L(G); Let G=G(N,T,S,P), then the corresponding FSA: M(G) = (N,T,δ,S,END), where N is the (finite) set of the internal states of M, T is the input alphabet, δ is the transition function: for each X ∈N,y ∈T,δ (X,y) ∈N, iff, when there is a production rule X ⇒xY ∈P, S is the initial state, END is the (unique) final state. ``` 在通常情况下，如 XML 模式语言，正则语言将以从语言字母表中选取的符号构建的正则表达式的形式给出。这些符号的集合是生成该语言的正则文法的终结值集合。 ### 2.2 从正则表达式构建有限状态自动机 为了定义正则函数依赖，需要一个接受正则语言的有限状态自动机。有许多算法可以从给定的正则表达式高效地构建有限自动机，主要分为非确定性（NFA）和确定性（DFA）两种类型。这里采用 Berry 和 Sethi 的经典算法，当所有符号都不同时，该算法可以从正则表达式高效地构建 DFA。 ```plaintext Algorithm 2. Construction Berry - Sethi [4]. Input: distinct regular expression E (built from the alphabet Σ, Output: deterministic finite state automaton M(E) accepting L(E). 1. M(E) has a state for the continuation of each (distinct) symbol in E. 2. Construct a transition from state p to the state of the continuation for α ∈E, if and only if, when p is for some continuation C and C can generate a string with a leading α. 3. The start state is for the whole expression E. A state is an accepting state iff, when it is a continuation C and Δ (C) = 1. ``` ### 2.3 示例 假设有一个正则文法 `G({S,A,B},{a,b},S,P)`，其中 `P = {S ⇒aS,S ⇒bS,S ⇒aA,A ⇒bB,B ⇒a}`。正则表达式 `E = (a + b)*aba` 也生成相同的正则语言 `L(G)`。使用算法 2 构建的 FSA 图如下： ```mermaid graph LR classDef startend fill:#F5EBFF,stroke:#BE8FED,stroke-width:2px; classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; S([S]):::startend -->|a| A(A):::process S -->|b| B(B):::process A -->|b| C(C):::process C -->|a| D(D):::process D -->|a| E(E):::process E -->|b| F(F):::process F -->|a| G([G]):::startend ``` ## 3. 正则语言上的函数依赖 ### 3.1 对偶语言的定义 可以对正则语言的对偶语言概念进行推广。设 `L` 是由 FSA `M(L)` 接受的正则语言，`L` 的对偶语言的字母表由 `M(L)` 的状态组成，对偶语言的句子是 `M(L)` 从起始状态到结束状态的接受遍历所访问的状态字符串。 ### 3.2 函数依赖的定义 根据关系函数依赖的概念，可以在每个对偶句子上选择两个子序列，分别作为依赖的左侧和右侧。设 `L` 是正则语言，`M(L)` 是其有限状态自动机的图表示，`X = (X1,X2)` 和 `Y = (Y1,Y2)` 是 `M(L)` 上的两个赋值，且 `X1 ⊆Y1` 和 `V (X2) ⊆V (Y2)`。定义在 `M(L)` 上的函数依赖（正则 FD）是形式为 `X →Y` 的表达式。一个有限数据库实例 `R` 满足 `X →Y` 函数依赖（表示为 `R |= X →Y`），当且仅当对于 `R` 中的任意两个元组 `t1` 和 `t2`，如果 `t1[X]=t2[X]`，则 `t1[Y]=t2[Y]`