该练习介绍查询最小化领域中的图仿真。考虑如下数据上的约束:(

该练习介绍查询最小化领域中的图仿真。考虑如下数据上的约束:(1)必须有双亲约東,其中我们可以指定标签b的一个元素的双亲总有标签a;(2)必须有祖先约束,其中我们可以指定标签b的一个元素总有一个标签a祖先
(1)我们将一个路径表达式表示为PE= roots, I1s2l2.L,其中s是分隔符,L是标签。作为一个有向图,一个节点为root,其他的节点为1。边从root到l,从1到l1。根据分隔符为/还是/,决定了一个边是双亲还是祖先。我们记从u到v的双亲边为u->v,记从u到v的祖先边为u=>v作为一个简单的练习,将路径表达式root//a/b/c表示为一张图。
(2)约束还以如下方式表达在一个有向图中。为每一个标签名创建一个节点。如果有一个约束:每个b元素必须有一个a双亲(祖先),则一个双亲(祖先)边从a标签名指向b标签名。论证:如果约束是有意义的,这个有向图必须是无环的
(3)一个仿真就是在两个有根的有向无环图的节点上的一个二元关系≤,其中这两个图G1和G2满足如下条件:如果u≤v,其中u是G1的一个节点,v是G2的一个节点;那么,对于每一个节点u->v,必定有v->v使得u≤v;并且对于每一个节点u=>v,必定有v的祖先√使得u"≤v。说明存在一个惟一的最大仿真关系≤”。如果u≤"v,称u被v仿真。
(4)说明路径表达式root//b/c可以被写为/c当且仅当查询图中的c节点可以被约束图中的c节点仿真。
(5)路径表达式//ls+11.,L(>1)是 roots, h, s,L2.L的一个后缀。如果它们对于所有满足约束的所有数据库实例的查询结果相同,就称该后缀是等价后缀。请说明如果查询图中的L可以被约束图中的l仿真,就会发生上述情况