The expressive powers of stable models for bound and unbound DATALOG queries.

*(English)*Zbl 0882.68088Summary: Various types of stable models are known in the literature: \(T\)-stable (total stable), \(P\)-stable (partial stable, also called three-valued stable), \(M\)-stable (maximal stable, also known under various different names), and \(L\)-stable (least undefined stable). For each type of stable model, the paper analyzes two versions of deterministic semantics: possible semantics, which is based on the union of all stable models of the given type, and definite semantics, which is instead based on their intersection and is like classical certain semantics except that it makes no inference if no model exists. For total stable models, which are the only type of stable models whose existence is not guaranteed for every program, certain semantics is taken into account as well. The expressive powers of each type of stable model under the above versions of semantics are investigated for both bound (i.e., ground) and unbound queries on DATALOG programs with negation. As deterministic semantics is argued to be inappropriate for unbound queries, a nondeterministic semantics is also proposed for them and its expressive power is fully characterized as well.

##### MSC:

68Q55 | Semantics in the theory of computing |

PDF
BibTeX
XML
Cite

\textit{D. Saccà}, J. Comput. Syst. Sci. 54, No. 3, 441--464 (1997; Zbl 0882.68088)

Full Text:
DOI

##### References:

[1] | Apt, K.; Blair, H.; Walker, A., Towards a theory of declarative knowledge, Foundations of Deductive Databases and Logic Programming, (1988), Morgan Kauffman Los Altos, p. 89-142 |

[2] | Abiteboul, S.; Hull, R.; Vianu, V., Foundations of Datahases, (1994), Addison-Wesley Reading |

[3] | S. Abiteboul, E. Simon, V. Vianu, 1990, Non-deterministic languages to express deterministic transformations, Proc. ACM PODS Symposium, 218, 229 |

[4] | Abiteboul, S.; Vianu, V., Procedural languages for database queries and updates, J. Comput. System Sci., 41, 181-229, (1990) · Zbl 0715.68019 |

[5] | S. Abiteboul, M. Y. Vardi, V. Vianu, 1992, Fixpoints, relational machines, and computational complexity, Proc. 7th IEEE Conf. on Structure in Complexity Theory, 156, 168 |

[6] | Baral, V.; Subrahmanian, V., Stable and extension class theory for logic programs and default logic, J. Automated Reasoning, 8, 345-366, (1992) · Zbl 0763.03017 |

[7] | Bidoit, N., Negation in rule-based database languages: A survey, Theoret. Comput. Sci., 78, 3-83, (1991) · Zbl 0716.68025 |

[8] | Cadoli, M.; Schaerf, M., A survey on complexity results for non-monotonic logics, J. Logic Programming, 17, 127-160, (1993) · Zbl 0784.68039 |

[9] | Ceri, S.; Gottlob, G.; Tanca, L., Logic Programming and Databases, (1990), Springer-Verlag Berlin |

[10] | Chandra, A.; Harel, D., Structure and complexity of relational queries, J. Comput. and System Sci., 25, 99-128, (1982) · Zbl 0511.68073 |

[11] | Chandra, A.; Harel, D., Horn clause and generalizations, J. Logic Programming, 2, 1-15, (1985) · Zbl 0583.68058 |

[12] | Z-Z. Chen, S. Toda, 1993, The complexity of selecting maximal solutions, Proc. of 8th IEEE Conference on Structure in Complexity Theory, 313, 325 · Zbl 0939.68657 |

[13] | P. Dung, 1991, Negation as hypotheses: An abductive foundation for logic programming, Proc. 8th Conference on Logic Programming, 3, 17 |

[14] | T. Eiter, G. Gottlob, H. Mannila, May 1994, Expressive power and complexity of disjunctive DATALOG, Proc. ACM PODS Symposium, 267, 278 |

[15] | R. Fagin, 1974, Generalized first-order spectra and polynomial-time recognizable sets, Complexity of Computation, R. Karp, SIAM-AMS Proc. 7, 43, 73 · Zbl 0303.68035 |

[16] | Carey, M.; Johnson, D. S., Computers and Intractability—A Guide to the Theory of NP-Completeness, (1979), Freeman New York · Zbl 0411.68039 |

[17] | M. Gelfond, V. Lifschitz, 1988, The stable model semantics for logic programming, Proc. 5th Conf. and Symp. on Logic Programming, 1070, 1080, MIT Press, Cambridge |

[18] | F. Giannotti, D. Pedreschi, D. Saccà, C. Zaniolo, 1991, Non-determinism in deductive databases, Proc. 2nd Conference on deductive and Obgect-Oriented databases, DOOD 91, C. DelobelM. KiferY. Masunaga, 29, 146, Springer-Verlag, New York/Berlin |

[19] | S. Greco, D. Saccà, C. Zaniolo, DATALOG queries with stratified negation and choice: From \(P\) to \(D\)^p, Proc. of the Fifth Int. Conf. on Database Theory (ICDT’95), LNCS 893, Springer-Verlag, 1995, 82, 96 |

[20] | Gurovich, Y., Logic and the challenge of computer science, (Borger, E., Trends in Theoretical Computer Science, (1988), Computer Science Press) |

