กระบวนการสืบค้นข้อมูลแบบกระจาย

ในระบบฐานข้อมูลแบบรวมศูนย์ ประสิทธิภาพของการสืบค้นข้อมูลจะวัดจากปริมาณของการเข้าถึงข้อมูลในดิสก์ แต่ในระบบฐานข้อมูลแบบกระจายจะต้องพิจารณาเพิ่มเติมอีกคือ

- ค่าใช้จ่ายในการส่งข้อมูลผ่านระบบเครือข่าย

- ประสิทธิภาพของไซต์ที่ประมวลผลแต่ละส่วนของคำสั่งแบบขนาน

ความสัมพันธ์ของค่าใช้จ่ายระหว่างการส่งข้อมูลผ่านระบบเครือข่ายและการส่งข้อมูลจากดิสก์ จะขึ้นอยู่กับประเภทของระบบเครือข่าย และความเร็วของดิสก์ ดังนั้นเราไม่สามารถที่จะระบุลงไปได้เลยว่าจะต้องเสียค่าใช้จ่ายไปกับดิสก์หรือระบบเครือข่ายมากกว่ากัน

1. Query Transformation

พิจารณาแบบสอบถามง่าย ๆ “จงแสดงข้อมูลทุกทูเปิลของรีเลชัน employee” จะเห็นว่าในระบบฐานข้อมูลแบบรวมศูนย์จะเป็นแบบสอบถามที่ง่าย แต่ในระบบฐานข้อมูลแบบกระจาย การประมวลผลแบบสอบถามนี้จะค่อนข้างยุ่งยากในการประมวลผล เนื่องจากรีเลชัน employee อาจจะถูกทำสำเนาไว้หลาย ๆ ไซต์ หรือถูกแบ่งออกเป็นหลายๆ รีเลชันย่อย หรือถูกทำทั้งสองอย่าง ถ้ารีเลชัน employee ถูกทำสำเนาและไม่ได้ถูกแบ่งออกเป็นรีเลชันย่อย เราก็จะเลือกสำเนาที่มีค่าใช้จ่ายในการส่งข้อมูลน้อยที่สุด อย่างไรก็ตามถ้าสำเนาของรีเลชันมีการแบ่งออกเป็นรีเลชันย่อยด้วย การเลือกก็จะมีความยุ่งยากเพิ่มขึ้น เนื่องจากเราต้องทำการ join หรือ union เพื่อสร้างรีเลชัน employee สำหรับกรณีนี้ ก็สามารถดำเนินการได้หลายวิธี

Fragmentation Transparency มีความหมายว่า ผู้ใช้อาจจะเขียนแบบสอบถามเป็น

s _{state=’New york’} (employee)

และเนื่องจาก employee ถูกกำหนดดังนี้

employee ₁ U employee ₂

สามารถเขียนได้ดังนี้

s _{state=’New york’} (employee ₁ U employee ₂)

ถ้าเราทำการอ๊อปติไมซ์นิพจน์นี้ เราสามารถเขียนเป็นนิพจน์ได้ดังนี้

s _{state=’New york’} (employee ₁) U s _{state=’New york’} (employee ₂)

ซึ่งทำการแบ่งออกเป็นนิพจน์ย่อย 2 นิพจน์ โดยนิพจน์แรกจะดำเนินการเฉพาะ employee ₁ ที่ไซต์ New york และนิพจน์ที่สองจะดำเนินการเฉพาะ employee ₂ ที่ไซต์ Texas

ถ้าเรามีการทำอ๊อฟติไมซ์ต่อไป โดยพิจารณาที่นิพจน์แรก

s _{state=’New york’} (employee ₁)

เนื่องจาก employee ₁ จะมีข้อมูลเฉพาะของ New york เท่านั้น ดังนี้เราสามารถที่จะขจัดการดำเนินการ Selection ออกไปได้ และในนิพจน์ที่สอง

s _{state=’New york’} (employee ₂)

เราสามารถปรับได้ดังนี้

s _{state=’New york’} (s _{state=’Texas’} (employee))

