Chapter06 The Relational Algebra

6-1

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

บทที่ 6* พีชคณิตเชิงสัมพันธ The Relational Algebra วัตถุประสงค 1. เพื่อศึกษาตัวอยางฐานขอมูลทางธุรกิจ 2. เพื่อศึกษาโอเปอเรเตอรพีชคณิตเชิงเสน 3. เพื่อศึกษาภาษา QBE

6.1

ฐานขอมูลในธุรกิจ ตัวอยางฐานขอมูลที่ใชในเชิงธุรกิจ ตัวอยางแสดงเคารางของรีเลชันที่มีความสัมพันธกัน โดยแตละรีเลชันจะมีคียหลักซึ่ง แอทตริบิวตจะขีดเสนใต

รูปที่ 6.1 ฐานขอมูล EMPLOYEE

6.2

หลักการของพีชคณิตเชิงสัมพันธ • • •

การทําโอเปอเรชันสําหรับโมเดลความสัมพันธจะถูกเรียกวาเปนพีชคณิตเชิงเสน ซึ่งจะทําการเรียกใชขอมูลจาก รีเลชันตางๆไดตามความตองการ ผลที่ไดจากการทําโอเปอเรชันพีชคณิต (algebra operations) นั้นจะทําใหเกิดรีเลชันใหม ซึ่งอาจจะเกิดมา จากรีเลชันเดียวหรือหลายรีเลชัน การทําโอเปอเรชันพีชคณิตที่ซอนกัน ก็จะไดผลแสดงเปนคิวรี่ของฐานขอมูล (Database Query)

* อางอิงจากบทที่ 6 ของเอกสารอางอิง [1]

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

6.3

6-2

การจัดแบงประเภทโอเปอเรชันเชิงสัมพันธ (Relational Operations)

•

โอเปอเรชันเชิงสัมพันธจากรีเลชันเดียว (Unary Relational operations) ตัวโอเปอเรเตอรไดแก SELECT , PROJECT and RENAME โอเปอเรชันเชิงสัมพันธจาก 2 รีเลชัน (Binary Relational Operations) - ตัวโอเปอเรเตอรไดแก JOIN and DIVISION โอเปอเรชันเชิงสัมพันธจากหลายรีเลชัน (N-Nary Relation Operations) - จะมีการนําเอาตัวโอเปอเรชั่นหลายตัวมาใชรวมกัน -

• •

6.3.1 โอเปอเรชันเชิงสัมพันธจากรีเลชันเดียว (Unary Relational

operations) SELECT

• • • • •

จะเปนการเลือกซับเซตของทูเพิลจากรีเลชันตามเงื่อนไขที่ตองการ จะมีรูปแบบของการทําโอเปอเรชันคือ σ<selection condition>(R) สัญญลักษณ σ เรียกวา ซิกมา (sigma) เปนสัญลักษณที่ใชในการทํา SELECT selection condition จะเปนการใสเงื่อนไขที่ตองการ R เปนชื่อของรีเลชันที่ตองการทําโอเปอเรต ตัวอยาง

σSALARY>30000(EMPLOYEE)

หมายถึง ตองการเลือกทูเพิลของรีเลชัน EMPLOYEE เฉพาะรายการที่มีเงินเดือนมากกวา 30000 เทานั้น คุณสมบัติของ SELECT • โอเปอเรเตอร SELECT นั้นผลที่ไดจะมีเคาราง (Schema) เหมือนกับรีเลชันตั้งตน σ<selection condition>(R) กับ R มีเคารางเดียวกัน • โอเปอเรเตอร SELECT มีคุณสมบัติการเรียงสับเปลี่ยน σ(σ(R))=σ(σ(R)) •

โอเปอเรเตอร SELECT อาจจะมีการเปลี่ยนลําดับการทําได

•

σ(σ(σ(R))) =σ(σ(σ(R))) โอเปอเรเตอร SELECT สามารถแทนไดโดยการใชตัวเชื่อม σ(σ(σ(R))) =σAND AND (R)

PROJECT

• • • • • •