[21] | Immerman, N., Languages which capture complexity classes, SIAM J. Computing, 16, 760-778, (1987) · Zbl 0634.68034 |

[22] | Johnson, D. S., A catalog of complexity classes, (van Leewen, J., Handbook of Theoretical Computer Science, (1990), North-Holland Amsterdam) · Zbl 0900.68246 |

[23] | Kakas, A.; Mancarella, P., Preferred extensions are partial stable models, J. Logic Programming, 14, 341-348, (1992) · Zbl 0769.68081 |

[24] | Kanellakis, P. C., Elements of relational database theory, (van Leewen, J., Handbook of Theoretical Computer Science, (1991), North-Holland Amsterdam) |

[25] | Kolaitis, P. G., The expressive power of stratified logics programs, Inform. and Comput., 90, 50-66, (1991) · Zbl 0727.68016 |

[26] | Kolaitis, P. G.; Papadimitriou, C. H., Why not negation by fixpoint?, J. Comput. System Sci., 43, 125-144, (1991) · Zbl 0753.68028 |

[27] | Leone, N.; Romeo, M.; Rullo, P.; Saccà, D., Effective implementation of negation in database logic query languages, (Atzeni, P., LOGIDATA+: Deductive Databases with Complex Objects, (1993), Springer-Verlag), 159-175 |

[28] | Lloyd, J. W., Foundations of Logic Programming, (1987), Springer-Verlag Berlin · Zbl 0547.68005 |

[29] | Marek, W.; Truszcynski, M., Autoepistemic logic, J. Assoc. Comput. Machin., 38, 588-619, (1991) · Zbl 0799.68176 |

[30] | A. R. Meyer, L. J. Stockmeyer, 1972, The equivalence problem for regular expressions with squaring requires exponential time, Proc. IEEE Symp. on Snitching and Automata Theory, 125, 129 |

[31] | Naqvi, S. A., A logic for negation in database systems, (Minker, J., Foundations of Deductive Databases and Logic Programming, (1987), Morgan Kaufman Los Altos) |

[32] | Naqvi, S.; Tsur, S., A Logical Data Language for Data and Knowledge Bases, (1989), Computer Science Press New York |

[33] | Papadimitriou, C., A note on the expressive power of prolog, Bull. EATCS, 26, 21-23, (1985) |

[34] | Papadimitriou, C., Computational Complexity, (1994), Addison-Wesley Reading · Zbl 0833.68049 |

[35] | Papadimitriou, C. H.; Yannakakis, M., The complexity of facets (and some facets of complexity), J. Comput. System Sci., 28, 244-259, (1982) · Zbl 0571.68028 |

[36] | Przymusinski, T. C., Well-founded semantics coincides with three-valued stable semantics, Foundament. Inform., 13, 445-463, (1990) · Zbl 0706.68029 |

[37] | Saccà, D., Multiple total stable models are definitely needed to solve unique solution programs, Inform. Process., 58, 249-254, (1996) · Zbl 1023.68514 |

[38] | D. Saccà, C. Zaniolo, 1990, Stable models and non-determinism in logic programs with negation, Proc. ACM PODS Symp. 205, 218 |

[39] | D. Saccà, C. Zaniolo, 1991, Partial models and three-valued models in logic programs with negation, Proc. 1st International Conference on Logic Programs and Non-monotonic Reasoning, 87, 104, MIT Press, Cambridge |

[40] | D. Saccà, C. Zaniolo, Deterministic and non-deterministic stable models, J. Logic Comput. |

[41] | J. S. Schlipf, 1990, The expressive powers of the logic programming semantics, Proc. ACM PODS Symp. 196, 204 · Zbl 0831.68012 |

[42] | J. S. Schlipf, Nov. 1993, A survey of complexity and undecidability results in logic programming, Proc. Workshop on Structural Complexity and Recursion-Theoretic Methods in Logic Programming, 143, 164 |

[43] | Ullman, J. D., Principles of Database and Knowledge Base Systems, (1989), Computer Science Press |

[44] | J. Van de Bussche, D. Van Gucht, 1992, Semi-determinism, Proc. of ACM PODS Symp. 191, 201 |

[45] | Van Gelder, A., Negation as failure using tight derivations for general logic programs, J. Logic Programming, 6, 109-133, (1989) · Zbl 0668.68108 |

[46] | Van Gelder, A.; Ross, K.; Schlipf, J. S., The well-founded semantics for general logic programs, J. Assoc. Comput. Machin., 38, 620-650, (1991) · Zbl 0799.68045 |

[47] | M. Y. Vardi, The complexity of relational query languages, Proc. ACM Symp. on Theory of Computing, 1982, 137, 146 |

[48] | J. You, L. Y. Yuan, Three valued formalization of logic programming: Is it needed?, Proc. of ACM PODS Symp, 1990, 172, 182 |

[49] | You, J.; Yuan, L. Y., On the equivalence of semantics for normal logic programs, J. Logic Programming, 22, 211-222, (1995) · Zbl 0830.68030 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.