Độ phức tạp của bài toán định trị truy vấn

Bài trước: Logic bậc nhất và truy vấn hội

Bài sau: Thuật toán Yannakakis

Bài trước lược khảo các khái niệm và kết quả của logic bậc nhất và định nghĩa truy vấn hội (conjunctive queries). Một cách vắn tắt, lớp các truy vấn hội là lớp các truy vấn có dạng

$\displaystyle \varphi(x_1,\dots,x_k) = \exists x_{k+1},\dots, \exists x_n R_1 \wedge R_2 \wedge \cdots \wedge R_r,$

trong đó ${x_1,\dots,x_k}$ là các biến tự do, ${x_{k+1},\dots,x_n}$ là các biến bị giới hạn, và ${R_1,\dots, R_r}$ là các công thức nguyên tử (atomic formula). Các truy vấn hội tương đương với các phát biểu SQL dạng select ... from ... where ... mà phần where là hội của các đẳng thức đơn giản. Một cách đơn giản khác để biểu diễn các truy vấn hội là dùng ngôn ngữ datalog: các truy vấn hội biểu diễn bằng datalog có thể viết dưới dạng

$\displaystyle q(x_1,\dots,x_k) \text{ :- } R_1(\bar A_1) \wedge \cdots \wedge R_r(\bar A_r)$

trong đó các biến tự do nằm trong phần “đầu” (head) của truy vấn datalog ${q}$ , và ${R_1,\cdots,R_r}$ là các nguyên tử (atom) trong phần “thân” (body) của truy vấn. Đa số các truy vấn vào CSDL hiện nay là truy vấn hội, cho nên lớp các truy vấn hội là lớp các truy vấn cực kỳ quan trọng cả về mặt thực tế lẫn lý thuyết.

1. Độ phức tạp của định trị truy vấn hội

Định nghĩa 1 (CQ và BCQ) Bài toán định trị truy vấn hội là bài toán sau đây: cho một cấu trúc ${\mathcal A = (A, \{R^{\mathcal A} \ | \ R \in \tau\})}$ của bộ từ vựng quan hệ ${\tau}$ , và một truy vấn hội ${q}$ , liệt kê tất cả các bộ ${(a_1,\dots,a_k) \in A^k}$ sao cho ${\mathcal A \models q(a_1,\dots,a_k)}$ .

Trường hợp đặc biệt khi ${k=0}$ thì ${q}$ được gọi là truy vấn hội có/không (Boolean conjunctive query). Câu trả lời của một truy vấn hội có/không là có hoặc không: có nếu tồn tại ${(a_1,\dots,a_k)}$ sao cho ${\mathcal A \models q(a_1,\cdots, a_k)}$ và không nếu điều ngược lại xảy ra.

Để phân biệt trường hợp ${k=0}$ và ${k>0}$ , ta gọi bài toán cho trường hợp ${k=0}$ là bài toán định trị truy vấn hội có/không (Boolean conjunctive query problem, viết tắt là bài toán BCQ), và bài toán cho trường hợp ${k>0}$ là bài toán CQ.

Thông thường, trong phân tích độ phức tạp của một bài toán ta trước hết giới hạn bài toán về một phiên bản có/không nào đó (decision version) để tránh ảnh hưởng của kích thước output đến kết quả độ phức tạp. Do đó, đầu tiên ta sẽ xét độ phức tạp của bài toán BCQ. Ngoài bài toán BCQ còn hai bài toán nữa cũng đều rất quan trọng trong CSDL.

Định nghĩa 2 (CQE) Cho hai truy vấn hội ${q_1}$ và ${q_2}$ , hỏi chúng có tương đương với nhau không? Nghĩa là, có phải là ${q_1(\mathcal A) = q_2(\mathcal A)}$ với mọi cấu trúc ${\mathcal A}$ hay không? Bài toán này gọi là bài toán truy vấn hội tương đương (Conjunctive Query Equivalence — viết tắt là CQE).

Tầm quan trọng của bài toán này trong CSDL có lẽ là hiển nhiên; ví dụ một trong những cách tối ưu hoá việc xử lý truy vấn là ta tìm một truy vấn tương đương sao cho định trị nó tốn ít thời gian hơn truy vấn cần định trị.

Định nghĩa 3 (CQC) Cho hai truy vấn hội ${q_1}$ và ${q_2}$ , bài toán truy vấn hội chứa trong nhau (Conjunctive Query Containment — CQC) hỏi có phải ${q_1(\mathcal A) \subseteq q_2(\mathcal A)}$ với mọi cấu trúc ${\mathcal A}$ hay không. Nếu ${q_1}$ và ${q_2}$ là các truy vấn hội có/không thì câu hỏi là có phải ${q_1(\mathcal A) \Rightarrow q_2(\mathcal A)}$ với mọi cấu trúc ${\mathcal A}$ hay không?

