Division ใน Relational Algebra

การหาร (DIVISION) ใน relational algebra อธิบายง่ายๆ คือการเอาตารางมา join กันแล้วนับว่าแต่ละ pk ของตารางตัวตั้ง มี row เท่ากับตารางตัวหารหรือไม่ ถ้าครบก็ตัด column ที่ปรากฏในตารางตัวหารทิ้งแล้วยุบรวม row ซ้ำด้วย pk เช่นเรามีข้อมูล

table: students
------+------+-------
 name | subj | grade 
------+------+-------
 bar  | code | A
 foo  | code | C+
 foo  | trek | A
 qux  | code | B+
 qux  | math | A
 qux  | trek | A
------+------+-------

table: colleges
-----------+------
  campus   | subj 
-----------+------
 leetademy | code
 leetademy | trek
 hack-cool | code
 hack-cool | math
-----------+------

คำสั่ง SQL ของการหารก็จะมีหน้าตาประมาณ

SELECT *
FROM   students
DIVISION (
    SELECT subj
    FROM   colleges
    WHERE  campus = 'leetademy'
) AS leetademy_courses

ซึ่งให้ผลลัพท์ออกมาคือ

------
 name 
------
 foo
 qux
------

---

ปัญหาของการหารคือ DBA แทบทั้งหมดไม่มีคำสั่งนี้ให้ใช้ (ต่างจากการลบ (MINUS) ที่ยังมีบ้าง แม้บางเจ้าจะเปลี่ยนชื่อเป็น EXCEPT ก็ตาม) เพราะมันเป็นท่าที่เปลืองทรัพยากรมาก แถมไม่ได้ใช้กันบ่อยๆ เสียด้วย ...ซึ่งจะว่าไปแล้วมันก็ดูไม่ใช่ปัญหาเลยนี่หน่า

อย่างไรก็ตามปัญหาจริงๆ คือมันเป็นท่าที่อาจารย์ database ส่วนใหญ่ชอบเอาไปออกสอบ ทำให้เราต้องหาท่าอ้อมๆ ที่ให้ผลลัพท์แบบเดียวกันมาใช้แทน

การจะเข้าใจมันได้ ถ้าคิดแบบ programming ก็แค่ดูว่า set ที่เป็นตัวตั้งหารนั้นเป็น superset ของ set ที่ถูกหารหรือเปล่า

students_set = defaultdict(set)
for name, subj, grade in students:
    students_set[name].add(subj)

colleges_set = defaultdict(set)
for campus, subj in colleges:
    colleges_set[campus].add(subj)

output = set()
for name, subj_set in students_set.items():
    if subj_set >= colleges_set['leetademy']:
        output.add(name)
print(output)

แต่การทำงานบน database เรามักเขียนพวกนี้ทั้งหมดให้เป็น one-liner เพื่อที่จะรับประกันว่าระหว่างการ query จะไม่เกิด race condition กับ query อื่นๆ สิ่งที่ต้องทำก่อนอื่นใดคือพยายามกำจัดการสร้าง set ของข้อมูลล่วงหน้าซะ

ในที่นี้ ขั้นแรกเราจะกำจัดการสร้าง colleges_set โดยวน loop ใน colleges ทุกตัวดูว่าแต่ละ subj มีใน students_set หรือเปล่า

def learnt_all(name):
    for campus, subj in colleges:
        if campus == 'leetademy':
            if subj not in students_set[name]:
                return False
    return True

output = set()
for name, _, _ in students:
    if learnt_all(name):
        output.add(name)
print(output)

ขั้นต่อมาก็กำจัด students_set โดย loop เข้า students ดูว่านักเรียนที่ชื่อ name ได้เรียนวิชา subj แล้วหรือยัง

def learnt(name, subj):
    for student_name, student_subj, _ in students:
        if student_name == name and student_subj == subj:
            return False
    return True

def learnt_all(name):
    for campus, subj in colleges:
        if campus == 'leetademy':
            if learnt(name, subj):
                return False
    return True
    
output = set()
for name, _, _ in students:
    if learnt_all(name):
        output.add(name)
print(output)

เนื่องจากในฟังก์ชัน learnt กับ learnt_all จะคืนค่า False ทันทีที่เข้าเงื่อนไขครบ แต่จะคืนค่า True หลังจากจบ loop เท่านั้น เราสามารถเขียนตรงนี้ใหม่ด้วย generator แล้ว wrap ด้านนอกด้วย not any(...) เช่นนี้

def inverse_learnt(name, subj):
    for student_name, student_subj, _ in students:
        if student_name == name and student_subj == subj:
            yield True

def inverse_learnt_all(name):
    for campus, subj in colleges:
        if campus == 'leetademy':
            if not any(inverse_learnt(name, subj)):
                yield True

output = set()
for name, _, _ in students:
    if not any(inverse_learnt_all(name)):
        output.add(name)
print(output)

พอทุกอย่างเป็น single-statement และ generator คราวนี้ก็ง่ายที่จะทำ one-liner แล้ว ... จับมาเขียนสวยๆ ได้แบบนี้

print({
    name
    for name, _, _ in students
    if not any(
        True
        for campus, subj in colleges
        if campus == 'leetademy'
        and not any(
            True
            for student_name, student_subj, _ in students
            if student_name == name
            and student_subj == subj
        )
    )
})

เห็น code นี้แล้วคงเดาได้ไม่ยากว่า พอเอาเขียนเป็น SQL คงหนีไม่พ้น

SELECT DISTINCT name
FROM   students AS s
WHERE  NOT EXISTS (
    SELECT *
    FROM   colleges AS c
    WHERE  campus = 'leetademy'
    AND    NOT EXISTS (
        SELECT *
        FROM   students AS ss
        WHERE  ss.name = s.name
        AND    ss.subj = c.subj
    )
)

อ้างอิง

• Steven Hauser: SQL Relational Algebra Examples
• Gregor Ulm: Relational Division in SQL The Easy Way
• Victor M. Matos; Rebecca Grasser (1995). "A Simpler (and Better) SQL Approach to Relational Division". Journal of Information Systems Education 13(2): 85–88. ISBN 0-471-18074-2.