{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,7]],"date-time":"2023-01-07T14:30:13Z","timestamp":1673101813838},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[1986,3]]},"abstract":"\n In [10] a method is proposed for decomposing join dependencies (jds) in a relational database using the notion of a hinge. This method was subsequently studied in [11] and [12]. We show how the technique of decomposition can be used to make integrity checking more efficient. It turns out that it is important to find a decomposition that minimizes the number of edges of its largest element. We show that the decompositions obtained with the method described in [10] are optimal in this respect. This minimality criterion leads to the definition of the\n degree of cyclicity<\/jats:italic>\n , which allows us to classify jds and leads to the notion of\n n-cyclicity<\/jats:italic>\n , of which acyclicity is a special case for n = 2. We then show that, for a fixed value of n (which may be greater than 2). integrity checking can be performed in polynomial time provided we restrict ourselves to\n n-cyclic<\/jats:italic>\n jds. Finally, we generalize a well-known characterization for acyclic jds by proving that n-cyclicity is equivalent to \u201cn-wise consistency implies global consistency.\u201d As a consequence, consistency checking can be performed in polynomial time if we restrict ourselves to n-cyclic jds, for a tired value of n, not necessarily equal to 2.\n <\/jats:p>","DOI":"10.1145\/5236.5237","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:31:44Z","timestamp":1027769504000},"page":"81-108","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["On the complexity of join dependencies"],"prefix":"10.1145","volume":"11","author":[{"given":"Marc","family":"Gyssens","sequence":"first","affiliation":[{"name":"Univ. of Antwerp"}]}],"member":"320","published-online":{"date-parts":[[1986,3]]},"reference":[{"key":"e_1_2_1_1_2","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320091"},{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802489"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322389"},{"key":"e_1_2_1_4_2","volume-title":"Graphes et Hypergraphes","author":"BERGI~ C.","year":"1970","unstructured":"BERGI~ , C. Graphes et Hypergraphes . Dunod , Paris , 1970 . BERGI~, C. Graphes et Hypergraphes. Dunod, Paris, 1970."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"e_1_2_1_6_2","volume-title":"Further normalizations of the relational data base model","author":"CODD E.F.","year":"1972","unstructured":"CODD , E.F. Further normalizations of the relational data base model . In Data Base Systems, R. Rustin, Ed., Prentice Hall , Englewood Cliffs, N.J. , 1972 , 33-64. CODD, E.F. Further normalizations of the relational data base model. In Data Base Systems, R. Rustin, Ed., Prentice Hall, Englewood Cliffs, N.J., 1972, 33-64."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/320557.320571"},{"key":"e_1_2_1_8_2","volume-title":"Proceedings o\/CAAP I983 (L'Aquila","author":"FA IN, R","year":"1983","unstructured":"FA (; IN, R . Acyclic database schemes (of various degrees): A painless introduction . In Proceedings o\/CAAP I983 (L'Aquila , 1983 ). FA(;IN, R. Acyclic database schemes (of various degrees): A painless introduction. In Proceedings o\/CAAP I983 (L'Aquila, 1983)."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/319732.319735"},{"key":"e_1_2_1_10_2","volume-title":"Advances in Database Theory, vol 2","author":"GYSSENS M.","year":"1973","unstructured":"GYSSENS , M. , AND PAREDAENS , J. A decomposition methodology for cyclic databases . In Advances in Database Theory, vol 2 , H. Gallaire, J. Minker, and J. M. Nicolas, Eds., Plenum Press , New York , 1973 . GYSSENS, M., AND PAREDAENS, J. A decomposition methodology for cyclic databases. In Advances in Database Theory, vol 2, H. Gallaire, J. Minker, and J. M. Nicolas, Eds., Plenum Press, New York, 1973."},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/588011.588032"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/325405.325441"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320115"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/648217.751067"},{"key":"e_1_2_1_16_2","first-page":"537","volume-title":"Proceedings of the 7th Symposium on the Mathematical Foundations of Computer Science: Lecture Notes in Computer Sc&nce 64","author":"RISSANEN J.","year":"1978","unstructured":"RISSANEN , J. Theory of joins for relational databasesmA tutorial survey . In Proceedings of the 7th Symposium on the Mathematical Foundations of Computer Science: Lecture Notes in Computer Sc&nce 64 , Springer Verlag , 1978 , 537 - 551 . RISSANEN, J. Theory of joins for relational databasesmA tutorial survey. In Proceedings of the 7th Symposium on the Mathematical Foundations of Computer Science: Lecture Notes in Computer Sc&nce 64, Springer Verlag, 1978, 537-551."},{"key":"e_1_2_1_18_2","volume-title":"Principles of Database Systems","author":"ULLMAN J.","year":"1982","unstructured":"ULLMAN , J. Principles of Database Systems . 2 nd ed., Pitman , Marshfield, Mass ., 1982 . ULLMAN, J. Principles of Database Systems. 2nd ed., Pitman, Marshfield, Mass., 1982.","edition":"2"},{"key":"e_1_2_1_19_2","volume-title":"Dept. of Computer Science","author":"ZANIOLO C.","year":"1976","unstructured":"ZANIOLO , C. Analysis and design of relational schemata for database systems. Tech. Pep. UCLA-ENG-7669 , Dept. of Computer Science , Univ. of California , Los Angeles , 1976 . ZANIOLO, C. Analysis and design of relational schemata for database systems. Tech. Pep. UCLA-ENG-7669, Dept. of Computer Science, Univ. of California, Los Angeles, 1976."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/5236.5237","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T21:47:47Z","timestamp":1672696067000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/5236.5237"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,3]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1986,3]]}},"alternative-id":["10.1145\/5236.5237"],"URL":"http:\/\/dx.doi.org\/10.1145\/5236.5237","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":["Information Systems"],"published":{"date-parts":[[1986,3]]},"assertion":[{"value":"1986-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}