May mà ta chỉ cần giải quyết một trong ba bài toán BCQ, CQE, và CQC là đủ, tại vì chúng tương đương với nhau. Trước hết, ${q_1 \equiv q_2}$ nếu và chỉ nếu ${q_1 \subseteq q_2}$ và ${q_2 \subseteq q_1}$ . Kế đến, ${q_1 \subseteq q_2}$ nếu và chỉ nếu ${q_1 \equiv q_1 \wedge q_2}$ . Do đó, CQC và CQE là tương đương.

Từ năm 1977, một bài báo kinh điển của Chandra và Merlin (STOC) đã chứng minh rằng bài toán BCQ là NP-đầy đủ, và rằng cả BCQ và CQC đều tương đương với một bài toán khác gọi là bài toán đồng cấu (Homomorphism problem). Ta sẽ định nghĩa bài toán đồng cấu và chứng minh định lý Chandra-Merlin dưới đây.

Lớp các truy vấn hội là tập con của lớp các truy vấn bậc nhất (FO queries), có thể biểu diễn bằng phép tính quan hệ (relational calculus). Từ bài báo của Codd năm 1972 (“Relational Completeness of Data Base Sublanguages”) ta đã biết là lớp các truy vấn bậc nhất tương đương với lớp các truy vấn biểu diển bằng đại số quan hệ (relational algebra). Và, độ phức tạp của chúng là PSPACE-đầy đủ. Do đó, giả sử ${\mathbf{NP} \not\subseteq \mathbf{PSPACE}}$ (hầu hết các nhà lý thuyết đều tin là giả thiết này đúng nhưng chưa chứng minh được), thì ngôn ngữ của các truy vấn bậc nhất và đại số quan hệ hùng mạnh hơn hẳn ngôn ngữ của các truy vấn hội.

Nếu ta xét các truy vấn bậc nhất hoặc các truy vấn của đại số quan hệ thì bài toán truy vấn tương đương là không quyết định được (undecidable). Tại vì, câu hỏi liệu ${q = \emptyset?}$ hay không, theo định lý Traktenbrots đã là không quyết định được. (Xem thêm bài trước.)

2. Độ phức tạp biểu thức và độ phức tạp dữ liệu của các truy vấn

Chứng minh rằng bài toán BCQ là NP-khó không phức tạp gì mấy. Ví dụ, ta có thể chuyển giản (reduce) từ bài toán tô 3 màu về bài toán BCQ như sau. Gọi ${G=(V,E)}$ là một đồ thị đơn bất kỳ. Ta xây dựng một cấu trúc ${\mathcal A}$ trên miền ${\{1,2,3\}}$ với chỉ một quan hệ

$\displaystyle R = \{(1,2),(2,1), (1,3), (3,1), (2,3), (3,2)\}$

Truy vấn hội của ta gồm ${|V|}$ biến, mỗi đỉnh ${v}$ của ${G}$ là một biến. Câu hỏi là

$\displaystyle q \text{ :- } \wedge_{uv\in E} Ruv.$

Dễ thấy rằng truy vấn này có câu trả lời có nếu và chỉ nếu đồ thị ${G}$ tô được bằng 3 màu. Bài toán tô 3 màu là bài toán NP-khó, vì thế bài toán BCQ là NP-khó.

Có một điểm hơi khó chịu ở phép chuyển giản trên: cái CSDL (cấu trúc ${\mathcal A}$ ) rất nhỏ; độ phức tạp của phép truy vấn nằm hoàn toàn ở bản thân phép truy vấn chứ không phụ thuộc vào kích thước của CSDL. Trên thực tế, đa số các phép truy vấn vào CSDL có kích thước nhỏ hơn bản thân CSDL rất nhiều. Ví dụ, một truy vấn SQL có kích thước cùng lắm là vài trăm bytes, còn CSDL thì có thể cả nghìn GB.

