{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:25:03Z","timestamp":1761611103551,"version":"3.40.5"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Annals of Mathematics and Artificial Intelligence"],"published-print":{"date-parts":[[1997,3]]},"DOI":"10.1023\/a:1018999404360","type":"journal-article","created":{"date-parts":[[2003,2,19]],"date-time":"2003-02-19T22:07:13Z","timestamp":1045692433000},"page":"97-125","source":"Crossref","is-referenced-by-count":27,"title":["Programming with non-determinism in deductive databases"],"prefix":"10.1007","volume":"19","author":[{"given":"Fosca","family":"Giannotti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Greco","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Domenico","family":"Sacc\u00e0","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlo","family":"Zaniolo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"325413_CR1","unstructured":"A.V. Aho, J.E. Hopcroft and J.D. Ullman, Data Structures and Algorithms (Addison-Wesley, 1983)."},{"key":"325413_CR2","doi-asserted-by":"crossref","unstructured":"S. Abiteboul, E. Simon and V. Vianu, Non-deterministic language to express deterministic transformation, in: Proceedings of the Ninth ACM Symposium on Principles of Database Systems (1990) pp. 215\u2013229.","DOI":"10.1145\/298514.298575"},{"key":"325413_CR3","unstructured":"S. Abiteboul, R. Hull and V. Vianu, Foundations of Databases (Addison-Wesley, 1995)."},{"key":"325413_CR4","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/0022-0000(91)90032-Z","volume":"43","author":"S. Abiteboul","year":"1991","unstructured":"S. Abiteboul and V. Vianu, Datalog extensions for databases queries and updates, Journal of Computer and System Science 43 (1991) 62\u2013124.","journal-title":"Journal of Computer and System Science"},{"issue":"1","key":"325413_CR5","first-page":"177","volume":"51","author":"F. Afrati","year":"1991","unstructured":"F. Afrati, S.S. Cosmadakis and M. Yannakakis, On Datalog vs. polynomial time, Journal of Computer and System Science 51(1) (1991) 177\u2013196.","journal-title":"Journal of Computer and System Science"},{"key":"325413_CR6","doi-asserted-by":"crossref","unstructured":"C. Apt, H. Blair and A. Walker, Towards a theory of declarative knowledge, in: Proc. Workshop on Found. of Deductive Database and Logic Programming, ed. I. Minker (1988) pp. 89\u2013148.","DOI":"10.1016\/B978-0-934613-40-8.50006-3"},{"key":"325413_CR7","unstructured":"A. Brogi, V.S. Subrahmanian and C. Zaniolo, The logic of totally and partially ordered plans: a deductive database approach, Ann. of Math. and AI (this issue)."},{"key":"325413_CR8","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/0022-0000(80)90032-X","volume":"21","author":"A. Chandra","year":"1980","unstructured":"A. Chandra and D. Harel, Computable queries for relational databases, Journal of Computer and System Science 21 (1980) 156\u2013178.","journal-title":"Journal of Computer and System Science"},{"key":"325413_CR9","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A. Chandra","year":"1982","unstructured":"A. Chandra and D. Harel, Structures and complexity of relational queries, Journal of Computer and System Science 25 (1982) 99\u2013128.","journal-title":"Journal of Computer and System Science"},{"issue":"1","key":"325413_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0743-1066(85)90002-0","volume":"2","author":"A. Chandra","year":"1985","unstructured":"A. Chandra and D. Harel, Horn clause and generalizations, Journal of Logic Programming 2(1) (1985) 1\u201315.","journal-title":"Journal of Logic Programming"},{"issue":"3","key":"325413_CR11","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0743-1066(95)00091-7","volume":"26","author":"W. Chen","year":"1996","unstructured":"W. Chen and J. Zeng, Non-determinism through well-founded choice, Journal of Logic Programming 26(3) (1996) 285\u2013309.","journal-title":"Journal of Logic Programming"},{"key":"325413_CR12","unstructured":"J. Chomicki, Temporal deductive databases, in: Temporal Databases: Theory, Design and Implementation, eds. A. Tansel et al. (Benjamin\/Cummings, 1993)."},{"key":"325413_CR13","doi-asserted-by":"crossref","unstructured":"L. Corciulo, F. Giannotti and D. Pedreschi, Datalog with non-deterministic choice computes NDB-PTIME, in: Proc. Deductive and Object-oriented Databases, Third International Conference, DOOD'93, eds. S. Ceri, K. Tanaka and S. Tsur, LNCS 760 (1993) pp. 49\u201366.","DOI":"10.1007\/3-540-57530-8_4"},{"key":"325413_CR14","unstructured":"L. Corciulo, F. Giannotti, D. Pedreschi and C. Zaniolo, Expressive power of non-deterministic operators for logic-based languages, in: Proc. 2nd ICLP Workshop on Deductive Databases and Logic Programming, Santa Margherita Ligure, June 1994, eds. U. Geske and D. Seipel, GMD-Studien 231 (1994) pp. 27\u201340."},{"issue":"3","key":"325413_CR15","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1109\/32.48941","volume":"16","author":"S.K. Debray","year":"1990","unstructured":"S.K. Debray and D.S. Warren, Towards banishing the cut from Prolog', IEEE Trans. on Software Engineering 16(3) (1990) 335\u2013349.","journal-title":"IEEE Trans. on Software Engineering"},{"key":"325413_CR16","first-page":"61","volume":"1","author":"F. Giannotti","year":"1994","unstructured":"F. Giannotti, D. Pedreschi and C. Zaniolo, Declarative semantics for pruning operators logic programming, Methods of Logic in Computer Science 1 (1994) 61\u201376.","journal-title":"Methods of Logic in Computer Science"},{"key":"325413_CR17","series-title":"Technical Report","volume-title":"Semantics and expressive power of non-deterministic constructs in deductive","author":"F. Giannotti","year":"1996","unstructured":"F. Giannotti, D. Pedreschi and C. Zaniolo, Semantics and expressive power of non-deterministic constructs in deductive, Technical Report C96-04, Istituto CNUCE, Pisa (1996), submitted for publication."},{"issue":"1","key":"325413_CR18","first-page":"244","volume":"51","author":"S. Ganguly","year":"1991","unstructured":"S. Ganguly, S. Greco and C. Zaniolo, Extrema predicates in deductive databases, Journal of Computer and System Science 51(1) (1991) 244\u2013259.","journal-title":"Journal of Computer and System Science"},{"key":"325413_CR19","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness (Freeman, 1979)."},{"key":"325413_CR20","unstructured":"M. Gelfond and V. Lifschitz, The stable model semantics of logic programming, in: Proceedings of the Fifth Int. Conference on Logic Programming (1988) pp. 1070\u20131080."},{"key":"325413_CR21","doi-asserted-by":"crossref","unstructured":"F. Giannotti, D. Pedreschi, D. Sacc\u00e0 and C. Zaniolo, Non-determinism in deductive databases, in: Proc. 2nd Int. Conf. on Deductive and Object-Oriented Databases (1991) pp. 129\u2013146.","DOI":"10.1007\/3-540-55015-1_7"},{"key":"325413_CR22","doi-asserted-by":"crossref","unstructured":"S. Greco, C. Zaniolo and S. Ganguly, Greedy by choice, in: Proceedings of the Eleventh ACM Symposium on Principles of Database Systems (1992) pp. 105\u2013163.","DOI":"10.1145\/137097.137836"},{"key":"325413_CR23","doi-asserted-by":"crossref","unstructured":"S. Greco, D. Sacc\u00e0 and C. Zaniolo, DATALOG queries with stratified negation and choice: from P to D\nP, in: Proc. of the Fifth Int. Conf. on Database Theory (1995) pp. 82\u201396.","DOI":"10.1007\/3-540-58907-4_8"},{"issue":"4","key":"325413_CR24","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman, Languages that capture complexity classes, SIAM Journal of Computing 16(4) (1987) 760\u2013778.","journal-title":"SIAM Journal of Computing"},{"key":"325413_CR25","doi-asserted-by":"crossref","unstructured":"D.S. Johnson, A Catalog of Complexity Classes, Handbook of Theoretical Computer Science, Vol. 1, ed. J. Leewen (North-Holland, 1990) pp. 67\u2013161.","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"key":"325413_CR26","doi-asserted-by":"crossref","unstructured":"P.C. Kanellakis, Elements of Relational Databases Theory, Handbook of Theoretical Computer Science, ed. J. Leewen (North-Holland, 1990) pp. 1075\u20131155.","DOI":"10.1016\/B978-0-444-88074-1.50022-6"},{"key":"325413_CR27","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0890-5401(91)90059-B","volume":"90","author":"P. Kolaitis","year":"1990","unstructured":"P. Kolaitis, The expressive power of stratified logic programs, Information and Computation 90 (1990) 50\u201366.","journal-title":"Information and Computation"},{"key":"325413_CR28","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0022-0000(91)90033-2","volume":"43","author":"P. Kolaitis","year":"1991","unstructured":"P. Kolaitis and C. Papadimitriou, Why not negation by fixpoint, Journal of Computer and System Science 43 (1991) 125\u2013144.","journal-title":"Journal of Computer and System Science"},{"key":"325413_CR29","doi-asserted-by":"crossref","unstructured":"P.G. Kolaitis and M.Y. Vardi, On the expressive power of Datalog: Tools and a case study, in: ACM Proc. Symp. on Principles of Database Systems (1990) pp. 61\u201371.","DOI":"10.1145\/298514.298542"},{"key":"325413_CR30","doi-asserted-by":"crossref","unstructured":"R. Krishnamurthy and S. Naqvi, Non-deterministic choice in Datalog, in: Proceedings of the 3rd International Conference on Data and Knowledge Bases (1988) pp. 416\u2013424.","DOI":"10.1016\/B978-1-4832-1313-2.50038-X"},{"key":"325413_CR31","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-83189-8","volume-title":"Foundations of Logic Programming","author":"J.W. Lloyd","year":"1987","unstructured":"J.W. Lloyd, Foundations of Logic Programming (Springer-Verlag, Berlin, 1987)."},{"key":"325413_CR32","volume-title":"A Logic Language for Data and Knowledge Bases","author":"S. Naqvi","year":"1989","unstructured":"S. Naqvi and S. Tsur, A Logic Language for Data and Knowledge Bases (Computer Science Press, New York, 1989)."},{"key":"325413_CR33","first-page":"21","volume":"26","author":"C. Papadimitriou","year":"1985","unstructured":"C. Papadimitriou, A note on the expressive power of Prolog, Bull. of the EATCS 26 (1985) 21\u201323.","journal-title":"Bull. of the EATCS"},{"key":"325413_CR34","unstructured":"C. Papadimitriou, Computational Complexity (Addison-Wesley, 1994)."},{"key":"325413_CR35","unstructured":"R. Ramakrishnan, D. Srivastava and S. Sudanshan, CORAL \u2014 Control, relations and logic, in: Proceedings of 18th VLDB Conference (1992)."},{"key":"325413_CR36","doi-asserted-by":"crossref","unstructured":"D. Sacc\u00e0 and C. Zaniolo, Stable models and non-determinism in logic programs with negation, in: Proceedings of the Ninth ACM Symposium on Principles of Database Systems (1990) pp. 205\u2013217.","DOI":"10.1145\/298514.298572"},{"key":"325413_CR37","unstructured":"D. Sacc\u00e0 and C. Zaniolo, Deterministic and Non-Deterministic Stable Models (1994), submitted for publication."},{"key":"325413_CR38","doi-asserted-by":"crossref","unstructured":"J.S. Schlipf, The expressive power of the logic programming semantics, in: Proceedings of the Ninth ACM Symposium on Principles of Database Systems (1990) pp. 196\u2013204.","DOI":"10.1145\/298514.298564"},{"key":"325413_CR39","unstructured":"J.S. Schlipf, A survey of complexity and undecidability results in logic programming, in: Proc. Workshop on Structural Complexity and Recursion-Theoretic Methods in Logic Programming (1993) pp. 143\u2013164."},{"key":"325413_CR40","doi-asserted-by":"crossref","unstructured":"Y.-H. Sheng, A non-deterministics deductive database language, in: Proceedings of the 1991 ACM-SIGMOD Int. Conference on Management of Data (1991) pp. 188\u2013198.","DOI":"10.1145\/115790.115817"},{"key":"325413_CR41","unstructured":"J.D. Ullman, Principles of Databases and Knowledge Base Systems, Vols. I and II (Computer Science Press, 1988)."},{"issue":"1","key":"325413_CR42","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0743-1066(89)90032-0","volume":"6","author":"A. Van Gelder","year":"1989","unstructured":"A. Van Gelder, Negation as failure using tight derivations for general logic programs, Journal of Logic Programming 6(1) (1989) 109\u2013133.","journal-title":"Journal of Logic Programming"},{"issue":"3","key":"325413_CR43","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1145\/116825.116838","volume":"38","author":"A. Van Gelder","year":"1991","unstructured":"A. Van Gelder, K.A. Ross and J.S. Schlipf, The well-founded semantics for general logic programs, Journal of ACM 38(3) (1991) 620\u2013650.","journal-title":"Journal of ACM"},{"key":"325413_CR44","doi-asserted-by":"crossref","unstructured":"M. Vardi, The complexity of relational query languages, in: Proceedings of the 14th ACM Symposium on Theory of Computing (1982) pp. 137\u2013146.","DOI":"10.1145\/800070.802186"},{"key":"325413_CR45","doi-asserted-by":"crossref","unstructured":"C. Zaniolo, N. Arni and K. Ong, Negation and aggregates in recursive rules: the LDL++ approach, in: Proc. 3rd Int. Conf. on Deductive and O-O DBs, DOOD-93, Phoenix, AZ (Dec. 6\u20138, 1993) pp. 104\u2013221.","DOI":"10.1007\/3-540-57530-8_13"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1018999404360.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1018999404360\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1018999404360.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T05:37:11Z","timestamp":1747546631000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1018999404360"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":45,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["325413"],"URL":"https:\/\/doi.org\/10.1023\/a:1018999404360","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"type":"print","value":"1012-2443"},{"type":"electronic","value":"1573-7470"}],"subject":[],"published":{"date-parts":[[1997,3]]}}}