{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T15:20:04Z","timestamp":1648567204326},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"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":[[2006,11,2]]},"DOI":"10.1007\/s00236-006-0025-9","type":"journal-article","created":{"date-parts":[[2006,10,10]],"date-time":"2006-10-10T16:15:20Z","timestamp":1160496920000},"page":"341-370","source":"Crossref","is-referenced-by-count":1,"title":["A semantic approach to optimize linear datalog programs"],"prefix":"10.1007","volume":"43","author":[{"given":"Jos\u00e9 R.","family":"Param\u00e1","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nieves R.","family":"Brisaboa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miguel R.","family":"Penabad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u00c1ngeles S.","family":"Places","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"25_CR1","unstructured":"Db2 query patroller: Query processing. URL: http:\/\/www- 06.ibm.com\/software\/data\/db2\/querypatroller\/queryprocessing.html."},{"issue":"6","key":"25_CR2","first-page":"282","volume":"32","author":"S. Abiteboul","year":"1989","unstructured":"Abiteboul S. (1989): Boundedness is undecidable for datalog programs with a single recursive rule. Inf. Process. Lett. 32(6): 282\u2013287","journal-title":"Inf. Process. Lett."},{"key":"25_CR3","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison Wesley, Reading (1995)"},{"issue":"3","key":"25_CR4","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1145\/320083.320091","volume":"4","author":"A.V. Aho","year":"1979","unstructured":"Aho A.V., Beeri C., Ullman J.D. (1979): The theory of joins in relational databases. ACM Trans. Database Syst. 4(3):297\u2013314","journal-title":"ACM Trans. Database Syst."},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"Armstong, W.W.: Dependency structures of data base relationships. In Proc. 1974 IFIP Congress, pp. 580\u2013583 (1974)","DOI":"10.1515\/9783110840308-026"},{"key":"25_CR6","doi-asserted-by":"crossref","unstructured":"Bancilhon, F., Maier, D., Sagiv, Y., Ullman, J.D.: Magic sets and other strange ways to implement logic programs. In Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pp. 1\u201316, Cambridge, Massachusetts, 24\u201326 March (1986)","DOI":"10.1145\/6012.15399"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Bancilhon, F., Ramakrishnan, R.: An amateur\u2019s introduction to recursive query processing strategies. In Proceedings of ACM SIGMOD International Conference on Management of Data, Washington, DC, pp. 16\u201352. ACM, New York (1986)","DOI":"10.1145\/16894.16859"},{"key":"25_CR8","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. (1984): A proof procedure for data dependencies. J. ACM, 31, 718\u2013741","journal-title":"J. ACM"},{"key":"25_CR9","doi-asserted-by":"crossref","unstructured":"Brisaboa, N.R.: Gonzalez-Tuchmann, A. Hern\u00e1ndez, H. J. and Jos\u00e9 R. Param\u00e1. The chase of datalog programs. In Advances in Databases: proceedings of 16th British National Conference on Databases, BNCOD16, of Lecture Notes in Computer Science, vol. 1405\u00a0pp. 165\u2013166. Springer, Berlin Heidelberg New York (1998)","DOI":"10.1007\/BFb0053479"},{"key":"25_CR10","unstructured":"Brisaboa, N.R., Gonzalez-Tuchmann, A., Hern\u00e1ndez, H.J., Param\u00e1, J.R.: Chasing programs in datalog. In Proceedings of the 6th International Workshop on Deductive Databases and Logic Programming DDLP98, pp. 13\u201323. GMD- Forschungzentrum Informationstechnik GmbH 1998 (GMD Report 22) (1998)"},{"key":"25_CR11","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/B978-0-934613-40-8.50011-7","volume-title":"Foundations of Deductive Databases and Logic Programming.","author":"U.S. Chakravarthy","year":"1988","unstructured":"Chakravarthy U.S., Grant J., Minker J. (1988): Foundations of semantic query optimization for deductive databases. In: Minker J. (eds) Foundations of Deductive Databases and Logic Programming. Morgan Kauffmann Publishers, San Fransisco, pp. 243\u2013273"},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"Cosmadakis, S.S.: On the first-order expressibility of recursive queries. In: ACM, (ed.), Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 311\u2013323 (1989)","DOI":"10.1145\/73721.73752"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Cosmadakis, S.S., Kanellakis, P.C.: Parallel evaluation of recursive rule queries. In: Proceedings of Fifth ACM SIGACT-SIGMOD Symposium on Principle of Database Systems, pp. 280\u2013293 (1986)","DOI":"10.1145\/6012.15421"},{"key":"25_CR14","doi-asserted-by":"crossref","unstructured":"Deutsch, A., Ludascher, B., Nash, A.: Rewriting queries using views with access patterns under integrity constraints. In Proceedings of ICDT 2005, 10th International Conference on Database Theory, of Lecture Notes in Computer Science, vol. 3363, pp. 352\u2013367. Springer, Berlin Heidelberg New York (2005)","DOI":"10.1007\/978-3-540-30570-5_24"},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"Deutsch, A., Tannen, V.: Reformulation of XML queries and constraints. In Proceedings of ICDT 2003, 9th International Conference on Database Theory, Lecture Notes in Computer Science, vol. 2572\u00a0pp. 225\u2013241. Springer, Berlin Heidelberg New York (2003)","DOI":"10.1007\/3-540-36285-1_15"},{"issue":"4","key":"25_CR16","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1145\/322217.322228","volume":"27","author":"P.J. Downey","year":"1980","unstructured":"Downey P.J., Sethi R., Tarjan R. (1980): Variations on the common subexpression problem. JACM: Journal of the ACM 27(4): 758\u2013771","journal-title":"JACM: Journal of the ACM"},{"key":"25_CR17","unstructured":"Gaifman, H., Mairson, H.G., Sagiv, Y., Vardi, M.Y.: Undecidable optimization problems for database logic programs. In: Proceedings of 2nd IEEE Symp. on Logic in Computer Science, pp. 106\u2013115 (1987)"},{"issue":"3","key":"25_CR18","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF01840452","volume":"1","author":"Y.E. Ioannidis","year":"1986","unstructured":"Ioannidis Y.E. (1986): A time bound on the materialization of some recursively defined views. Algorithmica 1(3):361\u2013385","journal-title":"Algorithmica"},{"key":"25_CR19","doi-asserted-by":"crossref","unstructured":"Lakshmanan, L.V.S., Hern\u00e1ndez, H.J.: Structural query optimization \u2013 a uniform framework for semantic query optimization in deductive databases. In: Proceedings of Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principle of Database Systems, pp. 102\u2013114 (1991)","DOI":"10.1145\/113413.113423"},{"key":"25_CR20","doi-asserted-by":"crossref","unstructured":"Lerat, N.: Query processing in incomplete logical databases. In: Ausiello, G., Atzeni, P., (ed.) Proceedings of ICDT\u201986, International Conference on Database Theory, of Lecture Notes in Computer Science, vol. 243\u00a0pp. 260\u2013277. Springer, Berlin Heidelberg New York (1986)","DOI":"10.1007\/3-540-17187-8_41"},{"key":"25_CR21","volume-title":"The Theory of Relational Databases","author":"D. Maier","year":"1983","unstructured":"Maier D. (1983): The Theory of Relational Databases. Computer Science Press, Mary Land"},{"issue":"4","key":"25_CR22","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1145\/320107.320115","volume":"4","author":"D. Maier","year":"1979","unstructured":"Maier D., Mendelzon A.O., Sagiv Y. (1979): Testing implications of data dependencies. ACM Trans. Database Syst. 4(4):455\u2013469","journal-title":"ACM Trans. Database Syst."},{"key":"25_CR23","doi-asserted-by":"crossref","unstructured":"Marcinkowski, J.: The 3 frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG programs. In STACS, pp. 427\u2013438 (1996)","DOI":"10.1007\/3-540-60922-9_35"},{"key":"25_CR24","volume-title":"SQL:1999 Understanding Relational Language Components","author":"J. Melton","year":"2002","unstructured":"Melton J., Simon A.R. (2002): SQL:1999 Understanding Relational Language Components. Morgan Kaufmann, San Fransisico"},{"issue":"1","key":"25_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0306-4379(83)90024-8","volume":"8","author":"J. Minker","year":"1982","unstructured":"Minker J., Nicolas J.M. (1982): On recursive axioms in deductive databases. Inf. Syst. 8(1):1\u201313","journal-title":"Inf. Syst."},{"key":"25_CR26","doi-asserted-by":"crossref","unstructured":"Naughton, J. Data independent recursion in deductive databases. In: Proceedings of Fifth ACM SIGACT-SIGMOD Symposium on Principle of Database Systems, pp. 267\u2013279 (1986)","DOI":"10.1145\/6012.15420"},{"key":"25_CR27","doi-asserted-by":"crossref","unstructured":"Naughton, J. Sagiv, Y.: A decidable class of bounded recursions. In: Proc. Sixth ACM SIGACT-SIGMOD Symposium on Principle of Database Systems, pp. 227\u2013236 (1987)","DOI":"10.1145\/28659.28684"},{"key":"25_CR28","doi-asserted-by":"crossref","unstructured":"Naughton, J.F., Ramakrishnan, R., Sagiv, Y., Ullman, J.D.: Efficient evaluation of right-, left-, and multi-linear rules. ACM SIGMOD RECORD, 18(2) June (1989) Also published in\/as: 19 ACM SIGMOD Conf. on the Management of Data, (Portland OR), May-June (1989)","DOI":"10.1145\/66926.66948"},{"key":"25_CR29","doi-asserted-by":"crossref","unstructured":"Papakonstantinou, Y., Vassalos, V.: Query rewriting for semistructured data. In SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, pp. 455\u2013466 (1999)","DOI":"10.1145\/304181.304222"},{"key":"25_CR30","doi-asserted-by":"crossref","unstructured":"Param\u00e1, J.R., Brisaboa, N.R., Penabad, M.R., Places, A.S.: A semantic query optimization approach to optimize linear datalog programs. In Proceedings of the Sixth East-European Conference on Advances in Databases and Information Systems, of Lecture Notes in Computer Science. vol. 2435 Springer, Berlin Heidelberg New York (2002)","DOI":"10.1007\/3-540-45710-0_22"},{"key":"25_CR31","doi-asserted-by":"crossref","unstructured":"Param\u00e1, J.R., Brisaboa, N.R., Penabad, M.R., Places, A.S.: Implication of functional dependencies for recursive queries. In: Proceedings of Andrei Ershov Fifth International Conference, PSI 2003,of Lecture Notes in Computer Science. vol. 2890 Springer, Berlin Heidelberg New York (2003)","DOI":"10.1007\/978-3-540-39866-0_49"},{"key":"25_CR32","unstructured":"Popa, L.: Object\/relational query optimization with Chase and Backchase. PhD Thesis, University of Pennsylvania, (2000)"},{"key":"25_CR33","doi-asserted-by":"crossref","unstructured":"Popa, L., Deutsch, A., Sahuguet, A., Tannen, V.: A chase too far? In: Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, Dallas, TX, pp. 273\u2013284. ACM, New York (2000)","DOI":"10.1145\/335191.335421"},{"key":"25_CR34","unstructured":"Ramakrishnan, R.: Magic templates: A spellbinding approach to logic programs. In: R. A. Kowalski and K. A. Bowen, (ed.), Proceedings of the Fifth International Conference and Symposium on Logic Programming, pp. 140\u2013159, ALP, IEEE, The MIT Press. Seatle (1988)"},{"key":"25_CR35","unstructured":"Ramakrishnan, R., Bothner, P., Srivastava, D., Sudarshan, S.: Coral: A databases programming language. Tech. Rep. TR-CS-90-14, Kansas State University, Department of Computing and Information Sciences, (1990)"},{"issue":"2","key":"25_CR36","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1145\/232616.232628","volume":"21","author":"K.A. Ross","year":"1996","unstructured":"Ross K.A. (1996): Tail recursion elimination in deductive databases. ACM Trans. Database Syst. 21(2):208\u2013237","journal-title":"ACM Trans. Database Syst."},{"key":"25_CR37","doi-asserted-by":"crossref","unstructured":"Sagiv, Y.: Optimizing datalog programs. In: Jack Minker, (ed.), Foundations of Deductive Databases and Logic Programming, chap. 17, pp. 659\u2013698. Morgan Kauffmann Publishers, San Fransisco (1987)","DOI":"10.1145\/28659.28696"},{"key":"25_CR38","volume-title":"Principles of Database And Knowledge-Base Systems, vol. 1","author":"J.D. Ullman","year":"1988","unstructured":"Ullman J.D. (1988): Principles of Database And Knowledge-Base Systems, vol. 1. Computer Science Press, Mary Land"},{"key":"25_CR39","volume-title":"Principles of Database And Knowledge-Base Systems, vol. 2","author":"J.D. Ullman","year":"1989","unstructured":"Ullman J.D. (1989): Principles of Database And Knowledge-Base Systems, vol. 2. Computer Science Press, Mary Land"},{"key":"25_CR40","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: Decidability and undecidability results for boundedness of linear recursive queries. In: Proceedings of Seventh ACM SIGACT-SIGMOD Symposium on Principle of Database Systems, pp. 341\u2013351 (1988)","DOI":"10.1145\/308386.308470"},{"issue":"4","key":"25_CR41","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0020-0190(92)90083-8","volume":"44","author":"K. Wang","year":"1992","unstructured":"Wang K., Yuan L.Y. (1992): Preservation of integrity constraints in definite datalog programs. Inf. Process. Lett. 44(4): 185\u2013193","journal-title":"Inf. Process. Lett."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-006-0025-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-006-0025-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-006-0025-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T13:41:53Z","timestamp":1558705313000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-006-0025-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,10,11]]},"references-count":41,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2006,11,2]]}},"alternative-id":["25"],"URL":"https:\/\/doi.org\/10.1007\/s00236-006-0025-9","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,10,11]]}}}