首页 > 数据库 >sql查询一对多关系中对应的多个值都在某集合中的值

sql查询一对多关系中对应的多个值都在某集合中的值

时间:2024-09-28 14:12:27浏览次数:8  
标签:复杂度 查询 cs stu sql 集合 id select

例如找到所有选的课都在课程表中的学生。
假如课程表中所有课的集合为cs,学生的表为stu,stu.id是学生姓名,stu.c是学生选的课。

思路:不存在某门课不在课程表中。

select id
from (
	select DISTINCT id
	from stu
) ids
where not exists (
	select c
	from stu
	where c not in (select * from cs) and
		stu.id = ids.id
);

测试

create database test;
use test;
create table stu (
	id char(10),
	c char(10)
);
create table cs (
	c char(10)
);
insert into stu
values
("1", "1"),
("1", "2"),
("2", "1"),
("2", "2"),
("3", "1"),
("3", "3"),
("4", "1"),
("4", "2"),
("4", "3"),
("5", "3");
insert into cs
values ("1"), ("2");

然后跑一遍查询,输出

+------+
| id   |
+------+
| 1    |
| 2    |
+------+

复杂度分析:
假设有x名学生,每名学生选了y门课,课程表中有z门课。

select DISTINCT id
from stu

这个子查询的复杂度为O(xy)。因为stu中有xy行,然后扫一遍,用哈希表除重。

select c
from stu
where c not in (select * from cs) and
	stu.id = ids.id

这个子查询跑一次的复杂度为O(y),因为只需要查询一个学生的信息,每个学生选了y门课,在哈希表中找这y门课即可。
这个子查询要跑x次,所以跑这个子查询总共的复杂度为O(xy)。
综上,总复杂度为O(xy)。

标签:复杂度,查询,cs,stu,sql,集合,id,select
From: https://www.cnblogs.com/searchstar/p/18437897

相关文章

  • sql学习笔记
    DDL各种数据类型mysql数据类型decimal参考:https://blog.csdn.net/qq_38228254/article/details/88374713decimal(a,b) a指定小数点左边和右边可以存储的十进制数字的最大个数,最大精度38。 b指定小数点右边可以存储的十进制数字的最大个数。小数位数必须是从0到a之间......
  • mysql 0928 DDL表操作
    `ALTERTABLEempaddnicknameVARCHAR(20)COMMENT'昵称';--添加字段nicknameDESCTABLEemp;--查看表ALTERTABLEempMODIFYnicknamevarchar(10);--修改数据类型ALTERTABLEempchangenicknameusernameVARCHAR(30);--修改字段nickname为usernameALT......
  • MySQL --用户管理
    文章目录1.用户1.1用户信息1.2创建用户1.3删除用户1.4修改用户密码2.数据库的权限2.1给用户授权2.2回收权限如果我们只能使用root用户,这样存在安全隐患。这时,就需要使用MySQL的用户管理。1.用户1.1用户信息MySQL中的用户,都存储在系统数据库mysql的user表中u......
  • T-SQL——关于四舍五入、向上取整、向下取整
    ------------------------------------------------------------------------关于四舍五入--使用ROUND函数四舍五入,但是保留了原始的位数,用0补齐SELECTROUND(2.3363,2);--2.3400SELECTCAST(ROUND(2.3363,2)ASDECIMAL(10,2));--2.34---保留两位小数,使用CAST转为DEC......
  • 深入剖析 MyBatis-Plus:操作总结、对比与实践案例(CRUD 操作、分页、条件构造器、自动填
    MyBatis-Plus是MyBatis的增强工具,它极大简化了MyBatis的配置和操作,提高了开发效率。本文从基本操作到高阶用法,详细介绍了MyBatis-Plus的常见功能及与MyBatis的区别,并通过实际案例展示其强大的扩展能力。MyBatis-Plus基于MyBatis,但旨在减少开发者的代码量,增强可......
  • 【MySQL】MySQL MVCC并发控制的原理、不可重复度、读已提交
    1.概述上一篇文章:【MySQL】MySQL脏读、幻读以及不可重复读、我真的不会读在介绍MVCC并发控制的原理之前,我们先普及两个知识点。要解决并发问题只有一种方案就是加锁。当然,锁不可避免的会导致性能下降,但是,锁也有乐观和悲观之分,上一讲我们聊到的,隔离级别中的串行化就是......
  • 京东面试:RR隔离mysql如何实现?什么情况RR不能解决幻读?
    文章很长,且持续更新,建议收藏起来,慢慢读!疯狂创客圈总目录博客园版为您奉上珍贵的学习资源:免费赠送:《尼恩Java面试宝典》持续更新+史上最全+面试必备2000页+面试必备+大厂必备+涨薪必备免费赠送:《尼恩技术圣经+高并发系列PDF》,帮你实现技术自由,完成职业升级,薪......
  • MySQL:去除字段中空格及前后空格
    1、使用TRIM()函数TRIM()函数可以去除字段的前后空格,并返回处理后的结果。可以在查询语句中使用TRIM()函数来实现去除字段空格的功能,示例如下:SELECTTRIM(column_name)FROMtable_name;这种方法会去除字段中的前后空格,但保留字段内部的空格。2、使用REPLACE()函数REPLACE......
  • 集合论(ZFC)之 幂集公理(Axiom of Power Set)注解
            集合论(ZFC)之幂集公理(AxiomofPowerSet)定义了给定一个集合X,存在一个集合Y为该集合X的幂集,记Y=P(X),其包含了集合X的所有子集(Subset)。    子集关系的定义为,如果集合U的所有元素,都是集合X的元素,那么集合U就是集合X的子集,记U ⊂X,有∀z(z∈U→......
  • MySQL查找占用CPU过高的SQL
    作为DBA工作中都会遇到过数据库服务器CPU飙升的场景,我们该如何快速定位问题?又该如何快速找到具体是哪个SQL引发的CPU异常呢?下面我们说两个方法。聊聊MySQL中如何快速定位占用CPU过高的SQL。技术人人都可以磨炼,但处理问题的思路和角度各有不同,希望这篇文章可以抛砖引玉。 以一......