{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:28:18Z","timestamp":1761611298669},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540501718"},{"type":"electronic","value":"9783540459439"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1983]]},"DOI":"10.1007\/3-540-50171-1_17","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:16:25Z","timestamp":1330200985000},"page":"267-280","source":"Crossref","is-referenced-by-count":5,"title":["On the complexity of queries in the logical data model"],"prefix":"10.1007","author":[{"given":"Gabriel M.","family":"Kuper","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe Y.","family":"Vardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Abiteboul, S., Hull, R.: IFO, a formal semantic database model. ACM Trans. on Database Systems, Dec. 1987.","DOI":"10.1145\/32204.32205"},{"key":"17_CR2","unstructured":"Bennet, J.H.: On Spectra, Ph.D. Dissertation, Princeton University, 1962."},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Bancilhon, F., Khoshafian, S.: A calculus for complex objects. Proc. ACM Symp. on Principles of Database Systems, 1986.","DOI":"10.1145\/6012.15404"},{"key":"17_CR4","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A. Chandra","year":"1982","unstructured":"Chandra, A., Harel, D.: Structure and Complexity of Relational Queries. J. Computer and Systems Sciences 25(1982), pp. 99\u2013128.","journal-title":"J. Computer and Systems Sciences"},{"key":"17_CR5","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A.K. Chandra","year":"1981","unstructured":"Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. J. ACM 28(1981), pp. 114\u2013133.","journal-title":"J. ACM"},{"key":"17_CR6","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1145\/362384.362685","volume":"13","author":"E.F. Codd","year":"1970","unstructured":"Codd, E.F.: A relational model of data for large shared data banks. Comm. ACM 13(1970), pp. 377\u2013387.","journal-title":"Comm. ACM"},{"key":"17_CR7","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1145\/320107.320109","volume":"4","author":"E.F. Codd","year":"1979","unstructured":"Codd, E.F.: Extending the database relational model to capture more meaning. ACM Trans. on Database Systems, 4(1979), pp. 397\u2013434.","journal-title":"ACM Trans. on Database Systems"},{"key":"17_CR8","unstructured":"Fischer, P.C., Thomas, S.J.: Operators for non-first-normal-form relations. Proc. IEEE Computer Software Applications Conference, 1983, pp. 464\u2013475."},{"key":"17_CR9","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1145\/319587.319588","volume":"6","author":"M. Hammer","year":"1981","unstructured":"Hammer, M., McLeod, D.: Database description with SDM: a semantic database model. ACM Trans. on Database Systems, 6(1981), pp. 351\u2013386.","journal-title":"ACM Trans. on Database Systems"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"Hull, R., Su, J.: On the expressive power of database queries with intermediate types. Proc. ACM Symp. on Principles of Database Systems, 1988.","DOI":"10.1145\/308386.308409"},{"key":"17_CR11","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979."},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"Hull, R., Yap, C.K.: The format model: a theory of database organization. Proc. ACM Symp. on Principles of Database Systems, 1982.","DOI":"10.1145\/588111.588146"},{"key":"17_CR13","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1145\/322307.322310","volume":"29","author":"B.E. Jacobs","year":"1982","unstructured":"Jacobs, B.E.: On database logic. J. ACM 29(1982), pp. 310\u2013322.","journal-title":"J. ACM"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Jaeschke, B., Schek, H.J.: Remarks on the algebra of non-first-normal-form relations. Proc. ACM Symp. on Principles of Database Systems, 1982.","DOI":"10.1145\/588111.588133"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"Kuper, G.M.: The logical data model: a new approach to database logic. Ph.D. Dissertation, Stanford University, 1985.","DOI":"10.21236\/ADA141130"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Kuper, G.M., Vardi, M.Y.: A new approach to database logic. Proc. ACM Symp. on Principles of Database Systems, 1984.","DOI":"10.21236\/ADA141130"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Kuper, G.M., Vardi, M.Y.: On the expressive power of the logical data model. Proc. SIGMOD, 1985.","DOI":"10.1145\/318898.318915"},{"key":"17_CR18","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1145\/319540.319561","volume":"6","author":"D. Shipman","year":"1981","unstructured":"Shipman, D.: The functional model and the data language DAPLEX. ACM Trans. on Database Systems, 6(1981), pp. 140\u2013173.","journal-title":"ACM Trans. on Database Systems"},{"key":"17_CR19","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/359605.359620","volume":"20","author":"J.M. Smith","year":"1977","unstructured":"Smith, J.M., Smith, D.C.P.: Database abstractions: aggregation. Comm. ACM 20(1977), pp. 405\u2013413.","journal-title":"Comm. ACM"},{"key":"17_CR20","unstructured":"Stockmeyer, L.J.: The complexity of decision problems in automata theory and logic. Ph.D. Dissertation, MIT, 1974."},{"key":"17_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1977","unstructured":"Stockmeyer, L.J.: The polynomial time hierarchy. Theoretical Computer Science 3(1977), pp. 1\u201322.","journal-title":"Theoretical Computer Science"},{"key":"17_CR22","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: The complexity of relational query language. Proc. ACM Symp. on Theory of Computing, 1982.","DOI":"10.1145\/800070.802186"},{"key":"17_CR23","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/0304-3975(83)90038-5","volume":"23","author":"H. Volger","year":"1983","unstructured":"Volger, H.: Turing machines with bounded alternation. Theoretical Computer Science 23(1983), pp. 333\u2013337.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","ICDT '88"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-50171-1_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:17:29Z","timestamp":1605647849000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-50171-1_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983]]},"ISBN":["9783540501718","9783540459439"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-50171-1_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1983]]}}}