{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T18:40:26Z","timestamp":1740336026529,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540212003"},{"type":"electronic","value":"9783540247418"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24741-8_26","type":"book-chapter","created":{"date-parts":[[2010,8,2]],"date-time":"2010-08-02T14:56:54Z","timestamp":1280761014000},"page":"441-458","source":"Crossref","is-referenced-by-count":9,"title":["Projection Pushing Revisited"],"prefix":"10.1007","author":[{"given":"Benjamin J.","family":"McMahan","sequence":"first","affiliation":[]},{"given":"Guoqiang","family":"Pan","sequence":"additional","affiliation":[]},{"given":"Patrick","family":"Porter","sequence":"additional","affiliation":[]},{"given":"Moshe Y.","family":"Vardi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"26_CR1","volume-title":"Foundations of databases","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of databases. Addison-Wesley, Reading (1995)"},{"key":"26_CR2","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1145\/320107.320112","volume":"4","author":"A. Aho","year":"1979","unstructured":"Aho, A., Sagiv, Y., Ullman, J.D.: Efficient optimization of a class of relational expressions. ACM Trans. on Database Systems\u00a04, 435\u2013454 (1979)","journal-title":"ACM Trans. on Database Systems"},{"key":"26_CR3","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1137\/0208017","volume":"8","author":"A. Aho","year":"1979","unstructured":"Aho, A., Sagiv, Y., Ullman, J.D.: Equivalence of relational expressions. SIAM Journal on Computing\u00a08, 218\u2013246 (1979)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"26_CR4","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1109\/TSE.1983.236170","volume":"9","author":"P. Apers","year":"1983","unstructured":"Apers, P., Hevner, A., Yao, S.: Optimization algorithms for distributed queries. IEEE Trans. Software Engineering\u00a09(1), 57\u201368 (1983)","journal-title":"IEEE Trans. Software Engineering"},{"issue":"2","key":"26_CR5","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM Journal of Algebraic and Discrete Methods\u00a08(2), 277\u2013284 (1987)","journal-title":"SIAM Journal of Algebraic and Discrete Methods"},{"key":"26_CR6","first-page":"1","volume":"11","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica\u00a011, 1\u201321 (1993)","journal-title":"Acta Cybernetica"},{"key":"26_CR7","unstructured":"Bouquet, F.: Gestion de la dynamicit\u00e9 et \u00e9num\u00e9ration d\u2019implicants premiers: une approche fond\u00e9e sur les Diagrammes de D\u00e9cision Binaire. PhD thesis, Universit\u00e9 de Provence, France (1999)"},{"key":"26_CR8","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational databases. In: Proc. 9th ACM Symp. on Theory of Computing, pp. 77\u201390 (1977)","DOI":"10.1145\/800105.803397"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Chauhan, P., Clarke, E.M., Jha, S., Kukula, J.H., Veith, H., Wang, D.: Using combinatorial optimization methods for quantification scheduling. In: Proc. 11th Conf. on Correct Hardware Design and Verification Methods, pp. 293\u2013309 (2001)","DOI":"10.1007\/3-540-44798-9_24"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Ramajaran, A.: Conjunctive query containment revisited. Technical report, Stanford University (November 1998)","DOI":"10.1007\/3-540-62222-5_36"},{"key":"26_CR11","series-title":"Lecture Notes in Computer Science","first-page":"311","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"V. Dalmau","year":"2002","unstructured":"Dalmau, V., Kolaitis, P.G., Vardi, M.Y.: Constraint satisfaction, bounded treewidth, and finite-variable logics. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, pp. 311\u2013326. Springer, Heidelberg (2002)"},{"key":"26_CR12","unstructured":"Dechter, R.: Mini-buckets: A general scheme for generating approximations in automated reasoning. In: International Joint Conference on Artificial Intelligence, pp. 1297\u20131303 (1997)"},{"issue":"1-2","key":"26_CR13","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0004-3702(99)00059-4","volume":"113","author":"R. Dechter","year":"1999","unstructured":"Dechter, R.: Bucket elimination: a unifying framework for reasoning. Artificial Intelligence\u00a0113(1-2), 41\u201385 (1999)","journal-title":"Artificial Intelligence"},{"key":"26_CR14","volume-title":"Constraint Processing","author":"R. Dechter","year":"2003","unstructured":"Dechter, R.: Constraint Processing. Morgan Kaufmann, San Francisco (2003)"},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0004-3702(87)90002-6","volume":"34","author":"R. Dechter","year":"1987","unstructured":"Dechter, R., Pearl, J.: Network-based heuristics for constraint-satisfaction problems. Artificial Intelligence\u00a034, 1\u201338 (1987)","journal-title":"Artificial Intelligence"},{"key":"26_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parametrized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parametrized Complexity. Springer, Heidelberg (1999)"},{"key":"26_CR17","unstructured":"Freuder, E.C.: Complexity of k-tree structured constraint satisfaction problems. In: Proc. AAAI 1990, pp. 4\u20139 (1990)"},{"key":"26_CR18","doi-asserted-by":"crossref","unstructured":"Freytag, J.C.: A rule-based view of query optimization. In: Proceedings of the 1987 ACM SIGMOD international conference on Management of data, pp. 173\u2013180 (1987)","DOI":"10.1145\/38714.38735"},{"key":"26_CR19","volume-title":"Database System Implementation","author":"H. Garcia-Molina","year":"2000","unstructured":"Garcia-Molina, H., Ullman, J.D., Widom, J.: Database System Implementation. Prentice-Hall, Englewood Cliffs (2000)"},{"key":"26_CR20","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Hypertree decompositions and tractable queries. In: Proc. 18th ACM Symp. on Principles of Database Systems, pp. 21\u201332 (1999)","DOI":"10.1145\/303976.303979"},{"key":"26_CR22","doi-asserted-by":"crossref","unstructured":"Griffiths, P.P., Astrahan, M.M., Chamberlin, D.D., Lorie, R.A., Price, T.G.: Access path selection in a relational database management system. In: ACM SIGMOD International Conference on Management of Data, pp. 23\u201334 (1979)","DOI":"10.1145\/582095.582099"},{"key":"26_CR23","doi-asserted-by":"crossref","unstructured":"Halevy, A.: Answering queries using views: A survey. VLDB Journal, 270\u2013294 (2001)","DOI":"10.1007\/s007780100054"},{"key":"26_CR24","doi-asserted-by":"crossref","unstructured":"Hojati, R., Krishnan, S.C., Brayton, R.K.: Early quantification and partitioned transition relations. In: Proc. 1996 Int\u2019l Conf. on Computer Design, pp. 12\u201319 (1996)","DOI":"10.1109\/ICCD.1996.563525"},{"key":"26_CR25","doi-asserted-by":"crossref","unstructured":"Ioannidis, Y., Wong, E.: Query optimization by simulated annealing. In: ACM SIGMOD International Conference on Management of Data, pp. 9\u201322 (1987)","DOI":"10.1145\/38714.38722"},{"key":"#cr-split#-26_CR26.1","doi-asserted-by":"crossref","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences, 302-332 (2000)","DOI":"10.1006\/jcss.2000.1713"},{"key":"#cr-split#-26_CR26.2","unstructured":"Earlier version in: Proc. 17th ACM Symp. on Principles of Database Systems (PODS 1998) (1998)"},{"key":"26_CR27","unstructured":"Kunen, I.K., Suciu, D.: A scalable algorithm for query minimization. Technical report, University of Washington (2002)"},{"key":"26_CR28","doi-asserted-by":"crossref","unstructured":"Ramakrishnan, R., Beeri, C., Krishnamurthi, R.: Optimizing existential datalog queries. In: Proceedings of the ACM Symposium on Principles of Database Systems, pp. 89\u2013102 (1988)","DOI":"10.1145\/308386.308420"},{"issue":"1\/2","key":"26_CR29","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1023\/A:1006303512524","volume":"24","author":"I. Rish","year":"2000","unstructured":"Rish, I., Dechter, R.: Resolution versus search: Two strategies for SAT. Journal of Automated Reasoning\u00a024(1\/2), 225\u2013275 (2000)","journal-title":"Journal of Automated Reasoning"},{"key":"26_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/3-540-45578-7_9","volume-title":"Principles and Practice of Constraint Programming - CP 2001","author":"A. San Miguel Aguirre","year":"2001","unstructured":"San Miguel Aguirre, A., Vardi, M.Y.: Random 3-SAT and BDDs \u2013 the plot thickens further. In: Walsh, T. (ed.) CP 2001. LNCS, vol.\u00a02239, pp. 121\u2013136. Springer, Heidelberg (2001)"},{"issue":"3","key":"26_CR31","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to tests chordality of graphs, tests acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. on Computing\u00a013(3), 566\u2013579 (1984)","journal-title":"SIAM J. on Computing"},{"key":"26_CR32","volume-title":"Database and Knowledge-Base Systems","author":"J.D. Ullman","year":"1989","unstructured":"Ullman, J.D.: Database and Knowledge-Base Systems, vol.\u00a0I and II. Computer Science Press, Rockville (1989)"},{"key":"26_CR33","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: On the complexity of bounded-variable queries. In: Proc. 14th ACM Symp. on Principles of Database Systems, pp. 266\u2013276 (1995)","DOI":"10.1145\/212433.212474"},{"issue":"3","key":"26_CR34","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1145\/320473.320479","volume":"1","author":"E. Wong","year":"1976","unstructured":"Wong, E., Youssefi, K.: Decomposition - a strategy for query processing. ACM Trans. on Database Systems\u00a01(3), 223\u2013241 (1976)","journal-title":"ACM Trans. on Database Systems"},{"key":"26_CR35","unstructured":"Yannakakis, M.: Algorithms for acyclic database schemes. In: Proc. 7 Int\u2019l Conf. on Very Large Data Bases, pp. 82\u201394 (1981)"},{"key":"26_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/3-540-49257-7_22","volume-title":"Database Theory - ICDT\u201999","author":"R. Yerneni","year":"1998","unstructured":"Yerneni, R., Li, C., Ullman, J.D., Garcia-Molina, H.: Optimizing large join queries in mediation systems. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol.\u00a01540, pp. 348\u2013364. Springer, Heidelberg (1998)"}],"container-title":["Lecture Notes in Computer Science","Advances in Database Technology - EDBT 2004"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24741-8_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T17:59:18Z","timestamp":1740333558000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24741-8_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540212003","9783540247418"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24741-8_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}