{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:41:19Z","timestamp":1787388079473,"version":"build-2736575974"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1988,2]]},"abstract":"<jats:p>A lossless database scheme with full implicational dependencies is considered. The following condition is necessary in order that restricted projections of the representative instance could be expressed in relational algebra (i.e., in first-order logic): The dependencies of the database scheme are equivalent to a single join dependency and some equality-generating dependencies. An important special case is when the database scheme has only full tuple-generating dependencies. In this case, restricted projections of the representative instance can be expressed in relational algebra if and only if the following condition is true: The dependencies of the database scheme are equivalent to a single join dependency. Testing this condition is decidable. This result also applies to the class of Horn-clause programs consisting only of typed rules with one predicate symbol R (and without function symbols). A program consisting of rules of this form is equivalent to a nonrecursive program if and only if it is equivalent to a project-join mapping. Finally, it is also shown that a tableau mapping is idempotent if and only if it is a project-join mapping.<\/jats:p>","DOI":"10.1137\/0217001","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:30:13Z","timestamp":1109226613000},"page":"1-22","source":"Crossref","is-referenced-by-count":14,"title":["On Bounded Database Schemes and Bounded Horn-Clause Programs"],"prefix":"10.1137","volume":"17","author":[{"given":"Yehoshua","family":"Sagiv","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"RABU","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320091"},{"key":"RASU1","doi-asserted-by":"publisher","DOI":"10.1137\/0208017"},{"key":"RASU2","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320112"},{"key":"RARM","first-page":"580","volume-title":"Information processing 74 (Proc. IFIP Congress, Stockholm, 1974)","author":"Armstrong W. W.","year":"1974"},{"key":"RAC","doi-asserted-by":"crossref","unstructured":"P. Atzeni, E. P. F. Chan,  Efficient query answering in the representative instance approach,  Proc. Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, Portland, OR,  1985,  181\u2013188, March","DOI":"10.1145\/325405.325429"},{"key":"RBB","doi-asserted-by":"publisher","DOI":"10.1145\/320064.320066"},{"key":"RBMSU","doi-asserted-by":"publisher","DOI":"10.1137\/0210025"},{"key":"RBV1","doi-asserted-by":"publisher","DOI":"10.1137\/0213006"},{"key":"RBV2","doi-asserted-by":"publisher","DOI":"10.1145\/1634.1636"},{"key":"RCM","doi-asserted-by":"crossref","unstructured":"Ashok K. Chandra, Philip M. Merlin,  Optimal implementation of conjunctive queries in relational data bases,  Conference Record of the Ninth Annual ACM Symposium on Theory of Computing (Boulder, Colo., 1977), Assoc. Comput. Mach., New York,  1977,  77\u201390, May 58:8576","DOI":"10.1145\/800105.803397"},{"key":"RCO","doi-asserted-by":"publisher","DOI":"10.1145\/362384.362685"},{"key":"RCK","doi-asserted-by":"crossref","unstructured":"S. S. Cosmadakis, P. C. Kanellakis,  Parallel evaluation of recursive rule queries,  Proc. Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, Boston, MA,  1986,  280\u2013292, March","DOI":"10.1145\/6012.15421"},{"key":"RFA","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322347"},{"key":"RFMUY","doi-asserted-by":"publisher","DOI":"10.1137\/0212003"},{"key":"RGM","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-3384-5"},{"key":"RGY","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90079-5"},{"key":"RHO","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322330"},{"key":"RIO","unstructured":"Y. E. Ioannidis,  A time bound on the materialization of some recursively defined views,  Proc. Internat. Conf. on Very Large Data Bases, Stockholm, Sweden,  1985"},{"key":"RIIK","doi-asserted-by":"publisher","DOI":"10.1137\/0214026"},{"key":"RMA","volume-title":"The theory of relational databases","author":"Maier David","year":"1983"},{"key":"RMMS","doi-asserted-by":"publisher","DOI":"10.1145\/320107.320115"},{"key":"RMUV","doi-asserted-by":"publisher","DOI":"10.1145\/329.318580"},{"key":"RME","doi-asserted-by":"publisher","DOI":"10.1145\/329.318579"},{"key":"RNA","doi-asserted-by":"crossref","unstructured":"J. Naughton,  Data independent recursion in deductive databases,  Proc. Fifth ACM SIGACT- SIGMOD Symposium on Principles of Database Systems, Boston, MA,  1986,  267\u2013279, March","DOI":"10.1145\/6012.15420"},{"key":"RSA1","doi-asserted-by":"crossref","unstructured":"Y. Sagiv,  Can we use the universal instance assumption without using nulls?  Proc. ACM-SIGMOD Internat. Conf. on Management of Data, Ann Arbor, MI,  1981,  108\u2013120, April","DOI":"10.1145\/582318.582336"},{"key":"RSA2","doi-asserted-by":"publisher","DOI":"10.1137\/0212020"},{"key":"RSA3","doi-asserted-by":"publisher","DOI":"10.1145\/319983.319988"},{"key":"RSA4","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102787"},{"key":"RSA5","unstructured":"Y. Sagiv,  Optimizing datalog programs,  Proc. Workshop on Foundations of Deductive Databases and Logic Programming, Washington, D.C.,  1986, August"},{"key":"RSY","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322221"},{"key":"RU1","volume-title":"Principles of database systems","author":"Ullman Jeffrey D.","year":"1982"},{"key":"RYA","unstructured":"M. Yannakakis,  Algorithms for acyclic database schemes,  Proc. Seventh Internat. Conf. on Very Large Data Bases,  1981,  82\u201394, September"},{"key":"RYP","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90008-3"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0217001","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:43:53Z","timestamp":1787337833000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0217001"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,2]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1988,2]]}},"alternative-id":["10.1137\/0217001"],"URL":"https:\/\/doi.org\/10.1137\/0217001","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,2]]}}}