{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T14:49:03Z","timestamp":1749221343143},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540575306"},{"type":"electronic","value":"9783540482123"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57530-8_4","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:08:26Z","timestamp":1330261706000},"page":"49-66","source":"Crossref","is-referenced-by-count":7,"title":["Datalog with non-deterministic choice computes NDB-PTIME"],"prefix":"10.1007","author":[{"given":"Luca","family":"Corciulo","sequence":"first","affiliation":[]},{"given":"Fosca","family":"Giannotti","sequence":"additional","affiliation":[]},{"given":"Dino","family":"Pedreschi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"K. R. Apt. Introduction to Logic Programming. In: Handbook of Theoretical Computer Science, vol B. (Ed. J. van Leeuwen) (1990). pp. 493\u2013574.","DOI":"10.1016\/B978-0-444-88074-1.50015-9"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"S. Abiteboul, E. Simon, V. Vianu. Non-Deterministic Language to Express Deterministic Transformation. Proceedings of ACM Symposium on Principles of Database Systems, 1990. pp. 218\u2013229.","DOI":"10.1145\/298514.298575"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"S. Abiteboul, V. Vianu. Transaction Languages for Databases Update and Specification. INRIA Technical Report n. 715 (1987).","DOI":"10.1145\/28659.28688"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"S. Abiteboul, V. Vianu. Procedural Languages for Database Queries and Updates. Journal of Computer and System Science 41 (2) (1990).","DOI":"10.1016\/0022-0000(90)90036-K"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"S. Abiteboul, V. Vianu. Fixpoint Extension of First Order Logic and Datalog-Like Languages. Proc. 4th Symp on Logic in Computer Science (LICS). IEEE Computer Press (1989). pp. 71\u201389.","DOI":"10.1109\/LICS.1989.39160"},{"key":"4_CR6","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF01530924","volume":"3","author":"S. Abiteboul","year":"1991","unstructured":"S. Abiteboul, V. Vianu. Non-Determinism in Logic Based Languages. Annals of Mathematics and Artificial Intelligence 3 (1991). pp. 151\u2013186.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"4_CR7","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, D. Harel. Structures and Complexity of Relational Queries. Journal of Computer and System Science 25 (1982). pp. 99\u2013128.","journal-title":"Journal of Computer and System Science"},{"issue":"1","key":"4_CR8","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1109\/69.50907","volume":"2","author":"D. Chimenti","year":"1990","unstructured":"D. Chimenti, et al., The DL System Prototype. IEEE Journal on Data and Knowledge Engineering, Vol. 2, No. 1, (1990). pp. 76\u201390.","journal-title":"IEEE Journal on Data and Knowledge Engineering"},{"key":"4_CR9","first-page":"33","volume-title":"Data Base Systems","author":"E. F. Codd","year":"1972","unstructured":"E.F. Codd. Relational Completeness of Database Sublanguages. Data Base Systems, (Ed. R. Rustin), Prentice-Hall, Englewood Cliffs, NJ (1972) pp. 33\u201364."},{"key":"4_CR10","unstructured":"L. Corciulo. Non determinism in deductive databases. Laurea Thesis. Dipartimento di Informatica, Universit\u00e0 di Pisa. 1993 (in Italian)"},{"issue":"2","key":"4_CR11","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/356924.356929","volume":"16","author":"H. Gallaire","year":"1984","unstructured":"H. Gallaire, J. Minker, J.M. Nicolas. Logic and Databases, a Deductive Approach. ACM Computing Surveys 16(2) (1984). pp. 153\u2013185.","journal-title":"ACM Computing Surveys"},{"key":"4_CR12","unstructured":"M. Gelfond, V. Lifschitz. The stable model semantics for logic programming. Proc. 5th Int. Conf. and Symp. on Logic Programming, MIT Press, pp. 1080\u20131070, 1988."},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"F. Giannotti, D. Pedreschi, D. Sacc\u00e0, C. Zaniolo. Non-Determinism in Deductive Databases. Proc. Deductive and Object-oriented Databases, Second International Conference, DOOD'93, (Eds. C. Delobel, M. Kifer, Y. Masunaga), Springer-Verlag, LNCS 566, pp. 129\u2013146, 1991.","DOI":"10.1007\/3-540-55015-1_7"},{"key":"4_CR14","unstructured":"F. Giannotti, D. Pedreschi, C. Zaniolo. Declarative Semantics for Pruning Operators in Logic Programming. Methods of Logic in Computer Science (1993) To appear."},{"key":"4_CR15","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0168-0072(86)90055-2","volume":"32","author":"Y. Gurevich","year":"1986","unstructured":"Y. Gurevich, S. Shelah. Fixed-Point Extensions of First-Order Logic. Annals of Pure and Applicate Logic 32 (1986). pp. 265\u2013280.","journal-title":"Annals of Pure and Applicate Logic"},{"issue":"4","key":"4_CR16","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman, Languages which Capture Complexity Classes. SIAM J. Computing, 16,4, (1987). pp. 760\u2013778.","journal-title":"SIAM J. Computing"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"P.C. Kanellakis. Elements of Relational Databases Theory. In: Handbook of Theoretical Computer Science, (Ed. J. van Leeuwen) (1990). pp. 1075\u20131155.","DOI":"10.1016\/B978-0-444-88074-1.50022-6"},{"key":"4_CR18","first-page":"416","volume-title":"Non-Deterministic Choice in Datalog","author":"R. Krishnamurthy","year":"1988","unstructured":"R. Krishnamurthy, S. Naqvi. Non-Deterministic Choice in Datalog. Proc. 3nd Int. Conf. on Data and Knowledge Bases, Morgan Kaufmann Pub., Los Altos (1988). pp. 416\u2013424."},{"key":"4_CR19","volume-title":"A Logical Language for Data and Knowledge Bases","author":"S. Naqvi","year":"1989","unstructured":"S. Naqvi, S. Tsur. A Logical Language for Data and Knowledge Bases. Computer Science Press, New York (1989)."},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"D. Sacc\u00e0, C. Zaniolo. Stable Models and Non-Determinism in Logic Programs with Negation. Proc. Symp. on Principles of Database System PODS'89 (1989).","DOI":"10.1145\/298514.298572"},{"key":"4_CR21","volume-title":"Principles of Databases and Knowledge Base System. Volume I and II","author":"J. D. Ullman","year":"1988","unstructured":"J.D. Ullman. Principles of Databases and Knowledge Base System. Volume I and II. Computer Science Press, Rockville, Md (1988)."}],"container-title":["Lecture Notes in Computer Science","Deductive and Object-Oriented Databases"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57530-8_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T05:39:29Z","timestamp":1640929169000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57530-8_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540575306","9783540482123"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-57530-8_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}