อัลกอริทึม " การไล่ล่า" (Chase)เป็นอัลกอริทึมแบบจุดคงที่ที่เรียบ ง่าย ใช้ทดสอบและบังคับใช้ความหมายของการพึ่งพาข้อมูลในระบบฐานข้อมูลมีบทบาทสำคัญทั้งในทฤษฎีฐานข้อมูลและการใช้งานจริง ผู้ที่ออกแบบฐานข้อมูลใช้อัลกอริทึมนี้โดยตรงหรือโดยอ้อมในชีวิตประจำวัน และใช้ในระบบเชิงพาณิชย์เพื่อพิจารณาความสอดคล้องและความถูกต้องของการออกแบบข้อมูล การประยุกต์ใช้การไล่ล่าในรูปแบบใหม่ๆ ในการจัดการเมตาเดต้าและการแลกเปลี่ยนข้อมูลยังคงถูกค้นพบอย่างต่อเนื่อง

การไล่ล่านี้มีต้นกำเนิดมาจากเอกสารสำคัญสองฉบับในปี พ.ศ. 2522 ฉบับหนึ่งโดยAlfred V. Aho , Catriel BeeriและJeffrey D. Ullman ^{[ 1 ]}และอีกฉบับโดยDavid Maier , Alberto O. MendelzonและYehoshua Sagiv ^{[ 2 ]}

ในการประยุกต์ใช้ที่ง่ายที่สุด การค้นหาจะใช้เพื่อทดสอบว่าการฉายภาพของโครงสร้างความสัมพันธ์ที่ถูกจำกัดโดยการพึ่งพาเชิงฟังก์ชัน บางอย่าง ไปยังการแยกส่วนที่กำหนด สามารถกู้คืนได้หรือไม่โดยการเชื่อมต่อการฉายภาพเหล่านั้น เข้าด้วยกัน ให้tเป็นทูเปิลในโดยที่Rคือความสัมพันธ์และFคือเซตของการพึ่งพาเชิงฟังก์ชัน (FD) ถ้าทูเปิลในRถูกแทนด้วยt ₁ , ..., t _kการเชื่อมต่อของการฉายภาพของแต่ละt _iควรตรงกับtบนโดยที่i = 1, 2, ..., kถ้าt _iไม่อยู่ในค่าของมันจะไม่ทราบ ${\displaystyle \pi _{S_{1}}(R)\bowtie \pi _{S_{2}}(R)\bowtie ...\bowtie \pi _{S_{k}}(R)}$${\displaystyle \pi _{S_{i}}(R)}$${\displaystyle \pi _{S_{i}}(R)}$

การค้นหาสามารถทำได้โดยการวาดตาราง (ซึ่งเป็นรูปแบบเดียวกันกับที่ใช้ในแบบสอบถามตาราง ) สมมติว่าRมีแอตทริบิวต์A, B, ...และส่วนประกอบของtคือa, b, ...สำหรับt _iให้ใช้ตัวอักษรเดียวกันกับtในส่วนประกอบที่อยู่ใน S _i แต่ให้ใส่ตัวห้อย iต่อท้ายตัวอักษรหากส่วนประกอบนั้นไม่อยู่ใน S _iจากนั้นt _iจะตรงกับtหากอยู่ใน S _iและจะมีค่าที่ไม่ซ้ำกันในกรณีอื่น ๆ

กระบวนการไล่ล่ามีความต่อเนื่องกันมีการนำอัลกอริทึมการไล่ ล่าไปใช้ ^{[ 3 ]}บางส่วนก็เป็นโอเพนซอร์สด้วย^{[ 4 ​​]}

ให้R ( A , B , C , D ) เป็นสคีมาความสัมพันธ์ที่ทราบว่าสอดคล้องกับชุดความสัมพันธ์เชิงฟังก์ชันF = { A → B , B → C , C → A } สมมติว่าRถูกแยกออกเป็นสคีมาความสัมพันธ์สามสคีมา S ₁ = { A , D }, S ₂ = { A , C } และ S ₃ = { B , C , D } การตรวจสอบว่าการแยกนี้เป็นการแยกแบบไม่สูญเสียข้อมูลหรือไม่ สามารถทำได้โดยการดำเนินการติดตามดังแสดงด้านล่าง

ตารางแสดงโครงสร้างเบื้องต้นสำหรับการแยกส่วนนี้คือ:

