{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T20:26:50Z","timestamp":1672691210795},"reference-count":27,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1998,4,1]],"date-time":"1998-04-01T00:00:00Z","timestamp":891388800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,19]],"date-time":"2013-07-19T00:00:00Z","timestamp":1374192000000},"content-version":"vor","delay-in-days":5588,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The Journal of Logic Programming"],"published-print":{"date-parts":[[1998,4]]},"DOI":"10.1016\/s0743-1066(97)10004-8","type":"journal-article","created":{"date-parts":[[2003,4,23]],"date-time":"2003-04-23T19:53:40Z","timestamp":1051127620000},"page":"79-101","source":"Crossref","is-referenced-by-count":7,"title":["Datalog with non-deterministic choice computes NDB-PTIME"],"prefix":"10.1016","volume":"35","author":[{"given":"Fosca","family":"Giannotti","sequence":"first","affiliation":[]},{"given":"Dino","family":"Pedreschi","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0743-1066(97)10004-8_BIB1","series-title":"Proceedings of the Third International Conference on Deductive and Object-Oriented Databases DOOD'93","first-page":"49","article-title":"Datalog with non deterministic choice computes NDB_PTIME","volume":"vol. 760","author":"Corciulo","year":"1993"},{"issue":"1","key":"10.1016\/S0743-1066(97)10004-8_BIB2","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","article-title":"Structure and complexity of relational queries","volume":"25","author":"Chandra","year":"1982","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0743-1066(97)10004-8_BIB3","series-title":"Proceedings of the First International Conference on Deductive and Object-oriented Databases DOOD'89","first-page":"7","article-title":"Object identity and inheritance in deductive databases: An evolutionary approach","author":"Zaniolo","year":"1989"},{"issue":"1\u20132","key":"10.1016\/S0743-1066(97)10004-8_BIB4","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1023\/A:1018999404360","article-title":"Programming with non determinism in deductive databases","volume":"19","author":"Giannotti","year":"1997","journal-title":"Ann. of Math. and Artificial Intelligence"},{"issue":"4","key":"10.1016\/S0743-1066(97)10004-8_BIB5","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","article-title":"Languages with capture complexity classes","volume":"16","author":"Immerman","year":"1987","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0743-1066(97)10004-8_BIB6","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF01530924","article-title":"Non determinism in logic based languages","volume":"3","author":"Abiteboul","year":"1991","journal-title":"Ann. of Math. and Artificial Intelligence"},{"key":"10.1016\/S0743-1066(97)10004-8_BIB7","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","article-title":"Relational queries computable in polynomial time","volume":"68","author":"Immerman","year":"1986","journal-title":"Inform. and Control"},{"key":"10.1016\/S0743-1066(97)10004-8_BIB8","series-title":"Proceedings of the ACM-SIGACT Symposium on the Theory of Computing","first-page":"137","article-title":"The complexity of relational query languages","author":"Vardi","year":"1982"},{"issue":"2","key":"10.1016\/S0743-1066(97)10004-8_BIB9","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0022-0000(90)90036-K","article-title":"Procedural languages for database queries and updates","volume":"41","author":"Abiteboul","year":"1990","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0743-1066(97)10004-8_BIB10","series-title":"Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems PODS 90","first-page":"218","article-title":"Non deterministic language to express deterministic transformation","author":"Abiteboul","year":"1990"},{"key":"10.1016\/S0743-1066(97)10004-8_BIB11","series-title":"Proceedings of the Fourth Symposium on Logic in Computer Science LICS'89","first-page":"71","article-title":"Fixpoint extension of first order logic and datalog like languages","author":"Abiteboul","year":"1989"},{"key":"10.1016\/S0743-1066(97)10004-8_BIB12","series-title":"Proceedings of the Third International Conference on Data and Knowledge Bases","first-page":"416","article-title":"Non deterministic choice in datalog","author":"Krishnamurthy","year":"1988"},{"key":"10.1016\/S0743-1066(97)10004-8_BIB13","series-title":"Proceedings of ACM Symposium on Principles of Database Systems PODS 90","first-page":"205","article-title":"Stable models and non determinism in logic programs with negation","author":"Sacc\u00e0","year":"1990"},{"key":"10.1016\/S0743-1066(97)10004-8_BIB14","series-title":"Proceedings of the Second International Conference on Deductive and Object-oriented Databases DOOD'91","first-page":"129","article-title":"Non determinism in deductive databases","volume":"vol. 566","author":"Giannotti","year":"1991"},{"key":"10.1016\/S0743-1066(97)10004-8_BIB15","series-title":"Foundations of Databases","author":"Abiteboul","year":"1995"},{"issue":"3","key":"10.1016\/S0743-1066(97)10004-8_BIB16","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0743-1066(95)00091-7","article-title":"Non determinism through well-founded choice","volume":"26","author":"Cheng","year":"1996","journal-title":"J. Logic Programming"},{"key":"10.1016\/S0743-1066(97)10004-8_BIB17","first-page":"1075","article-title":"Elements of relational database theory","volume":"vol. B","author":"Kanellakis","year":"1990"},{"key":"10.1016\/S0743-1066(97)10004-8_BIB18","volume":"vols. 1\/11","author":"Ullman","year":"1988"},{"key":"10.1016\/S0743-1066(97)10004-8_BIB19","series-title":"Data Base Systems","first-page":"33","article-title":"Relational completeness of database sublanguages","author":"Codd","year":"1972"},{"issue":"2","key":"10.1016\/S0743-1066(97)10004-8_BIB20","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/356924.356929","article-title":"Logic and databases: A deductive approach","volume":"16","author":"Gallaire","year":"1984","journal-title":"ACM Comput. Surveys"},{"key":"10.1016\/S0743-1066(97)10004-8_BIB21","first-page":"493","article-title":"Introduction to logic programming","volume":"vol. B","author":"Apt","year":"1990"},{"key":"10.1016\/S0743-1066(97)10004-8_BIB22","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0168-0072(86)90055-2","article-title":"Fixed-point extensions of first-order logic","volume":"32","author":"Gurevich","year":"1986","journal-title":"Ann. of Pure and Appl. Logic"},{"key":"10.1016\/S0743-1066(97)10004-8_BIB23","series-title":"A logical language for data and knowledge bases","author":"Naqvi","year":"1989"},{"issue":"1","key":"10.1016\/S0743-1066(97)10004-8_BIB24","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1109\/69.50907","article-title":"The LDL system prototype","volume":"2","author":"Chimenti","year":"1990","journal-title":"IEEE J. Data and Knowledge Engineering"},{"key":"10.1016\/S0743-1066(97)10004-8_BIB25","series-title":"Proceedings of the Fifth International Conference and Symposium on Logic Programming","first-page":"1070","article-title":"The stable model semantics for logic programming","author":"Gelfond","year":"1988"},{"key":"10.1016\/S0743-1066(97)10004-8_BIB26","article-title":"Non determinism in deductive databases (in Italian)","author":"Corciulo","year":"1993"},{"key":"10.1016\/S0743-1066(97)10004-8_BIB27","first-page":"61","article-title":"Declarative semantics for pruning operators in logic programming","volume":"1","author":"Giannotti","year":"1994","journal-title":"Methods of Logic in Computer Science"}],"container-title":["The Journal of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0743106697100048?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0743106697100048?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T10:22:40Z","timestamp":1555410160000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0743106697100048"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,4]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,4]]}},"alternative-id":["S0743106697100048"],"URL":"https:\/\/doi.org\/10.1016\/s0743-1066(97)10004-8","relation":{},"ISSN":["0743-1066"],"issn-type":[{"value":"0743-1066","type":"print"}],"subject":[],"published":{"date-parts":[[1998,4]]}}}