ผลลัพท์ที่จะเป็นเซตว่าง ดังนั้นเมื่อทำการอ๊อปติไมซ์แบบสอบถามแล้ว ผลลัพธ์จะได้จากการดำเนินการดึงข้อมูลจากไซต์ New york เพียงไซต์เดียว

1.1 Simple Join Processing

กลยุทธ์สำคัญในการทำ query-processing คือการเลือกวิธีการ join พิจารณานิพจน์ดังต่อไปนี้

employee department project

สมมุติว่าทั้งสามรีเลชันไม่ได้ถูกทำสำเนาและไม่ได้ถูกแบ่งเป็นรีเลชันย่อย และ employee ถูกเก็บไว้ที่ไซต์ S₁ department เก็บไว้ที่ไซต์ S₂ และ project เก็บไว้ที่ไซต์ S₃ และกำหนด S_i เป็นไซต์ที่จะส่งผลลัพธ์ของแบบสอบถามไปให้ ดังนั้นวิธีการที่เป็นไปได้สำหรับประมวลผลแบบสอบถามนี้คือ

1. ส่งสำเนาของทั้งสามรีเลชันไปที่ไซต์ S_i และใช้เทคนิคต่าง ๆ ในการในการสืบค้นข้อมูลที่ไซต์ S_i

2. ส่งสำเนาของรีเลชัน employee ไปที่ไซต์ S₂ และทำการประมวลผล temp₁= employee department ที่ไซต์ S₂ จากนั้นส่ง temp₁ จากไซต์ S₂ ไปยังไซต์ S₃ และประมวลผล temp₂ = temp₁ project และส่ง temp₂ ไปยังไซต์ S_i

3. ทำในลักษณะคล้าย ๆ กับวิธีการที่สอง แต่สลับไซต์ในการส่งข้อมูล

ไม่มีวิธีไหนที่ดีทีสุด เราต้องพิจารณาระหว่างปริมาณของข้อมูลที่จะต้องส่งระหว่างไซต์ ค่าใช้จ่ายในการส่งผ่านข้อมูลระหว่างสองไซต์ และความเร็วในการประมวลผลของแต่ละไซต์ ซึ่งในวิธีการแรก ถ้าเราส่งข้อมูลทั้งหมดไปที่ไซต์ S_i โดยที่รีเลชันเหล่านั้นมีการสร้างอินเด็กซ์ ดังนั้นเราจำเป็นที่จะต้องสร้างอินเด็กซ์เหล่านั้นที่ไซต์ S_i ด้วย ซึ่งการสร้างอินเด็กซ์ทำให้มีการประมวลผลเพิ่มขึ้นมา และยังมีการใช้ดิสก์เพิ่มขึ้นอีก อย่างไรก็ตามวิธีการที่สองก็มีข้อเสียคือรีเลชันที่ได้จากการทำประมวลผลมีขนาดใหญ่(employee department)ซึ่งต้องส่งข้อมูลจากไซต์ S₂ ไปที่ไซต์ S₃ ซึ่งวิธีการที่สองจะทำให้มีการส่งข้อมูลบนระบบเครือข่ายมากกว่า เมื่อเทียบกับวิธีการที่หนึ่ง

1.2 Semijoin Strategy

แนวคิดการทำแบบสอบถามแบบกระจายโดยใช้วิธีการทำ semijoin มีจุดประสงค์เพื่อลดจำนวนของทูเปิลใน รีเลชันก่อนที่จะทำการส่งให้ไซต์อื่น สมมุติว่าเราต้องการประมวลผลนิพจน์ r₁ r₂ ซึ่ง r₁ และ r₂ เก็บอยู่ที่ไซต์ S₁ และ S₂ ตามลำดับ กำหนดให้ R₁ และ R₂ แทนสกีมาของ r₁ และ r₂ ตามลำดับ สมมุติว่าเราต้องการผลลัพธ์ที่ S₁ ถ้ามีทูเปิลหลาย ๆ ทูเปิลใน r₂ ที่ไม่ได้ join กับทูเปิลใด ๆ ใน r₁ ดังนั้นการส่งรีเลชัน r₂ ทั้งหมดไปที่ไซต์ S₁ ก็จะเป็นการส่งทูเปิลที่ทำให้เกิดการ join เกิดผลลัพธ์ที่เกินมาได้ ดังนั้น ก่อนที่เราจะส่งข้อมูลจาก r₂ ไปที่ไซต์ S₁ ก็น่าจะส่งเฉพาะทูเปิลสามารถ join กับ รีเลชัน r₁ ที่ไซต์ S₁ เท่านั้น