แถวแรกแสดงถึง S ₁ส่วนประกอบสำหรับคุณลักษณะAและDจะไม่มีตัวห้อย และส่วนประกอบสำหรับคุณลักษณะBและCจะมีตัวห้อยi = 1 แถวที่สองและสามจะเติมข้อมูลในลักษณะเดียวกันด้วย S ₂และ S ₃ตามลำดับ

เป้าหมายของการทดสอบนี้คือการใช้F ที่กำหนดให้ เพื่อพิสูจน์ว่าt = ( a , b , c , d ) อยู่ใน Rจริงๆในการทำเช่นนั้น เราสามารถไล่ตามตารางได้โดยการใช้ FD ในFเพื่อเทียบสัญลักษณ์ในตาราง ตารางสุดท้ายที่มีแถวที่เหมือนกับtหมายความว่าทูเปิลt ใดๆ ในการเชื่อมต่อของการฉายภาพนั้นเป็นทูเปิลของ R จริงๆใน การ ทำการทดสอบการไล่ตาม ขั้นแรกให้แยก FD ทั้งหมดในFออกเพื่อให้แต่ละ FD มีแอตทริบิวต์เดียวทางด้านขวามือของ "ลูกศร" (ในตัวอย่างนี้Fยังคงไม่เปลี่ยนแปลงเนื่องจาก FD ทั้งหมดมีแอตทริบิวต์เดียวทางด้านขวามืออยู่แล้ว: F = { A → B , B → C , CD → A })

เมื่อเทียบสัญลักษณ์สองตัว ถ้าตัวหนึ่งไม่มีตัวห้อย ให้เปลี่ยนตัวอีกตัวให้มีตัวห้อยเหมือนกัน เพื่อให้ตารางสุดท้ายมีแถวที่เหมือนกับt = ( a , b , c , d ) ทุกประการ ถ้าทั้งสองตัวมีตัวห้อยของตัวเอง ให้เปลี่ยนตัวใดตัว _{หนึ่ง}เป็นอีกตัวหนึ่ง อย่างไรก็ตาม เพื่อหลีกเลี่ยงความสับสน ควรเปลี่ยนทุกตัวที่ปรากฏ ก่อนอื่น ให้ใช้A → Bกับตาราง แถวแรกคือ ( a , b1 , c1 , d ) โดยที่aไม่มีตัวห้อย และ_{b1 มีตัวห้อยเป็น 1}เมื่อเปรียบเทียบแถวแรกกับแถวที่สอง ให้เปลี่ยนb2เป็น_{b1 เนื่องจาก}แถวที่สามมี3 _{ดังนั้น} b ในแถว ที่ สาม จึงยังคงเหมือนเดิม ตารางที่ได้คือ:

จากนั้นพิจารณาB → Cทั้งแถวแรกและแถวที่สองมีb ₁และสังเกตว่าแถวที่สองมีc ที่ไม่มีตัวห้อย ดังนั้น แถวแรกจะเปลี่ยนเป็น ( a , b ₁ , c , d ) จากนั้นตารางที่ได้จะเป็นดังนี้:

ทีนี้ลองพิจารณาCD → A ดู แถวแรกมีc ที่ไม่มีตัวห้อย และd ที่ไม่มีตัวห้อย ซึ่งเหมือนกับในแถวที่สาม นั่นหมายความว่าค่า A สำหรับแถวที่หนึ่งและแถวที่สามต้องเหมือนกันด้วย ดังนั้น ให้เปลี่ยน₃ในแถวที่สามเป็นaผลลัพธ์ที่ได้คือ:

ณ จุดนี้ โปรดสังเกตว่าแถวที่สามคือ ( a , b , c , d ) ซึ่งเหมือนกับtดังนั้น นี่คือตารางสุดท้ายสำหรับการทดสอบการไล่ล่าด้วยRและF ที่กำหนดให้ ดังนั้น เมื่อใดก็ตามที่Rถูกฉายลงบน S1 _, S2 _และ S3 _แล้ว นำ มารวมกัน ผลลัพธ์จะอยู่ในRโดยเฉพาะอย่างยิ่ง ทูเปิลที่ได้จะเหมือนกับทูเปิลของRที่ถูกฉายลงบน { B , C , D }

• Sergio Greco; Francesca Spezzano; Cristian Molinaro (2012). ข้อมูลที่ไม่สมบูรณ์และการพึ่งพาข้อมูลในฐานข้อมูลเชิงสัมพันธ์ . สำนักพิมพ์ Morgan & Claypool. ISBN 978-1-60845-926-1.