軟考：中級軟件設(shè)計(jì)師:關(guān)系代數(shù)

提示：系列被面試官問的問題，我自己當(dāng)時(shí)不會，所以下來自己復(fù)盤一下，認(rèn)真學(xué)習(xí)和總結(jié)，以應(yīng)對未來更多的可能性

關(guān)于互聯(lián)網(wǎng)大廠的筆試面試，都是需要細(xì)心準(zhǔn)備的
（1）自己的科研經(jīng)歷，科研內(nèi)容，學(xué)習(xí)的相關(guān)領(lǐng)域知識，要熟悉熟透了
（2）自己的實(shí)習(xí)經(jīng)歷，做了什么內(nèi)容，學(xué)習(xí)的領(lǐng)域知識，要熟悉熟透了
（3）除了科研，實(shí)習(xí)之外，平時(shí)自己關(guān)注的前沿知識，也不要落下，仔細(xì)了解，面試官很在乎你是否喜歡追進(jìn)新科技，跟進(jìn)創(chuàng)新概念和技術(shù)
（4）準(zhǔn)備數(shù)據(jù)結(jié)構(gòu)與算法，有筆試的大廠，第一關(guān)就是手撕代碼做算法題
面試中，實(shí)際上，你準(zhǔn)備數(shù)據(jù)結(jié)構(gòu)與算法時(shí)以備不時(shí)之需，有足夠的信心面對面試官可能問的算法題，很多情況下你的科研經(jīng)歷和實(shí)習(xí)經(jīng)歷足夠跟面試官聊了，就不需要考你算法了。但很多大廠就會面試問你算法題，因此不論為了筆試面試，數(shù)據(jù)結(jié)構(gòu)與算法必須熟悉熟透了
秋招提前批好多大廠不考筆試，直接面試，能否免筆試去面試，那就看你簡歷實(shí)力有多強(qiáng)了。
（5）考網(wǎng)警的大佬，務(wù)必把軟考：中級軟件設(shè)計(jì)師的內(nèi)容學(xué)好學(xué)透，學(xué)廣，學(xué)多

---

文章目錄

• 軟考：中級軟件設(shè)計(jì)師:關(guān)系代數(shù)
• • @[TOC](文章目錄)
• 軟考：中級軟件設(shè)計(jì)師:關(guān)系代數(shù)
• 規(guī)范化理論——函數(shù)依賴
• 規(guī)范化理論它的價(jià)值和用途
• 規(guī)范化理論的鍵
• 如何求候選鍵——考點(diǎn)哦
• 規(guī)范化里面的范式——年年必考
• • 第一范式1NF：屬性不可分的院子值
  • 第二范式2NF：消除非主屬性，對候選鍵的部分依賴
  • 第三范式3NF：消除非主屬性，對候選鍵的傳遞依賴
  • 第BC范式BCNF：消除主屬性，對候選鍵的傳遞依賴
• 范式例題
• 規(guī)范化理論中的模式分解
• 總結(jié)

軟考：中級軟件設(shè)計(jì)師:關(guān)系代數(shù)

并；重復(fù)的去掉，其余的東西都要撈過來

交：只要重復(fù)的

差呢就是干掉公共部分

這些都不是重點(diǎn)
重點(diǎn)還是后面的

笛卡爾積，沒用的，啥玩意都要組裝一遍

實(shí)際操作中，要避免出現(xiàn)笛卡爾積
因?yàn)檫@種爆炸，也沒有意義

浪費(fèi)空間

n*m
爆炸的

投影是選列【column】
選擇是選行【row】

連接
等值連接
內(nèi)連接，連接
這些都是數(shù)據(jù)庫中的騷操作，我講過很多，你看我數(shù)據(jù)庫那些文章

等值連接，是保證同一個(gè)字段相等時(shí)，可以連接勾出來，把其他的字段掛在屁股，同一個(gè)字段保留一條。

