×

Complexity and expressive power of deterministic semantics for DATALOG\(^ \neg\). (English) Zbl 1045.68514

Summary: Deterministic models are (partial) stable models which are not contradicted by any other stable model; i.e., \(M\) is a deterministic model if there is no stable model \(N\) such that \(M\cup N\) is not an interpretation. For instanced the well-founded model, which coincides with the intersection of all partial stable models, is a deterministic model. As the well-founded model is deterministic and unique for each program, well-founded model semantics has been proposed as the canonical deterministic semantics for partial stable models. But the well-founded model is not the unique deterministic model; indeed the family of deterministic (partial stable) models is not, in general, a singleton and admits a minimum (the well-founded model) and a maximum, the max-deterministic model. The latter model is, another candidate for a deterministic semantics. The aim of this paper is to study the complexity and the expressive power of deterministic semantics. In coherence with the deterministic nature of the model, the expressive power of max-deterministic semantics is shown to be able to express problems with unique solutions, whereas the well-founded model only captures a proper subset of the queries computable in polynomial time, the so-called fixpoint queries.

MSC:

68N17 Logic programming
68P15 Database theory

Software:

Datalog
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abiteboul, S.; Hull, R.; Vianu, V., Foundations of Databases (1994), Addison-Wesley: Addison-Wesley Reading
[2] Abiteboul, S.; Simon, E.; Vianu, V., Non-deterministic languages to express deterministic transformations, Proceedings of the 9th ACM Symposium on Principles of Database Systems (1990), p. 218-229
[3] Buccafurri, F.; Greco, S.; Saccà, D., The expressive power of unique total stable model semantics, Proceedings 22nd International Colloquium on Automata Languages and Programming (1997), p. 849-859 · Zbl 1401.68027
[4] Blass, A.; Gurevich, Y., On the unique satisfiability problem, Inform. and Control, 55, 80-88 (1982) · Zbl 0543.03027
[5] Ceri, S.; Gottlob, G.; Tanca, L., Logic programming and Databases (1990), Springer-Verlag: Springer-Verlag New York/Berlin
[6] Chandra, A.; Harel, D., Structure and complexity of relational queries, J. Comput. System Sci., 25, 99-128 (1982) · Zbl 0511.68073
[7] Chen, Z. Z.; Toda, S., The complexity of selecting maximal solutions, Inform. and Comput., 119, 231-239 (1995) · Zbl 0834.68045
[8] Eiter, T.; Gottlob, G.; Mannila, H., Disjunctive datalog, ACM Trans. Database Systems, 22, 364-418 (1997)
[9] Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, (Karp, R., Complexity of Computation. Complexity of Computation, SIAM-AMS Proc., 7 (1974), SIAM: SIAM Philadelphia), 43-73
[10] Fitting, M. 1994, On prudent bravery and other abstractions, unpublished manuscript.; Fitting, M. 1994, On prudent bravery and other abstractions, unpublished manuscript.
[11] Fitting, M., A Kripke-Kleene semantics for logic programs, J. Logic Programming, 2, 295-312 (1985) · Zbl 0589.68011
[12] Gelfond, M.; Lifschitz, V., The stable model semantics for logic programming, Proceedings of the 5th International Conference on Logic Programming (1988), p. 1070-1080
[13] Greco, S.; Saccà, D., “Possible is Certain” is desirable and can be expressive, Ann. Math. Artif. Intel., 19, 147-168 (1997) · Zbl 0880.68011
[14] Greco, S.; Saccà, D., Deterministic semantics for \(Datalog^¬\): Complexity and expressive power, Proceedings of the International Conference on Deductive and Object Oriented Databases (1997), p. 337-350
[15] Greco, S.; Saccà, D.; Zaniolo, C., DATALOG queries with stratified negation and choice: From \(P\) to \(DP\), Proceedings of the 5th International Conference on Database Theory (1995), p. 82-96
[16] Grumbach, S.; Lacroix, Z.; Lindell, S., Implicit definitions on finite structures, Proceedings of the Conference on Computer Science Logic (1995), p. 252-265
[17] Gurevich, Y., Logic and the Challenge of Computer Science, (Borger, E., Trends in Theoretical Computer Science (1988), Comput. Sci. Press: Comput. Sci. Press New York)
[18] Johnson, D. S., A catalog of complexity classes, (van Leeuwen, J., Handbook of Theoretical Computer Science (1990), North-Holland: North-Holland Amsterdam), 67-254 · Zbl 0900.68246
[19] Kolaitis, P. G., Implicit definability on finite structures and unambiguous computations, Proceedings 5th IEEE Symposium on Logic in Computer Science (1990), p. 168-180
[20] Kolaitis, P. G.; Papadimitriou, C. H., Why not negation by fixpoint?, J. Comput. System Sci., 43, 125-144 (1991) · Zbl 0753.68028
[21] Laenens, E.; Vermeir, D.; Zaniolo, C., Logic programming semantics made easy, Proceedings of the Int. Colloquium on Automata, Languages and Programming (1992), p. 499-508 · Zbl 1425.68052
[22] Lloyd, J. W., Foundations of Logic Programming (1987), Springer-Verlag: Springer-Verlag Berlin · Zbl 0547.68005
[23] Marek, W.; Truszcynski, M., Autoepistemic Logic, J. Assoc. Comput. Mach., 38, 588-619 (1991) · Zbl 0799.68176
[24] Papadimitriou, C., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading · Zbl 0833.68049
[25] 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
[26] Przymusinski, T. C., Well-founded semantics coincides with three-valued stable semantics, Fundamenta Inform., 13, 445-463 (1990) · Zbl 0706.68029
[27] Saccà, D., Multiple total stable models are definitely needed to solve unique solution programs, Inform. Process. Lett., 58, 249-254 (1996) · Zbl 1023.68514
[28] Saccà, D., The expressive powers of stable models for bound and unbound queries, J. Comput. System Sci., 54, 441-464 (1997) · Zbl 0882.68088
[29] Saccà, D.; Zaniolo, C., Stable models and non-determinism in logic programs with negation, Proceedings ACM Symposium on Principles of Database Systems (1990), p. 205-218
[30] Saccà, D.; Zaniolo, C., Deterministic and non-deterministic stable models, J. Logic Comput., 7, 555-579 (1997) · Zbl 0883.68031
[31] Schlipf, J. S., The expressive powers of the logic programming semantics, Proceedings ACM Symposium on Principles of Database Systems (1990), p. 196-204
[32] Smullyan, R. M., What Is the Name of This Book?: The Riddle of Dracula and Other Logical Puzzles (1978), Prentice-Hall: Prentice-Hall Englewood Cliffs · Zbl 0432.00028
[33] Ullman, J. D., Principles of Database and Knowledge Base Systems (1988), Comput. Sci. Press: Comput. Sci. Press New York
[34] Van Gelder, A., The alternating fixpoint of logic programming with negation, J. Comput. System Sci., 47, 125-144 (1992)
[35] Van Gelder, A.; Ross, K.; Schlipf, J. S., The well-founded semantics for general logic programs, J. Ass. Comput. Mach., 38, 620-650 (1991) · Zbl 0799.68045
[36] Vardi, M. Y., The complexity of relational query languages, Proceedings ACM Symposium on Theory of Computing (1982), p. 137-146
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.