จะเปนการเลือกเฉพาะคอลัมนที่ตองการจากตารางหรือรีเลชันเทานั้น จะมีรูปแบบของการทําโอเปอเรชันคือ π(R) โดย π เรียกวา พาย (pi) เปนสัญลักษณที่ใชในการทํา PROJECT attribute list คือแอทตริบิวตตามที่ตองการ R เปนชื่อของรีเลชันที่ตองการทําการโอเปอเรต โอเปอเรเตอร PROJECT นั้นถามีทูเพิลซ้ํากันก็จะใหลบทูเพิลที่ซ้ําออก ตัวอยาง πLNMAE,FNAME,SALARY(EMPLOYEE) หมายถึง ตองการเลือกเฉพาะแอทตริบิวต LNAME,FNAME และSALARY จากรีเลชัน EMPLOYEE

เทานั้น

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

6-3

คุณสมบัติของ PROJECT • •

การ PROJECT นั้นผลที่ไดจะมีจํานวนทูเพิลนอยกวาหรือเทากับรีเลชันตั้งตน ถาแอทตริบิวตที่เปนคียถูกเลือกใน การโอเปอเรชัน PROJECT จะทําให π(R) กับ R มีจํานวนทูเพิลเทากัน

รูปที่ 6.2 การ SELECT และ PROJECT รูปที่ 6.2 แสดงการใชคําสั่ง SELECT และ PROJECT (a) σ (DNO=4 AND SALARY>25000) OR (DNO=5 AND SLARY>30000)(EMPLOYEE) (b) πLNMAE,FNAME,SALARY(EMPLOYEE) (c) πSEX,SALARY(EMPLOYEE)

RENAME ถาในบางครั้งเราจําเปนที่จะตองนําผลลัพธ จากการทําโอเปอเรชันพีชคณิตเชิงสัมพันธ ไปหาผลลัพธอยางตอเนื่อง ดังนั้นเราจึงจําเปนที่จะตองสรางรีเลชันที่เปนสื่อกลาง (intermediate result relation) ที่จะนํารีเลชันสื่อกลางที่ ไดนี้ไปหาผลลัพธตอไป ซึ่งมีสัญลักษณที่ใชแทนคือ ρ เรียกวา โรห (rho) ตัวอยาง ถาตองการขอมูลชื่อ นามสกุล และเงินเดือน ที่อยูในแผนกหมายเลข 5 เราจะสามารถเขียนไดเปน πFNAME, LNAME, SALARY(σ DNO=5(EMPLOYEE))

หรือถาตองการใหแสดงอยูในรูปของรีเลชันสื่อกลางจะไดเปน DEP5_EMPS ← σ DNO=5(EMPLOYEE) RESULT ← π FNAME, LNAME, SALARY (DEP5_EMPS)

จากคําสั่งขางบน จะมีการสรางรีเลชันชื่อ DEP5_EMPS เพื่อดึงขอมูลของแผนก 5 ออกมากอนแลวจึงสรางรีเลชัน ชื่อ RESULT เพื่อดึงขอมูลเฉพาะชื่อ นามสกุลและเงินเดือน ออกมาจากรีเลชันชื่อDEP5_EMPS อีกครั้งหนึ่ง ดังแสดงไวในรูปที่ 6.2

รูปที่ 6.3 การใชรีเลชัน สื่อกลางและ RENAME

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

6-4

รูปที่ 6.3 แสดงการสรางรีเลชันสื่อกลางและคําสั่ง RENAME (a) (b)

πFNAME, LNAME, SALARY(σ DNO=5(EMPLOYEE)) TEMP ← σ DNO=5(EMPLOYEE) R ← π FNAME, LNAME, SALARY (TEMP)

โอเปอเรชันพีชคณิตเชิงสัมพันธโดยใชทฤษฏีของเซต UNION

การ UNION แทนดวยสัญลักษณ R ∪ S หมายถึง จะมีการสรางรีเลชันใหม โดยจะนําทูเพิลของ R และทูเพิลของ S มารวมกัน โดยถามีทูเพิลที่ซ้ํากัน ก็จะ นําทูเพิลนั้นมาลงในรีเลชันใหมเพียงทูเพิลเดียว ดังตัวอยางรูปที่ 6.4

