14.1 格的定义及性质
本章目录 · 1 节
本章导读
【14.1 格的定义及性质】本节先按偏序定义格,再说明与两个二元运算的等价定义。符号∧、∨在本章表示交、并运算(下确界、上确界),并非直接把元素当成命题;逻辑应用中会另作说明。格的底集非空。
【定义14.1.1】偏序集(L,≤)中,若任意两个元素a、b都有最大下界和最小上界,就称为格。记a∧b=inf{a,b},a∨b=sup{a,b}。它们是L内唯一的元素;“存在若干上界”不等于“存在最小上界”,“极小上界”也不能未经比较就叫最小上界。
【例14.1.1】正整数n的全部正因子Sₙ,以整除为序,构成格:a∧b=gcd(a,b),a∨b=lcm(a,b)。两者仍为n的正因子。以下依次绘出S₈、S₆、S₃₀,线只表示覆盖关系,交叉处没有标点就不是额外元素。
例如S₃₀中2∨3=6,6∧10=2。格中标号1是全下界,n是全上界,不应与抽象格常用的0、1名称混为具体整数0、1。(例完)
【例14.1.2】(1)幂集P(B)以包含为序是格,X∧Y=X∩Y,X∨Y=X∪Y。(2)整数Z以通常≤为序也是格,x∧y=min(x,y),x∨y=max(x,y);格不要求整个底集有最大或最小元素。(3)以下四图均不是格。
在(b)中c与e不可比,不能因为c画得较低就认为c≤e;(c)中d、e为不可比的极小上界,f在两者之上,仍不产生最小上界。(例完)
【例14.1.3】群G的全部子群L(G)按包含构成格。交H₁∩H₂仍为子群,是最大下界;最小上界为⟨H₁∪H₂⟩,即所有包含两者的子群的交,也等于由两者元素及其逆元作有限乘积生成的子群。H₁∪H₂本身一般不是子群,不能拿并集直接当作并运算。例如V₄中两个不同二阶子群的并集只有三个元素,生成子群却是整个V₄。(例完)
【例14.1.4 数据仓库中的视图格】保留原例的汽车销售背景:Sales(serialNo,date,dealer,price)、Autos(serialNo,model,color)、Dealers(name,city,phone)。其中Sales.serialNo与Autos.serialNo关联,Sales.dealer与Dealers.name关联。查询“从2005年1月1日开始,各城市销售记录的平均价格”可写为:SELECT d.city, AVG(s.price) AS avg_price FROM Sales s JOIN Dealers d ON s.dealer=d.name WHERE s.date >= '2005-01-01' GROUP BY d.city;。
这里日期列是date,原例写作data需修正;该查询只按city分组,不能称为“每个城市每种车型的平均价格”。如果需要分车型,应再连接Autos,并把model加入SELECT和GROUP BY;关联键应唯一,否则重复连接会重复计数。2005年是原例的示意查询起点,并非实时销售数据。
将原始记录按维度分组,预先保存结果即物化视图。一天分组加细一个月分组,代理商分组加细城市分组;若P₁的每块都包含于P₂某块,记P₁≤P₂。全部划分按加细构成格:交运算为共同加细(非空块交),并运算为共同粗化(由“同块”关系的并取等价闭包)。不能把分组名称当作序的全部依据,要检查实际记录的块是否包含。
日期图保留“天→周→全部”和“天→月→季度→年→全部”两条汇总路径。周可能跨月、跨季度、跨年,所以没有擅自补周→月或周→年的连线。日期维应使用带所属期间的唯一分组键;代理商、城市、省的层级也须按实际归属规则定义。
多个维度的分组格作笛卡儿积,逐坐标比较,交、并也逐坐标求,便得到视图格。设V₁按月和城市分组,V₂按周和省分组;某些查询可用任一视图,某些只能使用一个,另一些仍须原始Sales。
图中Q₁可由V₁或V₂回答,Q₂可由V₁回答,Q₃须Sales。这里只展示部分依赖关系,不宣称所选六个节点本身形成完整的视图格。
还须检查聚集函数是否支持重汇总:销量COUNT、总价SUM可相加;平均价格AVG不能将各组均值不加权再平均。应保留每组SUM(price)与COUNT(price),上卷后用总和除以非空价格的总计数,并处理计数为0。例如一组1辆均价10,另一组9辆均价20,总均价19,不是15。仅有月均价不能恢复月内某天的均价。因此“划分更细即可回答”还以保存了足够的聚集信息、可下推过滤条件为前提。(例完)
【定义14.1.2 对偶命题】交换≤与≥,交换∧与∨,保持元素及等号不变,得到对偶式。有界格中还须交换0与1。例如(a∨b)∧c≤c的对偶是(a∧b)∨c≥c。
【格的对偶原理】若一个仅使用这些符号的命题对所有格都成立,其对偶也对所有格成立。理由是将一个格的序反向仍得格,原交变成新并,原并变成新交。该原理针对所有格上的定理;某个特殊格满足的额外性质不能无条件声称在同一个格中自对偶成立。
【定理14.1.1】格的两运算满足交换律、结合律、幂等律和吸收律:
证明交换律用{a,b}={b,a}及确界唯一;(a∨b)∨c与a∨(b∨c)都是{a,b,c}的最小上界,所以相等;幂等律因{a}的确界为a;吸收律因a∧b≤a,故a与a∧b的最小上界恰为a。各条交运算结论由对偶得到。这些论证不要求分配律。
【定理14.1.2及定义14.1.3 代数定义】非空系统(S,*,○)中,若两个二元运算各自交换、结合,并满足双吸收a*(a○b)=a、a○(a*b)=a,则可定义a≤b当且仅当a○b=b;它是格,a∧b=a*b、a∨b=a○b。
先由吸收得a○(a*a)=a,再用另一吸收得a*a=a*(a○(a*a))=a,同理a○a=a。因而关系自反;若a○b=b、b○a=a,则交换性给出a=b;若a○b=b、b○c=c,则a○c=a○(b○c)=(a○b)○c=c,故传递。
吸收律还给出a○b=b当且仅当a*b=a。在此序下a○b是共同上界;若c为任一共同上界,则(a○b)○c=a○(b○c)=a○c=c,所以它最小。对*同理得到最大下界。幂等律已经推出,无须再独立列作额外公理;但不能漏掉任一侧吸收律。
【定理14.1.3】下列三条件等价:a≤b;a∧b=a;a∨b=b。第一到第二由最大下界定义,第二到第三由b∨(b∧a)=b,第三到第一由a≤a∨b。
【定理14.1.4 单调性】若a≤b、c≤d,则a∧c≤b∧d,a∨c≤b∨d。例如a∧c同时≤b及d,故≤b∧d;并式对偶可得。不等号是允许等号的≤,不能误写为严格小于。
【例14.1.5 分配不等式】任意格均有
第一式由b∧c≤b,c及单调性知左侧分别≤a∨b、a∨c;第二式为对偶并调换等式两边。一般格中只能保证不等式,不能直接写成等式。(例完)
【定义14.1.4 子格】L的非空子集S,若对L原有的∧、∨封闭,则连同这些限制运算形成L的子格。若只把诱导偏序看成另一个格,其确界可能变了,不一定是子格。
【例14.1.6】下图L中取S₁={a,e,f,g}、S₂={a,b,e,g}。
e∧f=c不属于S₁,所以S₁不是子格,虽然S₁的诱导序看起来是四元菱形。S₂为a<b<e<g的链,在L中的两元素确界仍为它们的较小、较大者,均在S₂,所以是子格。(例完)