เราสามารถดำเนินการดังกล่าวได้ดังนี้

1. หา temp₁ ß P _{R1 Ç R2} ( r₁ ) ที่ไซต์ S₁

2. ส่ง temp₁ จากไซต์ S₁ ไป S₂

3. หา temp₂ ß r₂ temp₁ ที่ไซต์ S₁

4. ส่ง temp₂ จากไซต์ S₂ ไป S₁

5. ประมวลผล r₁ temp₂ ที่ไซต์ S₂

ในขั้นตอนที่ 3 temp₂ สามารถหาได้จาก r₂ P _{R1 Ç R2} ( r₁ ) และ

ในขั้นตอนที่ 5 ทำ r₁ r₂ P _{R1 Ç R2} ( r₁ ) เราสามารถเขียนนิพจน์ใหม่ได้ดังนี้

(r₁ P _{R1 Ç R2} ( r₁ )) r₂

เนื่องจาก r₁ P _{R1 Ç R2} ( r₁ ) = r₁ ดังนั้นนิพจน์นี้จะเท่ากับ r₁ r₂

วิธีการนี้จะมีความเหมาะสมในกรณีที่จำนวนของทูเปิลของ r₂ มีจำนวนน้อย วิธีการดำเนินการแบบ semijoin แทนด้วยสัญลักษณ์ ดังนั้น semijoin ของ r₁ และ r₂ เขียนแทนด้วย r₁ r₂ คือ

P _R1(r₁ r₂)

ดังนั้น r₁ r₂ จะเป็นการเลือกทูเปิลของ r₁ ที่ เพื่อการทำ r₁ r₂ ซึ่งในขั้นตอนที่ 3 จะสามารถเขียนได้ใหม่ดังนี้

temp₂ = r₂ r₁

1.3 Join Strategies that Exploit Parallelism

พิจารณาการ join ของรีเลชัน 4 รีเลชัน

r₁ r₂ r₃ r₄

ซึ่งรีเลชัน ri จะถูกเก็บไว้ที่ไซต์ S_i สมมุติว่าเราต้องการผลลัพธ์ที่ไซต์ S₁ ซึ่งก็มีอยู่หลายวิธีการที่จะดำเนินการแบบขนาน ยกตัวอย่างเช่น r₁ ถูกส่งไปที่ไซต์ S₂ และทำ r₁ r₂ ที่ไซต์ S₂ ในขณะเดียวกัน r₃ ก็ถูกส่งไปที่ไซต์ r₄ และทำ r₃ r₄ ที่ไซต์ S₄ ไซต์ S₂ จะส่งผลลัพธ์ (r₁ r₂) กลับไปที่ไซต์ S₁ และไซต์ S₃ จะส่งผลลัพธ์ (r₃ r₄) กลับไปที่ไซต์ S₁ เมื่อ S₁ ได้รับผลลัพธ์กลับจาก S₂ และ S₄ แล้ว ก็จะทำการ join อีกครั้ง (r₃ r₄) (r₁ r₂) ดังนั้นจะเห็นว่าการประมวลผลการ join ที่ S₁ สามารถดำเนินการแบบขนานโดยมีการประมวลผลที่ไซต์ S₂ และไซต์ S₄ ไปพร้อมๆ กัน

---

2.1 ความรู้เบื้องต้นของระบบจัดการฐานข้อมูลแบบกระจาย 2.2 กระบวนการสืบค้นข้อมูลแบบกระจาย 2.3 การควบคุมสภาวะการทำงานพร้อมกันและการฟื้นสภาพข้อมูล