รูปที่ 6.4 การสรางรีเลชัน RESULT

รูปที่ 6.4 แสดงการสรางรีเลชัน RESULT ที่เกิดจาก RESULT1 ∪ RESULT2 จะเห็นไดวา คา 333445555 มีอยูทั้งใน RESULT1 และ RESULT2 แตเมื่อมีทําการ UNION จะปรากฏอยู ใน RESULT เพียงคาเดียว Type ที่สามารถใชได (Type Compatibility) • แอทตริบิวตที่จะนํามา UNION กัน จําเปนตองมีจํานวนแอทตริบิวตและโดเมนที่เขากันได • รีเลชันที่เปนผลลัพทธของ R1 ∪ R2 , R1 ∩ R2 , R1 – R2 นั้นจะมีชื่อแอทตริบิวตตามรีเลชันตัวแรก (R1)

INTERSECTION

สัญลักษณการ INTERSECTION แทนดวย R ∩ S หมายถึง จะมีการสรางรีเลชันใหม โดยจะนําทูเพิลของ R และทูเพิลของ S มาเลือกเฉพาะทูเพิลที่ซ้ํากัน ก็จะนําทู เพิลนั้นมาลงในรีเลชันใหมซึ่งถาทูเพิลไมซ้ํากันก็ใหตัดทิ้ง

MINUS สัญลักษณการ MINUS แทนดวย R - S หมายถึง จะมีการสรางรีเลชันใหม โดยจะนําทูเพิลเฉพาะที่อยูใน R แตไมอยูใน S มาลงในรีเลชันใหมเทานั้น ซึ่งถา ทูเพิลนั้นอยูเฉพาะใน S อยางเดียวหรือทูเพิลนั้นอยูทั้งใน R และ S ใหตดทิ้ง

รูปที่ 6.5 UNION INTERSECTION และ MINUS

รูปที่ 6.5 แสดงการ UNION INTERSECTION และ MINUS

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย (a) (b) (c) (d) (e)

6-5

แสดงรีเลชัน STUDENT กับ รีเลชัน INSTRUCTOR แสดงผลลัพธของ STUDENT INSTRUCTOR แสดงผลลัพธของ STUDENT ∩ INSTRUCTOR แสดงผลลัพธของ STUDENT - INSTRUCTOR แสดงผลลัพธของ INSTRUCTOR - STUDENT

จากรูป 6.5 จะเห็นวาชื่อแอทตริบิวตของผลลัพธของ (d) กับ (e) จะขึ้นอยูกับรีเลชันตัวแรก • • •

UNION กับ INTERSECTION มีคุณสมบัติการเรียงสับเปลี่ยน R ∪ S = S ∪ R และ R ∩ S = S ∩ R UNION กับ INTERSECTION มีคุณสมบัติการจัดกลุม R ∪ (S ∪ T) = (R ∪ S) ∪ T และ R ∩ (S ∩ T) = (R ∩ S) ∩ T MINUS ไมมีคุณสมบัติการสลับที่ R-S ≠ S-R

CARTESIAN สัญลักษณการ CARTESIAN แทนดวย R x S หมายถึง จะมีการสรางรีเลชันใหม โดยจะเกิดจากการนําแอทตริบิวตของ R มารวมกับแอทตริบิวตของ S โดยนําทู เพิลทุกตัวของ R มาตอกันกับทูเพิลทุกตัวของ S ดังนั้นจํานวนแอทตริบิวตของ R x S จะเทากับ จํานวนแอทตริบิวต R + จํานวนแอทตริบิวต S และ จํานวนทูเพิลของ R x S ซึ่งเขียนแทนไดเปน ⎢R x S ⎢ = จํานวนทูเพิล R * จํานวนทูเพิล S

รูปที่ 6.6a UNION INTERSECTION และ MINUS

รูปที่ 6.6a

รูปที่ 6.6b ผลการ CARTESIAN

FEMALE_EMPS ← σ SEX=’F’(EMPLOYEE) EMPNAMES ← π FNAME, LNAME, SSN (FEMALE_EMPS)

6-6

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

รูปที่ 6.6b แสดงผลการ UNION INTERSECTION และ MINUS EMP_DEPENDENTS ← EMPNAMES x DEPENDENT