Năm 1982, Vardi (STOC) đề xuất rằng ta phải tách biệt độ phức tạp truy vấn và độ phức tạp dữ liệu của một phép truy vấn vào CSDL. Khi xét độ phức tạp truy vấn thì ta giả sử kích thước của CSDL là cố định. Khi xét độ phức tạp dữ liệu thì ta giả sử kích thước phép truy vấn là cố định. Động cơ thực tế là, nếu ta truy vấn vào CSDL dân số, 10 năm làm một lần, thì CSDL là cố định. Nếu ta truy vấn vào CSDL giá cả chứng khoán thì có khả năng là một truy vấn được lập lại nhiều lần trong khi dữ liệu lại thay đổi nhanh. Ngoài ra, do độ phức tạp truy vấn phụ thuộc rất nhiều vào cách mà ta mã hoá cái truy vấn. Ví dụ, truy vấn ${R \times R \times \cdots \times R}$ có kích thước lớn hơn truy vấn ${R^{100}}$ rất nhiều. Do đó, Vardi đề nghị đổi độ phức tạp truy vấn thành độ phức tạp biểu thức (expression complexity) của một truy vấn.

Nếu chỉ dùng phép chuyển giản từ bài toán tô 3 màu ở trên thì rõ ràng là độ phức tạp biểu thức của bài toán BCQ là NP-khó, nhưng phép chuyển giản không chứng minh được rằng độ phức tạp dữ liệu của bài toán BCQ là NP-khó. Thậm chí, Vardi chứng minh rằng độ phức tạp dữ liệu của BCQ nằm trong LOGSPACE (nhớ rằng ${\mathbf{L \subseteq NL \subseteq P}}$ ), do đó bài toán thuộc lớp P nếu ta giả sử kích thước của truy vấn là hằng số. Còn độ phức tạp dữ liệu của các truy vấn bậc nhất là LOGSPACE-đầy đủ.

Gần đây hơn một chút, năm 1995, Vardi cũng quan sát rằng nếu ta chỉ dùng tổng số biến của truy vấn để đo độ phức tạp thì kết quả khác đi một chút. Ta sẽ quay lại với loại độ phức tạp này sau, khi nào có dịp.

3. Độ phức tạp tham số của các truy vấn

Tất nhiên, giả thiết rằng biểu thức của truy vấn có kích thước cố định cũng không thực tế. Với một truy vấn kích thước ${|q|}$ vào CSDL ${\mathcal A}$ thì một thuật toán chạy trong thời gian ${|\mathcal A|^{O(|q|)}}$ vẫn là thuật toán không khả thi. Năm 1997, Papadimitriou và Yannakakis phân tích độ phức tạp tham số (parameterized complexity) của các truy vấn. Bài báo này được giải thưởng bài báo tốt nhất của hội nghị PODS 1997. Động cơ của việc xét độ phức tạp tham số rất đơn giản: như đã nêu, một thuật toán chạy trong thời gian ${O(|\mathcal A|^{|q|})}$ rõ ràng là không tốt bằng thuật toán chạy trong thời gian ${O(2^{|q|} \cdot |\mathcal A|^c)}$ với ${c}$ là một hằng số nào đó, kể cả khi ta xem kích thước của truy vấn ${q}$ là cố định.

Để hiểu rõ độ phức tạp tham số, ta có thể tham khảo Parameterized Complexity của Downey và Fellows, hoặc quyển Parameterized Complexity Theory của Jörg Flum. Xem thêm trang này.

Đại khái, xét bài toán ${k}$ -Clique: cho một đồ thị ${G}$ , hỏi ${G}$ có một clique với kích thước ${k}$ hay không. Bài toán này tất nhiên là giải được trong thời gian ${O(|G|^k)}$ và do đó nếu ${k}$ là một hằng số thì nó nằm trong lớp P. Tuy nhiên, cũng như trên một thuật toán giải ${k}$ -clique trong thời gian ${O(f(k) \cdot |G|^c)}$ với ${c}$ là một hằng số nào đó và ${f}$ là một hàm tính được vẫn có thể nhanh hơn thuật toán chạy trong thời gian ${O(|G|^k)}$ nhiều. Một bài toán với tham số ${k}$ giải được trong thời gian ${O(f(k) \cdot n^c)}$ với một hằng số ${c}$ được gọi là bài toán khả thi tham số cố định (fixed parameter tractable — FPT). Lưu ý rằng FPT không phải là Food Processing Technologies.

Rõ ràng là, kể cả ở bên ngoài ngữ cảnh của các truy vấn trong CSDL thì việc phân lớp xem bài toán nào thuộc lớp FPT và bài toán nào không là một vấn đề rất quan trọng trong lý thuyết độ phức tạp nói chung. Downey và Fellows giới thiệu một hệ thống cấp bậc (hierarchy) của các lớp bài toán tham số, gọi là \em hệ thống cấp bậc ${W}$ gồm các lớp

