Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Đối Xứng Trong Xử Lý Truy Vấn Được Định Hướng Theo Mục Tiêu Trong Cơ Sở Dữ Liệu Khấu Trừ Phân Tách
Tóm tắt
Các quy trình trả lời truy vấn từ dưới lên có xu hướng khám phá một không gian tìm kiếm lớn hơn nhiều so với những gì thực sự cần thiết. Các phương pháp xử lý từ trên xuống sử dụng truy vấn để thực hiện một tìm kiếm tập trung hơn, có thể mang lại hiệu quả tốt hơn trong việc trả lời truy vấn. Cho một cơ sở dữ liệu khấu trừ phân tách, DB, và một truy vấn, Q, chúng tôi thiết lập một mối liên kết mạnh mẽ giữa việc sinh mô hình và khả năng suy diễn mệnh đề trong hai đại diện khác nhau của DB và Q. Điều này cho phép chúng tôi sử dụng quy trình từ dưới lên để đánh giá Q trên DB một cách từ trên xuống. Phương pháp này không yêu cầu viết lại sâu rộng lý thuyết đầu vào và không giới thiệu bất kỳ tọa độ nào mới. Thay vào đó, nó dựa trên một nguyên lý đối xứng nhất định để diễn giải các kết nối lôgíc. Phép biến đổi đối xứng được thực hiện bằng cách đảo ngược hướng của các mũi tên hàm ý trong các mệnh đề đại diện cho cả lý thuyết và sự phủ định của truy vấn. Việc áp dụng một quy trình từ dưới lên tổng quát vào bộ mệnh đề đã biến đổi dẫn đến việc trả lời truy vấn từ trên xuống. Dưới các điều kiện thuận lợi, việc gia tăng hiệu quả là đáng kể, như đã được chứng minh bởi các thử nghiệm ban đầu của chúng tôi. Chúng tôi đưa ra ý nghĩa lôgíc của phép biến đổi đối xứng và chỉ ra các điều kiện và nguồn gốc nâng cao hiệu quả. Chúng tôi cho thấy cách tiếp cận đối xứng có thể được sử dụng cho việc trả lời truy vấn tinh vi bằng cách xác định các điều kiện tối thiểu (các cập nhật yếu nhất) đối với DB dưới điều kiện mà Q trở nên có thể suy diễn. Điều này được chứng minh là hữu ích cho việc cập nhật chế độ xem trong các cơ sở dữ liệu khấu trừ phân tách cũng như cho các ứng dụng thú vị khác.
Từ khóa
#cơ sở dữ liệu khấu trừ phân tách #truy vấn từ trên xuống #hiệu quả #biến đổi đối xứng #suy diễn mệnh đềTài liệu tham khảo
Bancilhon, F., Sagiv, Y. and Ullman, J.: Magic sets and other strange ways to implement logic programs, in Proceedings of the 5th ACM SIGMOD-SIGART Symposium on Principles of Database Systems, 1988, pp. 1-15.
Baumgartner, P.: Hyper tableaux - the next generation, in Proceedings of TABLEAUX:98, LNCS 1397, Springer-Verlag, 1998, pp. 60-76.
Baumgartner, P.: FDPLL - A first-order Davis-Putnam-Logemann-Loveland procedure, in Proceedings of CADE2000, pp. 200-219.
Baumgartner, P., Furbach, U. and Niemelä, I.: Hyper tableaux, in Proceedings of JELIA96, LNAI 1126, Springer-Verlag, 1996.
Bry, F.: Query evaluation in recursive databases: Bottom-up and top-down reconciled, in Data & Knowledge Engineering, 1990, pp. 289-312.
Bry, F. and Yahya, A.: Minimal model generation with positive unit hyper-resolution tableaux, in Proceedings of the 5th Workshop on Theorem Proving with Analytic Tableaux and Related Methods, LNAI 1071, Springer-Verlag, 1996, pp. 143-159.
Bry, F. and Yahya, A.: Positive unit hyper-resolution tableaux and their application to minimal model generation, J. Automated Reasoning 25(1) (2000), 35-82.
Codish, M.: Efficient goal directed bottom-up evaluation of logic programs, J. Logic Programming 38(3) (1999), 354-370.
Demolombe, R.: An efficient strategy for non-Horn deductive databases, Theoret. Comput. Sci. 78(1991), 245-259.
Eiter, T., Leone, N., Mateis, C., Pfeifer, G. and Scarcello, F.: Progress report on the disjunctive deductive database system dlv, in Proceedings of FQAS 1998, LNAI 1495, Springer, 1998, pp. 148-163.
Fernández, J. A. and Minker, J.: Bottom-up computation of perfect models for disjunctive stratified theories, J. Logic Programming 25(1) (1995), 33-50.
Fuchs, D. and Fuchs, M.: Cooperation between top-down and bottom-up theorem provers, J. Artif. Intell. Res. 10(1999), 169-198.
Grant, J., Horty, J., Lobo, J. and Minker, J.: View updates in disjunctive deductive databases, J. Automated Reasoning 11(1993), 249-267.
Hasegawa, R., Inoue, K., Ohta, Y. and Koshimura, M.: Nonhorn magic sets to incorporate topdown inference into bottom-up theorem proving, in Proceedings of CADE97, 1997, pp. 176-190.
Henschen, L. and Naqvi, S.: On compiling queries in recursive first-order databases, J. ACM 31(1) (1984), 47-86.
Inoue, K. and Sakama, C.: A fixpoint characterization of abductive logic programs, J. Logic Programming 27(1996), 107-136.
Johnson, C. A.: Top-down deduction in indefinite deductive databases, in Journ?s Bases de Donn?s Avanc?s, Toulouse, France, 1993, pp. 119-138.
Letz, R. and Stenz, G.: DCTP - A Disconnection Calculus Theorem Prover-System (Abstract), in Proceedings of IJCAR 2001, Siena, Italy, June 2001.
Lloyd, J. W.: Foundations of Logic Programming, 2nd edn, Springer-Verlag, 1987.
Lobo, J., Minker, J. and Rajasekar, A.: Semantics for Horn and disjunctive logic programs, J. Theoret. Comput. Sci. 86(1991), 93-106.
Lobo, J., Minker, J. and Rajasekar, A.: Foundations of Disjunctive Logic Programming, MIT Press, 1992.
Loveland, D. W., Reed, D. and Wilson, D.: Satchmore: Satchmo with relevancy, J. Automated Reasoning 14(1995), 349-363.
Loveland, D. W. and Yahya, A.: SATCHMOREBID: SATCHMO(RE) with BIDirectional Relevancy, Preprint.
Lu, W.: Nonmonotonic reasoning based on minimal model generation and its implementation, Ph.D. thesis, Koblenzer Schriften zur Informatik 11, Fölbach Verlag, Koblenz, 1999.
Manthey, R. and Bry, F.: Satchmo: A theorem prover implemented in Prolog, in J. L. Lassez (ed.), Proc. of the 9th CADE, 1988, pp. 456-459.
Minker, J.: On indefinite databases and the closed world assumption, in Lecture Notes in Comput. Sci.138, Springer, 1982, pp. 292-308.
Niemelä, I.: A tableau calculus for minimal model reasoning, in Proceedings of the 5th Workshop on Theorem Proving with Analytic Tableaux and Related Methods, LNAI 1071, Springer, 1996, pp. 278-294.
Neiman, V.: Refutation search for Horn sets by a subgoal extraction method, J. Logic Programming 9(1990), 267-284.
Ohta, Y., Inoue, K. and Hasegawa, R.: On the relationship between non-Horn magic sets and relevancy testing, in Proceedings of CADE-15, LNAI 421, 1998, pp. 333-348.
Rajasekar, A. and Yusuf, H.: DWAM - a WAM model extension for disjunctive logic programming, Ann. Math. Artificial Intelligence 14(1995), 275-308.
Ramsay, A.: Generating relevant models, J. Automated Reasoning 7(1991), 359-368.
Ramakrishnan, R. and Sudarshan, S.: Top-down vs. bottom-up revisited, in Proceedings of the ISLP’91, 1991.
Reiter, R.: On closed world databases, in H. Gallaire and J. Minker (eds.), Logic and Data Bases, Plenum Press, New York, 1978, pp. 55-76.
Rohmer, J., Lescoeur, R. and Kerisit, J.-M.: The Alexander method: A technique for the processing of recursive axioms in deductive databases, New Generation Computing 4(3) (1986), 1273-1285.
Royer, V.: Backward chaining evaluation in stratified disjunctive theories, in Proceedings of PODS’90, 1990, pp. 183-195.
Seipel, D., Minker, J. and Ruiz, C.: Model generation and state generation for disjunctive logic programs, J. Logic Programming 32(1) (1997), 48-69.
Shimajiri, Y., Seki, H. and Itoh, H.: Goal-directed query processing in disjunctive logic databases, in Proceedings of the 7th International Symposium on Programming Languages: Implementations, Logics and Programs PLILP’95, LNCS 982, Springer, 1995, pp. 415-430.
Stickel, M.: Meta interpretation of the model elimination theorem proving procedure for deduction and abduction, J. Automated Reasoning 13(2) (1994), 189-210.
Treitel, M. and Genesereth, M.: Choosing directions of rules, J. Automated Reasoning 3(2) (1987), 395-431.
Yahya, A.: Generalized query answering in disjunctive deductive databases: Procedural and nonmonotonic aspects, in Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning, LNCS 1265, Springer, July 1997, pp. 278-294.
Yahya, A.: Minimal model generation for refined answering of generalized queries in disjunctive deductive databases, J. Data and Knowledge Engineering 34(2000), 219-249.
Yahya, A.: A goal-driven approach to efficient query processing in disjunctive deductive databases, Technical Report PMS-FB-1996-12, Department of Computer Science, Munich University, July 1996.
Yahya, A. and Henschen, L. J.: Deduction in non-Horn databases, J. Automated Reasoning 1(2) (1985), 141-160.
Yahya, A. and Minker, J.: Representations for disjunctive deductive databases, Technical Report CS-TR-3111 UMIACS-TR-93-70, Department of Computer Science and UMIACS, University of Maryland, College Park, July 1993.