SQL实现中关系代数的除法
关系代数中除法的SQL实现
文章目录
- 关系代数中除法的SQL实现
- 引言
- 除法
- 笛卡尔积的逆
- SQL实现
- 应用场景举例
- 集合谓词的缺席
- 实现减法
- 实现除法
- 附录
- 实验用SQL
引言
关系代数中的运算主要有选择、投影、连接(或者说乘法,即笛卡尔积)、除法,以及集合运算。其中,选择、投影、连接能直接用 SQL 表达,但除法和大部分集合运算不能。尤其是除法的缺失,使得涉及该操作的查询难以编写。本文将介绍用如何现有 SQL 实现除法,并分析困难产生的原因。
除法
笛卡尔积的逆
关系除法可以看作笛卡尔积的逆,即对于
R
÷
S
R\div S
R÷S,其结果为所有满足
T
×
S
⊆
R
T\times S\subseteq R
T×S⊆R的
T
T
T中最大的那个,有
T
=
π
(
R
)
−
π
(
(
π
(
R
)
×
S
)
−
R
)
T=\pi(R)-\pi((\pi(R)\times S)-R)
T=π(R)−π((π(R)×S)−R)
可以将该结论表达为SQL以实现除法吗?在不支持
MINUS
,EXCEPT
的数据库中不能。由于R至少有两列,用NOT EXISTS实现MINUS并不简单。
SQL实现
应用场景举例
假设如下关系,
人与技能
person | skill |
---|---|
张大仙 | LOL |
殷子 | 笑 |
卫小妹 | CV |
成少 | LOL |
孙文涛 | Java |
张大仙 | 打剑 |
张大仙 | 机器学习 |
成少 | 机器学习 |
卫小妹 | 笑 |
需求的技能
skill |
---|
LOL |
机器学习 |
要求:找出PersonSkill中会Skill中所有技能的人。
这是一个典型的关系除法问题,将问题翻译成关系代数语言,即
P
e
r
s
i
o
n
S
k
i
l
l
÷
S
k
i
l
l
PersionSkill\div Skill
PersionSkill÷Skill
如何用SQL实现关系除法?
集合谓词的缺席
结合上述实际问题,一种自然的想法是:当一个人的所有技能包含需求的技能时,这个人被选中。试翻译为 SQL,
SELECT person
FROM PersonSkill AS PS
GROUP BY person
HAVING PS.skill CONTAINS SKill
可惜这不是一段可以执行的SQL,因为目前SQL不支持集合层面的包含关系判定。
经过观察不难发现,当前 SQL 支持的所有真假判断(谓词)都定义在元组层面上,这迫使我们将 PersonSkill 中的 person 看作分散的个体,每个元组依次独立做出判断。然而,这作用在单个元组上的判断又必须考虑与其同集合的其他元组,这让子查询的使用成为必然。最后,由于使某元组为真的谓词必定使其同集合元组为真,需要加 DISTINCT 去重。
综合上述思考,调整SQL语句框架为
SELECT DISTINCT person
FROM PersonSkill AS PS
WHERE <某关于PS.person的谓词(子查询)>
实现减法
我们现在要实现这样一个子查询,根据某人的姓名判断其技能是否满足需求。还是按照最自然的思路,判断某人的技能集是否包含需求集。
取出某人技能集的 SQL
SELECT skill
FROM PersonSkill
WHERE person = 某人
需求集
SELECT skill
FROM Skill
记技能集为A,需求集为B,
B
⊆
A
B\subseteq A
B⊆A等价于
∀
x
(
x
∈
B
→
x
∈
A
)
\forall x(x\in B\rightarrow x\in A)
∀x(x∈B→x∈A)
又等价于
!
∃
x
(
x
∈
B
∧
x
∉
A
)
!\exists x(x\in B \land x\notin A)
!∃x(x∈B∧x∈/A)
翻译为SQL
NOT EXISTS (
SELECT * FROM Skill AS S
WHERE S.skill NOT IN (
SELECT skill FROM PersonSkill AS PS
WHERE PS.person = 某人
)
)
也可以看作对等价式
B
−
A
=
∅
B-A=\empty
B−A=∅的判断,其中NOT EXISTS
判定空集,NOT IN
实现集合差。
遗憾的是,
NOT IN
实现集合差只对单列表有效
等价的双EXISTS版本
NOT EXISTS (
SELECT * FROM Skill AS S
WHERE NOT EXISTS (
SELECT * FROM PersonSkill AS PS -- 选A中对应S.skill的元组
WHERE PS.person = 某人 AND -- 某人的技能集A中的一个技能
PS.skill = S.skill -- 和需求集B中的一个技能相同
)
)
这段SQL可以理解为,“不存在B中有一行且A没有行与之对应的情况”,可以算是 ! ∃ x ( x ∈ B ∧ x ∉ A ) !\exists x(x\in B\land x\notin A) !∃x(x∈B∧x∈/A)的直接SQL表述。
双EXISTS版本非常不好理解,原因还是在于我们只能用元组层面的谓词构造集合层面的结论。但如果做差的表不止一列,只能使用双EXISTS版本。
实现除法
综合上述讨论,
SELECT DISTINCT person
FROM PersonSkill AS PS1
WHERE NOT EXISTS (
SELECT * FROM Skill AS S -- WHERE
WHERE NOT EXISTS (
SELECT skill FROM PersonSkill AS PS2
WHERE PS2.person = PS1.person AND
PS2.skill = S.skill
)
);
有时,做“除数”的表(本例中的Skill)也是筛选得出的,这种情况可以在上述SQL的注释处添加选择条件。
附录
实验用SQL
CREATE TABLE PersonSkill (
person VARCHAR(10) NOT NULL,
skill VARCHAR(20) NOT NULL,
PRIMARY KEY (person, skill)
);
INSERT INTO PersonSkill
VALUES ('张大仙', 'LOL'), ('殷子', '笑'), ('卫小妹', 'CV'),
('成少', 'LOL'), ('孙文涛', 'Java'), ('张大仙', '打剑'),
('张大仙', '机器学习'), ('成少', '机器学习'), ('卫小妹', '笑');
CREATE TABLE Skill (
skill VARCHAR(20) NOT NULL,
PRIMARY KEY (skill)
);
INSERT INTO Skill
VALUES ('LOL'), ('机器学习');
SELECT DISTINCT person
FROM PersonSkill AS PS1
WHERE NOT EXISTS (
SELECT * FROM Skill AS S -- WHERE
WHERE NOT EXISTS (
SELECT skill FROM PersonSkill AS PS2
WHERE PS2.person = PS1.person AND
PS2.skill = S.skill
)
);
结果为张大仙、成少。
推荐阅读
-
深入分析 C++ 中的虚拟函数和虚拟继承:实现多态性和继承关系的高级功能
-
纯干货分享 | 研发效能提升——敏捷需求篇-而敏捷需求是提升效能的方式中不可或缺的模块之一。 云智慧的敏捷教练——Iris Xu近期在公司做了一场分享,主题为「敏捷需求挖掘和组织方法,交付更高业务价值的产品」。Iris具有丰富的团队敏捷转型实施经验,完成了企业多个团队从传统模式到敏捷转型的落地和实施,积淀了很多的经验。 这次分享主要包含以下2个部分: 第一部分是用户影响地图 第二部分是事件驱动的业务分析Event driven business analysis(以下简称EDBA) 用户影响地图,是一种从业务目标到产品需求映射的需求挖掘和组织的方法。 在软件开发过程中可能会遇到一些问题,比如大家使用不同的业务语言、技术语言,造成角色间的沟通阻碍,还会导致一些问题,比如需求误解、需求传递错误等;这会直接导致产品的功能需求和要实现的业务目标不是映射关系。 但在交付期间,研发人员必须要将这些需求实现交付,他们实则并不清楚这些功能需求产生的原因是什么、要解决客户的哪些痛点。研发人员往往只是拿到了解决方案,需要把它实现,但没有和业务侧一起去思考解决方案是否正确,能否真正的帮助客户解决问题。而用户影响地图通常是能够连接业务目标和产品功能的一种手段。 我们在每次迭代里加入的假设,也就是功能需求。首先把它先实现,再逐步去验证我们每一个小目标是否已经实现,再看下一个目标要是什么。那影响地图就是在这个过程中帮我们不断地去梳理目标和功能之间的关系。 我们在软件开发中可能存在的一些问题 针对这些问题,我们如何避免?先简单介绍做敏捷转型的常规思路: 先做团队级的敏捷,首先把产品、开发、测试人员,还有一些更后端的人员比如交互运维的同学放在一起,组成一个特训团队做交付。这个团队要包含交付过程中所涉及的所有角色。 接着业务敏捷要打通整个业务环节和研发侧的一个交付。上图中可以看到在敏捷中需求是分层管理的,第一层是业务需求,在这个层级是以用户目标和业务目标作为输入进行规划,同时需要去考虑客户的诉求。业务人员通过获取到的业务需求,进一步的和团队一起将其分解为产品需求。所以业务需求其实是我们真正去发布和运营的单元,它可以被独立发布到我们的生产环境上。我们的产品需求其实就是产品的具体功能,它是我们集成和测试的对象,也就是我们最终去部署到系统上的一个基本单元。产品需求再到了我们的开发团队,映射到迭代计划会上要把它分解为相应的技术任务,包括我们平时所说的比如一些前端的开发、后端的开发、测试都是相应的技术任务。所以业务敏捷要达到的目标是需要去持续顺畅高质量的交付业务价值。 将这几个点串起来,形成金字塔结构。最上层我们会把业务目标放在整个金字塔的塔尖。这个业务目标是通过用户的目标以及北极星指标确立的。确认业务目标后再去梳理相应的业务流程,最后生产。另外产品需求包含了操作流程和业务规则,具需求交付时间、工程时间以及我们的一些质量标准的要求。 谈到用户影响的地图,在敏捷江湖上其实有一个传说,大家都有一个说法叫做敏捷需求的“任督二脉”。用户影响地图其实就是任脉,在黑客马拉松上用过的用户故事地图其实叫督脉。所以说用户影响地图是在用户故事地图之前,先帮我们去梳理出我们要做哪些东西。当我们真正识别出我们要实现的业务活动之后,用户故事地图才去梳理我们整个的业务工作流,以及每个工作流节点下所要包含的具体功能和用户故事。所以说用户影响地图需要解决的问题,我们包括以下这些: 首先是范围蔓延,我们在整张地图上,功能和对应的业务目标是要去有一个映射的。这就避免了一些在我们比如有很多干系人参与的会议上,那大家都有不同想法些立场,会提出很多需求(正确以及错误的需求)。这个时候我们会依据目标去看这些需求是否真的是会影响我们的目标。 这里提到的错误需求,比如是利益相关的人提出的、客户认为产品应该有的、某个产品经理需求分析师认为可以有的....但是这些功能在用户影响地图中匹配不到对应目标的话,就需要降低优先级或弃掉。另外,通常我们去制定解决方案的时候,会考虑较完美的实现,导致解决方案括很多的功能。这个时候关键目标至关重要,会帮助我们梳理筛选、确定优先级。 看一下用户影响到地图概貌 总共分为一个三层的结构: 第一层why,你的业务目标哪个是最重要的,为什么?涉及到的角色有哪些? 第二层how ,怎样产生影响?影响用户角色什么样的行为? (不需要去列出所有的影响,基于业务目标) 第三层what,最关键的是在梳理需求时不需一次把所有细节想全,这通常团队中经常遇到的问题。 我们用这个例子来看一下 这是一个客服中心的影响地图,业务目标是 3个月内不增加客服人数的前提下能支持1.5倍的用户数。此业务目标设定是符合 smart 原则的,specific非常的具体,miserable 是可以衡量的,action reoriented是面向活动的, real list 也是很实际的。 量化的目标会指引我们接下来的行动,梳理一个业务目标,尽量去量化,比如 :我们通过打造一条什么样的流水线,能够提高整个部署的效率,时间是原来的 1/2 。这样才是一个能量化的有意义的目标。 回到这幅图, how 层级识别出来的内容,客服角色:想要对它施加的影响,把客户引导到论坛上,帮助客户更容易的跟踪问题,更快速的去定位问题。初级用户:方论坛上找到问题。高级用户:在论坛上回答问题。通过我们这些用户角色,进行活动,完成在不增加客户客服人数的前提下支持更多的用户数量。 最后一个层级,才是我们日常接触比较多的真正的功能的特性和需求,比如引导到客户到论坛上,其实这个产品就需要有一个常见问题的论坛的链接。这个层次需要我们团队进一步地在交付,在每个迭代之前做进一步的梳理,细化成相应的用户故事。 这个是云智慧团队中,自己做的影响地图的范例,可以看下整个的层级结构。序号表示优先级。 那我们用户影响地图可以总结为:
-
InfoQ,谈谈百度开源高性能搜索引擎 Puck-Ben:Puck是团队长期研究和努力的成果,作为Puck的负责人,我对这个项目有着深深的热爱和执着,对我个人而言,它不仅仅是一个搜索引擎,而是代表着团队心血和智慧的结晶,它是我们对技术的追求,对创新的执着,也是我们对未来的期望和愿景,Puck的每一次升级和优化都记录着我们的成长和进步。这是我们对技术的追求,对创新的执着,也是我们对未来的期望和憧憬,帕克的每一次升级和优化都记录着我们的成长和进步。 我对帕克的未来充满期待。首先,我希望 Puck 能够在开发者社区得到广泛应用,同时得到社区的反馈,不断优化和改进。我期待看到更多的人参与到Puck的开发和使用中来,通过大家的共同努力,让Puck成为人工智能领域有影响力的工具。其次,我希望Puck能够不断创新和优化,保持技术领先地位,不仅要适应当前的技术需求,更要预测和引领未来的技术趋势。最后,我希望Puck能在更多的实际应用中实现自身价值,为人工智能在各行各业的应用提供有力支撑,推动科技发展。 访谈嘉宾简介: Ben,百度搜索内容技术部主任架构师,负责多模态内容理解、超大规模内容关系计算、内容处理与生成、模型优化等方向。 欢迎加入朋克技术交流群:913964818 本部门招聘ANN搜索工程师、模型优化工程师、分布式计算研发工程师等多个职位。欢迎勇于接受挑战、具有优秀分析和解决问题能力的人才加入我们。 招聘邮箱:tianyakun@baidu.com --END-- 推荐阅读
-
您最喜爱的关系代数与 Sql 实践网站和动手实践
-
windows下进程间通信的(13种方法)-摘 要 本文讨论了进程间通信与应用程序间通信的含义及相应的实现技术,并对这些技术的原理、特性等进行了深入的分析和比较。 ---- 关键词 信号 管道 消息队列 共享存储段 信号灯 远程过程调用 Socket套接字 MQSeries 1 引言 ---- 进程间通信的主要目的是实现同一计算机系统内部的相互协作的进程之间的数据共享与信息交换,由于这些进程处于同一软件和硬件环境下,利用操作系统提供的的编程接口,用户可以方便地在程序中实现这种通信;应用程序间通信的主要目的是实现不同计算机系统中的相互协作的应用程序之间的数据共享与信息交换,由于应用程序分别运行在不同计算机系统中,它们之间要通过网络之间的协议才能实现数据共享与信息交换。进程间通信和应用程序间通信及相应的实现技术有许多相同之处,也各有自己的特色。即使是同一类型的通信也有多种的实现方法,以适应不同情况的需要。 ---- 为了充分认识和掌握这两种通信及相应的实现技术,本文将就以下几个方面对这两种通信进行深入的讨论:问题的由来、解决问题的策略和方法、每种方法的工作原理和实现、每种实现方法的特点和适用的范围等。 2 进程间的通信及其实现技术 ---- 用户提交给计算机的任务最终都是通过一个个的进程来完成的。在一组并发进程中的任何两个进程之间,如果都不存在公共变量,则称该组进程为不相交的。在不相交的进程组中,每个进程都独立于其它进程,它的运行环境与顺序程序一样,而且它的运行环境也不为别的进程所改变。运行的结果是确定的,不会发生与时间相关的错误。 ---- 但是,在实际中,并发进程的各个进程之间并不是完全互相独立的,它们之间往往存在着相互制约的关系。进程之间的相互制约关系表现为两种方式: ---- (1) 间接相互制约:共享CPU ---- (2) 直接相互制约:竞争和协作 ---- 竞争——进程对共享资源的竞争。为保证进程互斥地访问共享资源,各进程必须互斥地进入各自的临界段。 ---- 协作——进程之间交换数据。为完成一个共同任务而同时运行的一组进程称为同组进程,它们之间必须交换数据,以达到协作完成任务的目的,交换数据可以通知对方可以做某事或者委托对方做某事。 ---- 共享CPU问题由操作系统的进程调度来实现,进程间的竞争和协作由进程间的通信来完成。进程间的通信一般由操作系统提供编程接口,由程序员在程序中实现。UNIX在这个方面可以说最具特色,它提供了一整套进程间的数据共享与信息交换的处理方法——进程通信机制(IPC)。因此,我们就以UNIX为例来分析进程间通信的各种实现技术。 ---- 在UNIX中,文件(File)、信号(Signal)、无名管道(Unnamed Pipes)、有名管道(FIFOs)是传统IPC功能;新的IPC功能包括消息队列(Message queues)、共享存储段(Shared memory segment)和信号灯(Semapores)。 ---- (1) 信号 ---- 信号机制是UNIX为进程中断处理而设置的。它只是一组预定义的值,因此不能用于信息交换,仅用于进程中断控制。例如在发生浮点错、非法内存访问、执行无效指令、某些按键(如ctrl-c、del等)等都会产生一个信号,操作系统就会调用有关的系统调用或用户定义的处理过程来处理。 ---- 信号处理的系统调用是signal,调用形式是: ---- signal(signalno,action) ---- 其中,signalno是规定信号编号的值,action指明当特定的信号发生时所执行的动作。 ---- (2) 无名管道和有名管道 ---- 无名管道实际上是内存中的一个临时存储区,它由系统安全控制,并且独立于创建它的进程的内存区。管道对数据采用先进先出方式管理,并严格按顺序操作,例如不能对管道进行搜索,管道中的信息只能读一次。 ---- 无名管道只能用于两个相互协作的进程之间的通信,并且访问无名管道的进程必须有共同的祖先。 ---- 系统提供了许多标准管道库函数,如: pipe——打开一个可以读写的管道; close——关闭相应的管道; read——从管道中读取字符; write——向管道中写入字符; ---- 有名管道的操作和无名管道类似,不同的地方在于使用有名管道的进程不需要具有共同的祖先,其它进程,只要知道该管道的名字,就可以访问它。管道非常适合进程之间快速交换信息。 ---- (3) 消息队列(MQ) ---- 消息队列是内存中独立于生成它的进程的一段存储区,一旦创建消息队列,任何进程,只要具有正确的的访问权限,都可以访问消息队列,消息队列非常适合于在进程间交换短信息。 ---- 消息队列的每条消息由类型编号来分类,这样接收进程可以选择读取特定的消息类型——这一点与管道不同。消息队列在创建后将一直存在,直到使用msgctl系统调用或iqcrm -q命令删除它为止。 ---- 系统提供了许多有关创建、使用和管理消息队列的系统调用,如: ---- int msgget(key,flag)——创建一个具有flag权限的MQ及其相应的结构,并返回一个唯一的正整数msqid(MQ的标识符); ---- int msgsnd(msqid,msgp,msgsz,msgtyp,flag)——向队列中发送信息; ---- int msgrcv(msqid,cmd,buf)——从队列中接收信息; ---- int msgctl(msqid,cmd,buf)——对MQ的控制操作; ---- (4) 共享存储段(SM) ---- 共享存储段是主存的一部分,它由一个或多个独立的进程共享。各进程的数据段与共享存储段相关联,对每个进程来说,共享存储段有不同的虚拟地址。系统提供的有关SM的系统调用有: ---- int shmget(key,size,flag)——创建大小为size的SM段,其相应的数据结构名为key,并返回共享内存区的标识符shmid; ---- char shmat(shmid,address,flag)——将当前进程数据段的地址赋给shmget所返回的名为shmid的SM段; ---- int shmdr(address)——从进程地址空间删除SM段; ---- int shmctl (shmid,cmd,buf)——对SM的控制操作; ---- SM的大小只受主存限制,SM段的访问及进程间的信息交换可以通过同步读写来完成。同步通常由信号灯来实现。SM非常适合进程之间大量数据的共享。 ---- (5) 信号灯 ---- 在UNIX中,信号灯是一组进程共享的数据结构,当几个进程竞争同一资源时(文件、共享内存或消息队列等),它们的操作便由信号灯来同步,以防止互相干扰。 ---- 信号灯保证了某一时刻只有一个进程访问某一临界资源,所有请求该资源的其它进程都将被挂起,一旦该资源得到释放,系统才允许其它进程访问该资源。信号灯通常配对使用,以便实现资源的加锁和解锁。 ---- 进程间通信的实现技术的特点是:操作系统提供实现机制和编程接口,由用户在程序中实现,保证进程间可以进行快速的信息交换和大量数据的共享。但是,上述方式主要适合在同一台计算机系统内部的进程之间的通信。 3 应用程序间的通信及其实现技术 ---- 同进程之间的相互制约一样,不同的应用程序之间也存在竞争和协作的关系。UNIX操作系统也提供一些可用于应用程序之间实现数据共享与信息交换的编程接口,程序员可以通过自己编程来实现。如远程过程调用和基于TCP/IP协议的套接字(Socket)编程。但是,相对普通程序员来说,它们涉及的技术比较深,编程也比较复杂,实现起来困难较大。 ---- 于是,一种新的技术应运而生——通过将有关通信的细节完全掩盖在某个独立软件内部,即底层的通讯工作和相应的维护管理工作由该软件内部来实现,用户只需要将通信任务提交给该软件去完成,而不必理会它的具体工作过程——这就是所谓的中间件技术。 ---- 我们在这里分别讨论这三种常用的应用程序间通信的实现技术——远程过程调用、会话编程技术和MQSeries消息队列技术。其中远程过程调用和会话编程属于比较低级的方式,程序员参与的程度较深,而MQSeries消息队列则属于比较高级的方式,即中间件方式,程序员参与的程度较浅。 ---- 4.1 远程过程调用(RPC)
-
在SQL Server中实现动态行变列操作:自定义表名、分组字段选择、转换过程中的列和值设定
-
在MyBatis中,XML方式与动态SQL的实践应用详解 - 第一部分:XML实现
-
三种方法实现SQL、Pandas和Spark中的窗口函数
-
南邮OJ Web任务大揭秘:层层挑战剖析 1. 挑战一:迷宫般的目录探索 题目作者似乎穷举了所有可能的目录组合,最终在404.php中的