{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T13:26:49Z","timestamp":1726406809573},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540637745"},{"type":"electronic","value":"9783540696452"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63774-5_97","type":"book-chapter","created":{"date-parts":[[2006,7,17]],"date-time":"2006-07-17T14:30:57Z","timestamp":1153146657000},"page":"53-69","source":"Crossref","is-referenced-by-count":0,"title":["The fundamental problem of database design"],"prefix":"10.1007","author":[{"given":"J. A.","family":"Makowsky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"E. V.","family":"Ravve","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,7,29]]},"reference":[{"key":"4_CR1","unstructured":"S. Abiteboul, R. Hull, and V. Vianu. Foundations of Database. Addison Wesley, 1994."},{"issue":"4","key":"4_CR2","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1145\/319628.319634","volume":"6","author":"F. Bancilhon","year":"1981","unstructured":"F. Bancilhon and N. Spyratos. Update semantics of relational views. ACM Transactions on Database Systems, 6(4):557\u2013575, 1981.","journal-title":"ACM Transactions on Database Systems"},{"key":"4_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(90)90080-L","volume":"48","author":"K.J. Compton","year":"1990","unstructured":"K.J. Compton and C.W. Henson. A uniform method for proving lower bounds on the computational complexity of logical theories. Annals of Pure and Applied Logic, 48:1\u201379, 1990.","journal-title":"Annals of Pure and Applied Logic"},{"key":"4_CR4","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0304-3975(94)90268-2","volume":"126","author":"B. Courcelle","year":"1994","unstructured":"B. Courcelle. Monadic second order graph transductions: A survey. Theoretical Computer Science, 126:53\u201375, 1994.","journal-title":"Theoretical Computer Science"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"E. Dahlhaus. Reductions to NP-complete problems by interpretations. In E. B\u00f6rger et. al., editor, Logic and Machines: Decision Problems and Complexity, volume 171, pages 357\u2013365. Springer Verlag, 1983.","DOI":"10.1007\/3-540-13331-3_51"},{"key":"4_CR6","unstructured":"A. Dawar. Feasible Computation Through Model Theory. PhD thesis, Department of Computer Science, University of Maryland, 1993."},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"H.D. Ebbinghaus, J. Flum, and W. Thomas. Mathematical Logic, 2nd edition. Undergraduate Texts in Mathematics. Springer-Verlag, 1994.","DOI":"10.1007\/978-1-4757-2355-7"},{"issue":"3","key":"4_CR8","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1145\/319587.319592","volume":"6","author":"R. Fagin","year":"1981","unstructured":"R. Fagin. A normal form for relational databases that is based on domains and keys. ACM Transactions on Database Systems, 6(3):387\u2013415, 1981.","journal-title":"ACM Transactions on Database Systems"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"R. Fagin and M. Vardi. The theory of data dependencies. In M. Anshel and W. Gewirtz, editors, Proceedings of Symposia in Applied Mathematics, volume 34 of American Mathematical Society, pages 19\u201371. RI, 1986.","DOI":"10.1090\/psapm\/034\/846853"},{"key":"4_CR10","volume-title":"Grundlagen der Mathematik, I, volume 40 of Die Grundleheren der mathematischen Wissenschaften in Einzeldarstellungn","author":"D. Hilbert","year":"1970","unstructured":"D. Hilbert and P. Bernays. Grundlagen der Mathematik, I, volume 40 of Die Grundleheren der mathematischen Wissenschaften in Einzeldarstellungn. Springer Verlag, Heidelberg, 2nd edition, 1970.","edition":"2nd edition"},{"key":"4_CR11","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1006\/inco.1995.1148","volume":"122","author":"C. Herrmann","year":"1995","unstructured":"C. Herrmann. On the ubdecidability of implication between embedded multivalued database dependencies. Information and Computation, 122:221\u2013235, 1995.","journal-title":"Information and Computation"},{"issue":"4","key":"4_CR12","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 on Computing, 16(4):760\u2013778, Aug 1987.","journal-title":"SIAM Journal on Computing"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"P.G. Kolaitis. Implicit definability on finite structures and unambiguous computations. In LiCS'90, pages 168\u2013180. IEEE, 1990.","DOI":"10.1109\/LICS.1990.113743"},{"issue":"2","key":"4_CR14","first-page":"145","volume":"14","author":"A. Keller","year":"1984","unstructured":"A. Keller and J.D. Ullman. On complementary and independent mappings on databases. Proceedings of ACM SIGMOD Annual Meeting on the Management of Data, 14(2):145\u2013148, 1984.","journal-title":"Proceedings of ACM SIGMOD Annual Meeting on the Management of Data"},{"key":"4_CR15","unstructured":"D. Maier. The Theory of Relational Databases. Computer Science Press, 1983."},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"J.A. Makowsky. Capturing complexity classes with Lindstr\u00f6m quantifiers. In MFCS'94, volume 841 of Lecture Notes in Computer Science, pages 68\u201371. Springer Verlag, 1994.","DOI":"10.1007\/3-540-58338-6_59"},{"key":"4_CR17","unstructured":"H. Mannila and K. J. R\u00e4ih\u00e4. The Design of Relational Databases. Addison-Wesley, 1992."},{"key":"4_CR18","volume-title":"Dependency preserving refinement of database schemes","author":"J.A. Makowsky","year":"1996","unstructured":"J.A. Makowsky and E. Ravve. Dependency preserving refinement of database schemes. Technical Report, April 1996, Department of Computer Science, Technion-Israel Institute of Technology, Haifa, Israel, 1996."},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"J.A. Makowsky and E. Ravve. Translation schemes and the fundamental problem of database design. In Conceptual Modeling-ER'96, volume 1157 of Lecture Notes in Computer Science, pages 5\u201326. Springer Verlag, 1996.","DOI":"10.1007\/BFb0019911"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"J.A. Makowsky and E. Ravve. Dependency preserving refinements and the fundamental problem of database design. In Data and Knowledge Engineering, to appear 1997.","DOI":"10.1016\/S0169-023X(97)00029-3"},{"volume-title":"The Structure of the Relational Database Model, volume 17 of EATCS Monographs on Theoretical Computer Science","year":"1989","key":"4_CR21","unstructured":"J. Paredaens, P. De Bra, M. Gyssens, and D. Van Gucht, editors. The Structure of the Relational Database Model, volume 17 of EATCS Monographs on Theoretical Computer Science. Springer Verlag, Heidelberg, 1989."},{"key":"4_CR22","unstructured":"M.A. Rabin. A simple method for undecidability proofs and some applications. In Y. Bar Hillel, editor, Logic, Methodology and Philosophy of Science II, Studies in Logic, pages 58\u201368. North Holland, 1965."},{"key":"4_CR23","unstructured":"E. Ravve. Ph.D. Thesis, Department of Computer Science, Technion-Israel Institute of Technology, to be completed in 1998."},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"B. Thalheim. Dependencies in Relational Databases, volume 126 of Teubner-Texte zur Mathematik. B.G. Teubner Verlagsgesellschaft, Leipzig, 1991.","DOI":"10.1007\/978-3-663-12018-6"},{"key":"4_CR25","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/BF01556354","volume":"7","author":"B. Thalheim","year":"1993","unstructured":"B. Thalheim. Foundation of entity-relationship modeling. Annals of Mathematics and Artificial Intelligence, 7:197\u2013256, 1993.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"4_CR26","unstructured":"B. Thalheim. A survey on database constraints. Reine Informatik I-8\/1994, Fakult\u00e4t f\u00fcr Mathematik, Naturwissenschaften and Informatik, 1994."},{"key":"4_CR27","unstructured":"J.D. Ullman. Principles of Database Systems. Principles of Computer Science Series. Computer Science Press, 2nd edition, 1982."},{"key":"4_CR28","unstructured":"J. Ullman and J. Widom. A First Course in Databases System. Prentice-Hall, 1997."},{"key":"4_CR29","unstructured":"M. Vardi. Fundamentals of dependency theory. In Trends in Theoretical Computer Science, pages 171\u2013224. Computer Science Press, 1987."}],"container-title":["Lecture Notes in Computer Science","SOFSEM'97: Theory and Practice of Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63774-5_97","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T02:05:34Z","timestamp":1555725934000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63774-5_97"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540637745","9783540696452"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-63774-5_97","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}