$\displaystyle \text{FPT} = W[0] \subseteq W[1] \subseteq W[2] \subseteq \cdots W[\text{poly}].$

Càng lên cao trên hệ thống cấp bậc này thì càng ít khả năng là bài toán thuộc lớp FPT.

Papadimitriou và Yannakakis chứng minh rằng BCQ là ${W[1]}$ -đầy đủ, và lớp các truy vấn bậc nhất là ${W[t]}$ -đầy đủ với mọi ${t}$ . ${W[1]}$ -đầy đủ tương tự như NP-đầy đủ của thế giới các bài toán tham số. Do đó, rất khó có khả năng là tồn tại một thuật toán cho bài BCQ với thời gian chạy ${O(f(|q|)\cdot |\mathcal A|^c)}$ với một hằng số ${c}$ và hàm tính được ${f}$ bất kỳ!

4. Bài toán đồng cấu

Xét hai cấu trúc ${\mathcal A}$ và ${\mathcal B}$ trên cùng một bộ từ vựng ${\tau}$ . Trong đó, miền của ${\mathcal A}$ là tập ${A}$ và của ${\mathcal B}$ là tập ${B}$ . Một hàm số ${h : A \rightarrow B}$ được gọi là một đồng cấu (homomorphism) từ ${\mathcal A}$ vào ${\mathcal B}$ nếu và chỉ nếu, với mọi bộ ${a_1\cdots a_m \in A^m}$ và mọi ký hiệu quan hệ ${R}$ bậc ${m}$ của ${\tau}$ , ta có

$\displaystyle R^{\mathcal A}a_1\cdots a_m \Longrightarrow R^{\mathcal B}h(a_1)\cdots h(a_m).$

Cho một cấu trúc ${\mathcal A}$ tuỳ ý, định nghĩa truy vấn chuẩn (cannonical query) của ${\mathcal A}$ là truy vấn có/không ${q^{\mathcal A}}$ mà trong đó mỗi thành viên ${a\in A}$ được xem là một biến số, và nếu ${R^{\mathcal A} a_1\cdots a_m \in A^m}$ thì ta có một nguyên tử ${R^{\mathcal A}}$ với các biến ${a_1,\cdots, a_m}$ nằm trong phần thân của truy vấn ${q^{\mathcal A}}$ .

Ví dụ, xét cấu trúc đồ thị ${\mathcal G = (V, E)}$ với ${V = \{a,b,c\}}$ và ${E = \{ab, ba, bc, ca, ac, ca\}}$ , thì truy vấn chuẩn ${q^{\mathcal A}}$ là truy vấn có/không

$\displaystyle q^{\mathcal A} = Eab \wedge Eba \wedge Eac \wedge Eca \wedge Ebc \wedge Eca.$

Ngược lại, xét một truy vấn hội có/không ${q}$ với tập biến ${\text{var}(q)}$ và các “conjunct” ${R_i(\bar A_i)}$ , thì ta có thể xây dựng một cấu trúc chuẩn ${\mathcal A^q}$ với miền ${A = \text{var}(q)}$ và các quan hệ ${R_i(\bar A_i)}$ . Ví dụ, giả sử ${q = Eab \wedge Eac \wedge Ebc}$ thì cấu trúc chuẩn ${\mathcal A^q = (A = \{a,b,c\}, E = \{ab, ac, ca\})}$ .

Năm 1977, Chandra và Merlin chứng minh định lý sau đây. Từ định lý và bài tập sau định lý ta thấy rằng bài toán đồng cấu và bài toán CQC là tương đương nhau.

Định lý 4 Cho hai cấu trúc ${\mathcal A, \mathcal B}$ trên cùng bộ từ vựng ${\tau}$ . Ba điều sau đây là tương đương nhau:

Tồn tại một phép đồng cấu ${h}$ từ ${\mathcal A}$ vào ${\mathcal B}$
${\mathcal B \models q^{\mathcal A}}$ , nghĩa là nếu ta truy vấn CSDL ${\mathcal B}$ với câu hỏi ${q^{\mathcal A}}$ thì câu trả lời là có!
${q^{\mathcal B} \subseteq q^{\mathcal A}}$