รูปที่ 6.6c ผลลัพธของ UNION INTERSECTION และ MINUS

รูปที่ 6.6c แสดงผลลัพธ ACTUAL_DEPENDENTS ← σ SSN=ESSN(EMP_DEPENDENTS ) RESULT ← π FNAME, LNAME,DEPENDENT_NAME (ACTUAL_DEPENDENTS)

6.3.2 โอเปอเรชันเชิงสัมพันธจาก 2 รีเลชัน (Binary Relational Operations) JOIN • •

•

ถาตองการดึงขอมูลจาก 2 รีเลชันที่มีทูเพิลอางอิงถึงกันเราเรียกวา JOIN โอเปอเรเตอร JOIN นี้มีความสําคัญอยางมากในการสรางความสัมพันธของฐานขอมูลที่มีมากกวา 1 รีเลชัน เพราะถือวาโอเปอเรเตอร JOIN นี้ทําใหรีเลชันมีการเชื่อมโยงกันภายในฐานขอมูลเดียวกัน สัญลักษณการ JOIN จะถูกแทนดวย R <join condition> S

รูปที่ 6.7 ผลลัพธของ JOIN

รูปที่ 6.7 DEPT_MGR ← DEPARTMENT

MGRSSN=SSN EMPLOYEE

6.7 นี้ เปนการดึงขอมูลของผูจัดการประจําแผนกโดยการโอเปอเรชัน JOIN ของรีเลชัน DEPARTMENT มา JOIN กับ รีเลชัน EMPLOYEE โดยเชื่อมโยงจากคาของ MGRSSN ตองเทากับคา ของ SSN

จากรูปที่

EQUI JOIN •

เปนการเชื่อมโยงขอมูลที่สนใจ “คาของขอมูล” ที่อยูในแอทตริบิวตที่เชื่อมโยงกันใหมีคาเทากัน โดยใช เครื่องหมาย = เชื่อมกันระหวางชื่อแอทตริบิวตของแตละรีเลชัน ที่มีความเชื่อมโยงกัน

NATURAL JOIN •

เปนการเชื่อมโยงขอมูลที่สนใจ “ชื่อแอทตริบิวต” โดยรีเลชันที่จะนํามาเชื่อมโยงกัน จะตองมีชื่อแอทตริบิวตที่ เหมือนกัน โดยแทนดวยเครื่องหมาย *

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

6-7

รูปที่ 6.7 ผลลัพธของ NATURAL JOIN

รูปที่ 6.7 แสดงถึงผลลัพธของการทํา NATURAL JOIN (a) PROJ_DEPT ← PROJECT * DEPT. (b) DEPT_LOCS ← DEPARTMENT * DEPT_LOCATIONS

เซตสมบูณของโอเปอเรชันเชิงสัมพันธ ประกอบดวย SELECT σ , PROJECT π ,UNION ∪ INTERSECTION ∩ , MINUS – และ CARTESIAN X ซึ่งถือวาเปนเซตสมบูรณ เพราะวา ในความสัมพันทางพีชคณิตนั้นสามารถนําทั้ง 5 โอเปอเรเตอรมาจัดการหาคาของขอมูลได ตัวอยาง R ∩ S = (R ∪ S) – ((R – S) ∪ (S - R)) R <join condition>S = σ<join condition>( R x S )

DIVISION สัญลักษณการ DIVISION แทนดวย R(Z) ÷ S(X) โดย X เปนซับเซตของ Z หมายถึง จะมีการสรางรีเลชันใหม โดยมีแอทตริบิวตที่ไดจะเปนแอทตริบิวตที่อยูใน R แตไมอยูใน S สวนทูเพิลที่ได นั้น จะตองเปรียบเทียบกับทูเพิลของ R กับ S ใหมีคาในแอทตริบิวตที่เหมือนกัน แลวคาในแอทตริบิวตอื่น (ที่อยู ใน R แตไมอยูใน S)ของ R จะตองเหมือนกัน จึงนําคาที่ไดนั้นไปใสในรีเลชันใหม ดังตัวอยางรูปที่ 6.8