自然連接
你可以仨字段，134列，或者sno，sname，age啥的三同時(shí)滿足條件
好說

規(guī)范化理論——函數(shù)依賴

不用讀上面這段
給定x，一定映射為一個(gè)唯一的y
這波就是x能確定y
f就是函數(shù)依賴
y依賴于函數(shù)f，有x確定y

y不能確定x，因?yàn)槎鄠€(gè)x可以都得到y(tǒng)

學(xué)號，函數(shù)f，直接確定一個(gè)姓名
這是一對一的映射。
只要確定了學(xué)號，它一定對應(yīng)唯一的名字，這是一個(gè)函數(shù)依賴。懂？

反過來不行，姓名同名的話，不見得就是同一個(gè)學(xué)號。

學(xué)號A，課程號B，姓名C
知道了學(xué)號，和課程號，一定可以確定姓名
或者只需要學(xué)號，就知道姓名
這種就是部分依賴

組件中的一部分，就可以唯一確定姓名

傳遞函數(shù)依賴

A確定B
B確定C
則A確定了C
但是B不能回退

規(guī)范化理論它的價(jià)值和用途

考試中的重點(diǎn)知識點(diǎn)哦

計(jì)算機(jī)系，其實(shí)沒必要存這么多，我們可以重新搞一個(gè)表
把系號，拿來做map表的話，我們少存很多信息，節(jié)約空間
這就是規(guī)范化理論的價(jià)值

逆規(guī)范化？加數(shù)據(jù)冗余

規(guī)范化理論的鍵

唯一標(biāo)識元組，單屬性，多屬性組合？超建？？？？？？？？？？
啥玩意

不懂

超建可能存在冗余

候選鍵不冗余

比如，學(xué)號，姓名，性別
學(xué)號確定性別
學(xué)號+性別組合鍵確定性別

則學(xué)號+性別可以是超建
但是它不是候選鍵
因?yàn)樗皇俏ㄒ淮_定
姓名，或者學(xué)號是候選鍵

主鍵，只有一個(gè)，它就是一個(gè)最終的核心代表
數(shù)據(jù)庫中主鍵就是唯一的代表，雖然身份證號，學(xué)號都能唯一確定人，但是只能設(shè)定一個(gè)
外鍵，是別的關(guān)系的主鍵，外表，需要關(guān)聯(lián)，我們需要找到同一個(gè)人，掛接的相關(guān)的屬性
比如部門號
員工很多都可以屬于外鍵中的同一個(gè)部門。

你先學(xué)數(shù)據(jù)庫，再學(xué)這個(gè)玩意，其實(shí)輕松一點(diǎn)哦。

如何求候選鍵——考點(diǎn)哦

很難哦
你怎么識別它是唯一標(biāo)識一個(gè)人的字段

圖示法！最方便

看題

有了依賴有向圖
入度A1沒有一個(gè)箭頭指向它，嘗試遍歷這個(gè)圖
必須每個(gè)點(diǎn)遍歷一遍

BFS可以遍歷整個(gè)圖，則，A1就是候選鍵。

不是聯(lián)通圖？？？？？？？？？？？？？？
這怎么玩！！！！！！

有辦法，當(dāng)無法聯(lián)通時(shí)，或者單獨(dú)一個(gè)點(diǎn)沒法遍歷整個(gè)圖時(shí)
需要找集合，就是那些入度我0的所有點(diǎn)，有了這些點(diǎn)，才能遍歷完所有的點(diǎn)
這些點(diǎn)的集合，就是候選鍵

這種呢？？？？？
B入度為0？？？？找中間節(jié)點(diǎn)，既有入度，也有出度
A同時(shí)決定BC組合鍵
可以
B也可以
所以A或者B都行
這么騷嗎
這就是軟考的題目哦

規(guī)范化里面的范式——年年必考

必考知識點(diǎn)

3NF爆炸了已經(jīng)很好了

123依次變高。【之前考試我都不會】