Chứng minh: Trước hết ta chứng minh (1) và (2) là tương đương. Giả sử tồn tại một phép đồng cấu ${h}$ từ ${\mathcal A}$ vào ${\mathcal B}$ . Ta phải chứng minh rằng truy vấn ${q^{\mathcal A}}$ vào CSDL ${\mathcal B}$ cho câu trả lời là có. Truy vấn này cho câu trả lời có nếu và chỉ nếu có một ánh xạ ${h}$ từ tập ${A}$ các biến của truy vấn vào tập miền ${B}$ của CSDL (hay cấu trúc) ${\mathcal B}$ sao cho, với mọi conjunct ${Ra_1\cdots a_m}$ của ${q^{\mathcal A}}$ ta có ${R^{\mathcal B}h(a_1)\cdots h(a_m)}$ . Nhưng đây chính là định nghĩa của phép đồng cấu từ ${\mathcal A}$ vào ${\mathcal B}$ . Chiều ngược lại cũng rõ ràng là đúng. Nói tóm lại, phát biểu (2) chẳng qua là một cách khác để nói phát biểu (1).

Bây giờ giả sử (1) đúng, ta chứng minh (3). Gọi ${\mathcal C}$ là một cấu trúc bất kỳ, ta phải chứng minh rằng nếu câu trả lời cho truy vấn ${q^{\mathcal B}}$ là có thì câu trả lời cho ${q^{\mathcal A}}$ cũng là có. Khi câu trả lời cho ${q^{\mathcal B}}$ là có thì tồn tại một ánh xạ ${f : B \rightarrow C}$ sao cho ${R^{\mathcal B}b_1\cdots b_m}$ nếu và chỉ nếu ${R^{\mathcal C}f(b_1)\cdots f(b_m)}$ . Bây giờ xét ánh xạ ${f \circ h}$ . Giả sử ${R^{\mathcal A}a_1\cdots a_m}$ , thì do ${h}$ là phép đồng cấu ta có ${R^{\mathcal B}h(a_1)\cdots h(a_m)}$ , và do đó ${R^{\mathcal C}f(h(a_1)) \cdots f(h(a_m))}$ . Tóm lại nếu ${\mathcal C \models q^{\mathcal B}}$ thì ${\mathcal C \models q^{\mathcal A}}$ .

Ngược lại, giả sử ${q^{\mathcal B} \subseteq q^{\mathcal A}}$ . Xét CSDL ${\mathcal B}$ . Rõ ràng là ${\mathcal B \models q^{\mathcal B}}$ dùng phép gán “biến” ${b \in B}$ sang phần tử ${b \in B}$ của CSDL. Do đó ${\mathcal B \models q^{\mathcal A}}$ . $\Box$

Bài tập 1 Cho hai truy vấn hội ${q_1}$ và ${q_2}$ . Chứng minh rằng ba điều sau đây là tương đương nhau:

${q_1 \subseteq q_2}$
Tồn tại mội phép đồng cấu từ ${\mathcal A^{q_2}}$ vào ${\mathcal A^{q_1}}$
${\mathcal A^{q_1} \models q_2}$ , nghĩa là truy vấn ${q_2}$ vào CSDL ${\mathcal A^{q_1}}$ thì câu trả lời là có!.

Ví dụ, cho một (cấu trúc) đồ thị ${G=(V,E^G)}$ trên bộ từ vựng ${\tau = E}$ . Nếu tồn tại một phép đồng cấu từ ${G}$ vào cấu trúc đồ thị ${K_3 = (\{a,b,c\}, \{ab,ba,ac,ca,bc,cb\})}$ thì đồ thị ${G}$ có thể tô được bằng ba màu! Ví dụ này cho thấy sức mạnh biểu diễn của phép đồng cấu, và nó cũng cho thấy bài toán tính xem có tồn tại phép đồng cấu giữa hai cấu trúc cho trước hay không là bài toán NP-khó.

Sau này, ở hội nghị PODS 1998, Kolaitis và Vardi chứng minh rằng các bài toán đồng cấu, BCQ, CQC, CQE, đều tương đương với bài toán thoả mãn ràng buộc (constraint satisfaction problem — CSP). Điều này cho thấy các bài toán CSDL ta đã thảo luận thuộc về một lớp các bài toán cực kỳ quan trọng trong KHMT nói chung. Ngoài ra, năm 2004 McMahan et al. dùng các kỹ thuật sẵn có giải quyết cái bài toán CSPs để định trị các truy vấn giao với một số kết quả khả quan.

Độ phức tạp của bài toán định trị truy vấn

Post a Comment Cancel reply

Thông điệp ngắn

Phản hồi mới

Bài mới

Chuyên Mục

Kho bài

Báo chí

Bảo mật

Blog Việt

Chưa phân loại

Giáo dục

Kỹ thuật

Khoa học khác

Kinh tế, luật pháp, xã hội

Lý thuyết & thuật toán

Mạng

Não học

Toán học

Vật Lý