{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T06:38:46Z","timestamp":1780382326863,"version":"3.54.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1986,6,1]],"date-time":"1986-06-01T00:00:00Z","timestamp":517968000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[1986,6]]},"DOI":"10.1007\/bf00289111","type":"journal-article","created":{"date-parts":[[2004,10,4]],"date-time":"2004-10-04T17:55:24Z","timestamp":1096912524000},"page":"231-244","source":"Crossref","is-referenced-by-count":13,"title":["On the expressive power of data dependencies"],"prefix":"10.1007","volume":"23","author":[{"given":"Johann A.","family":"Makowsky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moshe Y.","family":"Vardi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1137\/0208017","volume":"8","author":"A.V. Aho","year":"1979","unstructured":"Aho, A.V., Sagiv, Y., Ullman, J.D.: Equivalence among relational expressions. SIAM J. Comput. 8, 218?246 (1979)","journal-title":"SIAM J. Comput."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1017\/S0305004100013463","volume":"31","author":"G. Birkhoff","year":"1935","unstructured":"Birkhoff, G.: On the structure of abstract algebras. Proc. Cambridge Phil. Soc. 31, 433?454 (1935)","journal-title":"Proc. Cambridge Phil. Soc."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1145\/1634.1636","volume":"31","author":"C Beeri","year":"1984","unstructured":"Beeri, C, Vardi, M.Y.: A proof procedure for data dependencies. J. ACM 31, 718?741 (1984)","journal-title":"J. ACM"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Harel, D.: Horn clauses and the fixpoint query hierarchy. Proc. ACM. Symp. Principles Database Syst., pp. 158?163. Los Angeles 1982; and: Horn clause queries and generalizations. J. Logic Programming 1, 1?15 (1985)","DOI":"10.1016\/0743-1066(85)90002-0"},{"key":"CR5","volume-title":"Model theory","author":"C.C. Chang","year":"1977","unstructured":"Chang, C.C., Keisler, H.J.: Model theory. Amsterdam: North-Holland 1977"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Lewis, H.R., Makowsky, J.A.: Embedded implicational dependencies and their inference problem. Proc. XP1 Workshop on Relational Database Theory, Stony Brook, June 1980 and, in a modified version, Proc. 13th ACM Symp. on Theory of Computing, 1981, Milwaukee, pp. 342?354. (Full version to appear in J. Comput. Syst. Sci.)","DOI":"10.1145\/800076.802488"},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational databases. Proc. 9th ACM Symp. on Theory Comput. 77?90 (1977)","DOI":"10.1145\/800105.803397"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1145\/362384.362685","volume":"13","author":"E.F. Codd","year":"1970","unstructured":"Codd, E.F.: A relational model for large shared data bases. Commun. ACM 13, 377?387 (1970)","journal-title":"Commun. ACM"},{"key":"CR9","first-page":"33","volume-title":"Data Base Systems","author":"E.F. Codd","year":"1972","unstructured":"Codd, E.F.: Further normalization of the database relational model. In Data Base Systems (R Rustin, ed.), pp. 33?64. Englewood Cliffs: Prentice-Hall 1972"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1145\/321978.321991","volume":"23","author":"M.A. Emden van","year":"1976","unstructured":"van Emden, M.A., Kowalski, R.A.: The semantics of predicate logic as a programming language. J. ACM 23, 733?742 (1976)","journal-title":"J. ACM"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/320557.320571","volume":"2","author":"R. Fagin","year":"1977","unstructured":"Fagin, R.: Multivalued dependencies and a new normal form for relational databases. ACM Trans. Database Syst. 2, 262?278 (1977)","journal-title":"ACM Trans. Database Syst."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1145\/322344.322347","volume":"29","author":"R. Fagin","year":"1982","unstructured":"Fagin, R.: Horn clauses and database dependencies. J. Assoc. Comput. Mach. 29, 252?285 (1982)","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0304-3975(83)90019-1","volume":"29","author":"S. Ginsburg","year":"1983","unstructured":"Ginsburg, S., Hull, R.: Characterization for functional dependency and Boyce-Codd normal form families. Theor. Comput. Sci. 29, 243?284 (1983)","journal-title":"Theor. Comput. Sci."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1145\/4904.4798","volume":"33","author":"M.H. Graham","year":"1986","unstructured":"Graham, M.H., Mendelzon, A.O., Vardi, M.Y.: Notions of dependency satisfaction. J. ACM 33, 105?129 (1986)","journal-title":"J. ACM"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"Graham, M.H., Vardi, M.Y.: On the complexity and axiomatizability of consistents database states. Proc. of 3rd ACM Symp. on Principles of Database Systems. pp. 281?283. Waterloo 1984","DOI":"10.1145\/588011.588052"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1145\/322326.322331","volume":"29","author":"S. Ginsburg","year":"1982","unstructured":"Ginsburg, S., Zaiddan, S.M.: Properties of functional dependencies families. J. Assoc. Comput. Mach. 29, 678?698 (1982)","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR17","series-title":"Lect. Notes Math.","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BFb0099486","volume-title":"Computation and Proof Theory","author":"Y. Gurevich","year":"1984","unstructured":"Gurevich, Y.: Toward Logic Tailored for Computational Complexity. In: Computation and Proof Theory. (M.M. Richter and E. B\ufffdrger, eds.), pp. 175?216. Lect. Notes Math. 1104. Berlin, Heidelberg, New York: Springer 1984"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/322326.322330","volume":"29","author":"P. Honeyman","year":"1982","unstructured":"Honeyman, P.: Testing satisfaction of functional dependencies. J. Assoc. Comput. Mach. 29, 668?677 (1982)","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1145\/62.2162","volume":"31","author":"R. Hull","year":"1984","unstructured":"Hull, R.: Finitely specifiable implicational dependencies families. J. ACM 31, 210?226 (1984)","journal-title":"J. ACM"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1145\/319702.319730","volume":"7","author":"B.E. Jacobs","year":"1982","unstructured":"Jacobs, B.E., Aronson, A.R., Klug, A.C.: On interpretations of relational languages and solutions to the implied constraint problem. ACM Trans. Database Syst. 7, 291?315 (1982)","journal-title":"ACM Trans. Database Syst."},{"key":"CR21","volume-title":"Answering questions by computer: A logical study. RM-5428-PR","author":"J.L. Kuhns","year":"1967","unstructured":"Kuhns, J.L.: Answering questions by computer: A logical study. RM-5428-PR, Rand Corp., Santa Monica, Ca., Dec. 1967"},{"key":"CR22","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1007\/3-540-10843-2_8","volume-title":"Proc. 8th Int'l Colloq. on Automata, Languages and Programming, Acre, 1981","author":"J.A. Makowsky","year":"1981","unstructured":"Makowsky, J.A.: Characterizing database dependencies. Proc. 8th Int'l Colloq. on Automata, Languages and Programming, Acre, 1981. Lect. Notes Comput. Sci. 115, pp. 86?97. Berlin, Heidelberg, New York: Springer 1981"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0049-237X(08)71821-4","volume-title":"Logic Colloquium '82","author":"J.A. Makowsky","year":"1984","unstructured":"Makowsky, J.A.: Model theoretic issues in computer science, Part I: Relational data bases and abstract data types. In: Logic Colloquium '82 (G. Lolli, G. Longo and A. Marcja, eds.), pp. 303?343. Amsterdam: North Holland 1984"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/3-540-15198-2_24","volume":"185","author":"J.A. Makowsky","year":"1985","unstructured":"Makowsky, J.A.: Why Horn formulas matter in computer science: Initial structures and generic examples, Mathematical Foundations of Software Development, CAAP, Lect. Notes Comput. Sci. 185, 374?385 (1985). (Full paper to appear J. Comput. Syst. Sci.)","journal-title":"CAAP, Lect. Notes Comput. Sci."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1016\/S0049-237X(08)71960-8","volume-title":"Logic Colloquium '73","author":"J.A. Makowsky","year":"1975","unstructured":"Makowsky, J.A.: Securable quantifiers, k-unions and admissible sets. In: Logic Colloquium '73 (E. Rose and J. Shepherdson eds.), pp. 409?428. Amsterdam: North Holland 1975"},{"issue":"1","key":"CR26","doi-asserted-by":"crossref","first-page":"42","DOI":"10.2307\/2273786","volume":"50","author":"J.A. Makowsky","year":"1985","unstructured":"Makowsky, J.A.: Vop?nka's Principle and Compact Logies. J. Symb. Logic 50 (1), 42?48 (1985)","journal-title":"J. Symb. Logic"},{"key":"CR27","volume-title":"Algebraic systems","author":"A.I. Malc'ev","year":"1973","unstructured":"Malc'ev, A.I.: Algebraic systems. Berlin, Heidelberg, New York: Springer 1973"},{"key":"CR28","doi-asserted-by":"crossref","first-page":"61","DOI":"10.2307\/2268172","volume":"8","author":"J.C.C. McKinsey","year":"1943","unstructured":"McKinsey, J.C.C.: The decision problem for some classes of sentences without quantifiers. J. Symb. Logic 8, 61?76 (1943)","journal-title":"J. Symb. Logic"},{"key":"CR29","volume-title":"Principles of Database Systems","author":"J.D. Ullman","year":"1983","unstructured":"Ullman, J.D.: Principles of Database Systems. Potomac, M.D.: Computer Science Press 1983"},{"key":"CR30","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: On the integrity of databases with incomplete information. Proc. of the 5th ACM Symp. on Principles of Database systems, pp. 252?266. Boston 1986","DOI":"10.1145\/6012.15419"},{"key":"CR31","doi-asserted-by":"crossref","unstructured":"Yannakakis, M., Papadimitriou, C: Algebraic dependencies. 21st IEEE Ann. Symp. on Found, of Computer Science, pp. 328?332 (1980). (To appear in J. Comput. Syst. Sci.)","DOI":"10.1109\/SFCS.1980.10"},{"key":"CR32","unstructured":"Zaniolo, C.: Analysis and design of relational schemata for database systems, Ph. D. Thesis, Technical Report UCLA-ENG-7769, UCLA, 1976"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00289111.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00289111\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00289111","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T08:02:28Z","timestamp":1585900948000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00289111"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,6]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1986,6]]}},"alternative-id":["BF00289111"],"URL":"https:\/\/doi.org\/10.1007\/bf00289111","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,6]]}}}