第一范式1NF：屬性不可分的院子值

屬性已經(jīng)不能再拆分了

高職還能再拆

第二范式2NF：消除非主屬性，對候選鍵的部分依賴

消除非主屬性，對候選鍵的部分依賴。
【注意區(qū)分哦】這是消除非主屬性，對候選鍵的部分依賴

學(xué)號，課程號，聯(lián)合才能決定成績
但是課程號，能決定學(xué)分，一門課就是一個(gè)學(xué)分
非主屬性學(xué)分，沒有完全依賴主鍵
懂了吧，不符合2NF

我們要把課程和學(xué)分固定再搞一個(gè)表
這樣才能符合2范式

問題：
帶來數(shù)據(jù)冗余，學(xué)分對應(yīng)課程，壓根不需要放這么多空間。
更新異常，更新學(xué)分時(shí)，需要全部更新
插入異常，新課程號來了，學(xué)分6分，現(xiàn)在你想錄入學(xué)分
如果沒人選課，則你6分的新課程，你沒法插入啊
尷尬
刪除異常
你刪除學(xué)生，但是學(xué)分也被刪除了，尷尬

解決方案，把學(xué)分單獨(dú)列出一個(gè)表來。

第三范式3NF：消除非主屬性，對候選鍵的傳遞依賴

消除非主屬性，對候選鍵的傳遞依賴
【注意區(qū)分哦】這還是消除非主屬性，對候選鍵的傳遞依賴

一個(gè)字段做主鍵，一定滿足2范式，它不會有部分依賴。

問題：
數(shù)據(jù)冗余，計(jì)算機(jī)系，爆炸，樓號爆炸
更細(xì)姓名，爆炸
新加入學(xué)生也沒法錄入

解決方案
把dno后面仨字段重新獨(dú)立出來，部門重新單獨(dú)列一個(gè)表。

第BC范式BCNF：消除主屬性，對候選鍵的傳遞依賴

消除主屬性，對候選鍵的傳遞依賴
【注意區(qū)分哦】這還是消除主屬性，對候選鍵的傳遞依賴

這個(gè)其實(shí)別管了
我們了解一波
滿足3NF即可

主屬性——屬于候選鍵
非主屬性——不是候選鍵。

它出發(fā)能遍歷所有點(diǎn)

SJ,ST都是候選鍵
相當(dāng)于S,T,J都是主屬性

它滿足3NF
所有函數(shù)依賴
左邊時(shí)候選鍵——這樣才是BCNF
但是現(xiàn)在SJ–>T,ST–>J,T–>J
T不是候選鍵，所以它不是BCNF

這個(gè)就了解了，不管

范式例題

現(xiàn)在表4中有部門
表3需要加部門

表4有月銷售額
所以，需要把職工它銷售了什么商品號，日期是啥，銷量多少，就能算銷售額了
A

規(guī)范化理論中的模式分解

A–>B
B–C
拆分
AB
BC
保持了上面的依賴
這種就是保持函數(shù)的依賴分解
OK
相當(dāng)于拆表格
R3：AC
A–>C，A不能直接確定C，這種是不行的

壓縮時(shí)也會用到

數(shù)據(jù)壓縮，然后還原

數(shù)據(jù)庫學(xué)完了你才能玩這個(gè)東西
很多連接操作，我都會的
只要能連接2個(gè)表，算是無損

很好拆分
主鍵自己帶自己的屬性
連接外鍵搞定好了就好辦了
美滋滋。

分解出來的東西做交集
然后分別做差集

結(jié)果與交集是有依賴的，那就是無損

大致明白

表的某個(gè)鍵，一定與2個(gè)表都有掛接的

---

總結(jié)

提示：重要經(jīng)驗(yàn)：

1）
2）
3）筆試求AC，可以不考慮空間復(fù)雜度，但是面試既要考慮時(shí)間復(fù)雜度最優(yōu)，也要考慮空間復(fù)雜度最優(yōu)。