A New Partial Semantics for Disjunctive Deductive Databases

• Autorzy: Gire F , Plourde C.
• Języki publikacji: EN

Abstrakty

EN

We propose a new partial semantics for disjunctive deductive databases that we call disjunctive well-founded semantics. This semantics extends the classical well-founded semantics of normal databases for disjunctive databases. We give a declarative definition as well as a computational procedure for this new semantics. We prove that, in the case of disjunctive positive databases, i.e. disjunctive databases without negation, the disjunctive well-founded semantics coincides with the intersection of the minimal models.

Słowa kluczowe

EN

disjunctive deductive databases; normal deductive databases; partial semantics; well-founded semantics

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 67, nr 4
• Strony: 323--342
• Opis fizyczny: Bibliogr. 26 poz.

Twórcy

autor

Gire F

• Université de Paris I Centre de Recherche en Informatique 90 rue de Tobliac, 75634 Paris cedex 13, France

autor

Plourde C.

• Société ParaGraph Parc Technopolis 17 avenue du Parc, 91380 Chilly Mazarin, France

Bibliografia

• [1] Baral, C., Lobo, J., Minker, J.: Generalized Disjunctive Well-Founded Semantics for Logic Programs: Procedural Semantics, International Symposium on Methodologies for Intelligent Systems, 1990, 456–464.
• [2] Baral, C., Lobo, J., Minker, J.: WF3: A Semantics for Negation in Normal Disjunctive Logic Programs, International Symposium on Methodologies for Intelligent Systems, 1991, 459–468.
• [3] Bidoit, N.: Negation in rule-based database languages: a survey, Theoretical Computer Science, 78, 1991, 3–83.
• [4] Brass, S., Dix, J.: Characterizations of the Disjunctive Well-Founded Semantics: Confluent Calculi and Iterated GCWA., J. Autom. Reasoning, 20(1), 1998, 143–165.
• [5] Brass, S., Dix, J., Minker, J.: A Disjunctive Semantics Based upon Partiel and Bottom-Up Evaluation, Third Intl.Conference on Logic programming ICLP95, MIT Press, 1995, 199–213.
• [6] Brass, S., Dix, J., Niemel”, I., Przymusinski: A Comparison of the Static and the Disjunctive Well-Founded Semantics and its Implementation, Conf. on Principles of Knowledge Representation and Reasoning, 1998, 74–85.
• [7] Davis, M., Putnam, H.: A Computing Procedure for Quantification Theory, Journal of the ACM, 7, 1960, 201–215.
• [8] Eiter, T., Gottlob, G.: Complexity Aspects of various Semantics for Disjunctive Databases, Symposium of principles of Database Systems PODS93, 1993, 158–167.
• [9] Eiter, T., Gottlob, G., Mannila, H.: Adding disjunction to Datalog, Symposium of principles of Database Systems PODS94, 1994, 267–278.
• [10] Eiter, T., Leone, N., Sacca, D.: On the partial semantics for Disjunctive Deductive Databases, Ann. Math. Artif. Intell., 19(1-2), 1997, 59–96.
• [11] Eiter, T., Leone, N., Sacca, D., Mannila, H.: Expressive power and complexity of partial models for disjunctive deductive databases, Theoretical Computer Science, 206, 1998, 181–218.
• [12] Fernandez, J. A., Minker, J.: Computing perfect models of disjunctive stratified databases, ILPS’91Workshop on Disjunctive Logic Programs, 1991, 100–117.
• [13] Fernandez, J. A., Minker, J.: Semantics of Disjunctive Deductive Databases, International Conference on Database Theory, 1992, 21–50.
• [14] Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming, 5th Logic Programming Symposium, Assoc. For Logic Programming, MIT Press, 1988, 1070–1080.
• [15] Gire, F., Plourde, C.: A new partial semantics for disjunctive deductive databases (Fullpaper), Technical report, Centre de Recherche en Informatique de Paris 1, http://crinfo.univ-paris1.fr/users/gire/gire.htm, 2005.
• [16] Leone, N., Rullo, P., Scarcello, F.: Disjunctive Stable Models: Unfounded Sets, Fixpoint Semantics and Computation, Information and Computation, 135(2), 1997, 69–112.
• [17] Lloyd, J. W.: Foundations of Logic Programming, Springer-Verlag, 1984.
• [18] Przymusinski, T. C.: Extended stable semantics for normal and disjunctive programs, 7th Intl. Logic Programming Conf., Jerusalem, MIT Press, 1990, 459–477.
• [19] Przymusinski, T. C.: Well-founded Semantics Coincides with Three-valued Stable Semantics, Foundamenta Informaticae, 13, 1990, 445–463.
• [20] Przymusinski, T. C.: Static Semantics for Normal and Disjunctive Logic programs, Ann. Math. Artif. Intell., 14(2-4), 1995, 323–357.
• [21] Ross, K. A.: The well founded Semantics for Disjunctive Logic Programs in: Deductive and Object-oriented Databases, Elsevier Science Publishers B.V. (North Holland), 1990.
• [22] Seipel, D.: Partial Evidential Stable Models for Disjunctive Deductive Databases, Workshop on Logic Programming and Knowledge Representation (LPKR’97), 1997, 66–84.
• [23] Seipel, D.: An Alternating Well-Founded Semantics for Query Answering in Disjunctive Databases, Lectures Notes in Artificial Intelligence (FQAS’98), 1495, 1998, 341–353.
• [24] Van Gelder, A.: The Alternating Fix point of Logic Programs with Negation, Symp. On Principles of Database Systems, ACM SIGACT-SIGMOD-SIGART, 1989, 1–10.
• [25] Van Gelder, A., Ross, K., Schilpf, J. S.: Unfounded Sets and Well-founded Semantics for General Logic Programs, Symp. On Principles of Database Systems, 1988, 221–230.
• [26] Wang, K.: A Comparative Study ofWell-Founded Semantics for Disjunctive Logic programs, Conf. on Logic Programming and Non-Monotonic Reasoning (LPNMR), 2001, 133–146.