รูปที่ 6.8 ผลลัพธของ DIVISION

รูปที่ 6.8 แสดงคาผลลัพธ (a) Dividing SSN_PNOS by SMITH_PNOS (b) T ← R ÷ S

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

6-8

รูปที่ 6.9 ตารางแสดงโอเปอ เรชันของพีชคณิต เชิงสัมพันธ

6.3.3 โอเปอเรชันเชิงสัมพันธอนื่ ๆ (Additional Relational Operations การจัดกลุมและหาผลรวม การใชงานของฐานขอมูลนั้น ในสวนที่เปนตัวเลขสามารถที่จะนํามาใชได โดยมีการจัดกลุมตามคาโดเมนของแตละ แอทตริบิวต แลวสามารถนํามาโอเปอเรชันทางคณิตศาสตรได ซึ่งในแตละกลุมจะมีการคํานวณไดคือ ผลรวม (sum) , คาเฉลี่ย (average) , คาสูงสุด (maximum) , คาต่ําสุด (minimum) และการนับ (count)

รูปที่ 6.10 การนับจํานวน พนักงานและการหา คาเฉลี่ยของ เงินเดือน

รูปที่ 6.10 แสดงการหาการนับของจํานวนพนักงานและการหาคาเฉลี่ยของเงินเดือน DNO ℱCOUNT SSN, AVERAGE Salary (Employee)

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

6-9

ฟงกชันนัลโอเปอเรชัน • • •

การหาคาสูงสุดในแอทตริบิวต สามารถเขียนไดเปน ℱ MAX (R) การหาคาต่ําสุดในแอทตริบิวต สามารถเขียนไดเปน ℱ MIN (R) การหาคาผลรวมในแอทตริบิวต สามารถเขียนไดเปน ℱ SUM (R)

Outer JOIN •

• •

ใน Natural JOIN นั้นถาขอมูลในการเชื่อมโยงกันนั้นไมตรงกันก็จะถูกตัดทิ้ง ซึ่งจะทําใหขอมูลเกิดการสูญ หาย ดังนั้นจึงเกิดเปน Outer JOIN ที่จะเก็บคาทั้งหมดที่เกิดจากโอเปอเรชั่น JOIN โดยถาคาในขอมูลใด ไมมีก็จะใหเปนคาวาง (null) สัญลักษณ R S หมายถึงเก็บขอมูลทุกคาใน R แลว ขอมูลใน S บางคาที่ไมมีจะใสคาวาง สัญลักษณ R S หมายถึงเก็บขอมูลทุกคาใน S แลว ขอมูลใน R บางคาที่ไมมีจะใสคาวาง

รูปที่ 6.11 ผลการ JOINที่มี คา NULL รูปที่ 6.11 แสดงถึงรีเลชันที่ JOIN แลวทําใหเกิดคาวาง (null)

Outer UNION โอเปอเรเตอร Outer UNION ถูกพัฒนาขึ้นมาจากการที่ไมสามารถนํารีเลชัน 2 รีเลชันมาทําการ UNION ได เนื่องจากแอทตริบิวต ของทั้ง 2 รีเลชันนั้น ไมเหมือนกันทั้งหมด ดังนั้นถามีรีเลชัน R(X,Y) กับ S(X,Z) ซึ่งจะได รีเลชันใหมเปน T(X,Y,Z) ซึ่งจะทําใหในแตละทูเพิลของรีเลชัน T มีคาวาง (null) ในแอทตริบิวต Y หรือ แอทตริ บิวต Z ในคาใดคาหนึ่ง

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

แบบฝกหัด 1. 2. 3. • •

จงอธิบายความสําคัญของการทําโอเปอรเรชัน rename จงอธิบายความแตกตางระหวาง JOIN กับ OUTER JOIN จงพิจารณาฐานขอมูล Companyในรูป เพื่อตอบคําถามตอไปนี้ แอทตริบิวตใดในรีเลชั่น WORKS_ON ใน ไมสามารถเปนคา NULL ได เพราะเหตุใด แอทตริบิวตใดในรีเลชั่น PROJECT เปนคียนอก และคียดังกลาวเปนคียหลักของรีเลชั่นใด

6-10