{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:52:52Z","timestamp":1775638372917,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,7,1]],"date-time":"2010-07-01T00:00:00Z","timestamp":1277942400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0705589"],"award-info":[{"award-number":["IIS-0705589"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2010,7]]},"abstract":"<jats:p>\n            We investigate the question of whether a query\n            <jats:italic>Q<\/jats:italic>\n            can be answered using a set\n            <jats:bold>V<\/jats:bold>\n            of views. We first define the problem in information-theoretic terms: we say that\n            <jats:bold>V<\/jats:bold>\n            determines\n            <jats:italic>Q<\/jats:italic>\n            if\n            <jats:bold>V<\/jats:bold>\n            provides enough information to uniquely determine the answer to\n            <jats:italic>Q<\/jats:italic>\n            . Next, we look at the problem of rewriting\n            <jats:italic>Q<\/jats:italic>\n            in terms of\n            <jats:bold>V<\/jats:bold>\n            using a specific language. Given a view language\n            <jats:italic>V<\/jats:italic>\n            and query language\n            <jats:italic>Q<\/jats:italic>\n            , we say that a rewriting language\n            <jats:italic>R<\/jats:italic>\n            is complete for\n            <jats:italic>V<\/jats:italic>\n            -to-\n            <jats:italic>Q<\/jats:italic>\n            rewritings if every\n            <jats:italic>Q<\/jats:italic>\n            \u2208\n            <jats:italic>Q<\/jats:italic>\n            can be rewritten in terms of\n            <jats:bold>V<\/jats:bold>\n            \u2208\n            <jats:italic>V<\/jats:italic>\n            using a query in\n            <jats:italic>R<\/jats:italic>\n            , whenever\n            <jats:bold>V<\/jats:bold>\n            determines\n            <jats:italic>Q<\/jats:italic>\n            . While query rewriting using views has been extensively investigated for some specific languages, the connection to the information-theoretic notion of determinacy, and the question of completeness of a rewriting language have received little attention. In this article we investigate systematically the notion of determinacy and its connection to rewriting. The results concern decidability of determinacy for various view and query languages, as well as the power required of complete rewriting languages. We consider languages ranging from first-order to conjunctive queries.\n          <\/jats:p>","DOI":"10.1145\/1806907.1806913","type":"journal-article","created":{"date-parts":[[2010,8,2]],"date-time":"2010-08-02T13:15:22Z","timestamp":1280754922000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":75,"title":["Views and queries"],"prefix":"10.1145","volume":"35","author":[{"given":"Alan","family":"Nash","sequence":"first","affiliation":[{"name":"Aleph One LLC"}]},{"given":"Luc","family":"Segoufin","sequence":"additional","affiliation":[{"name":"INRIA, ENS-Cachan, CACHAN Cedex, France"}]},{"given":"Victor","family":"Vianu","sequence":"additional","affiliation":[{"name":"University of California San Diego, La Jolla, CA"}]}],"member":"320","published-online":{"date-parts":[[2010,7,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275516"},{"key":"e_1_2_1_2_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_3_1","volume-title":"Mathematical Foundations of Computer Science","author":"Afrati F.","unstructured":"Afrati , F. 2007. Rewriting conjunctive queries determined by views . In Mathematical Foundations of Computer Science . Springer , Berlin , 78--89. Afrati, F. 2007. Rewriting conjunctive queries determined by views. In Mathematical Foundations of Computer Science. Springer, Berlin, 78--89."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 26th International Conference on Very Large Databases (VLDB'00)","author":"Agrawal S.","unstructured":"Agrawal , S. , Chaudhuri , S. , and Narasayya , V. R . 2000. Automated sselection of materialized views and indexes in sql databases . In Proceedings of the 26th International Conference on Very Large Databases (VLDB'00) . Morgan Kaufmann Publishers, San Fransisco, CA, 496--505. Agrawal, S., Chaudhuri, S., and Narasayya, V. R. 2000. Automated sselection of materialized views and indexes in sql databases. In Proceedings of the 26th International Conference on Very Large Databases (VLDB'00). Morgan Kaufmann Publishers, San Fransisco, CA, 496--505."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/319628.319634"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1385-7258(53)50042-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Borger E. Gradel E. and Gurevich Y. 1997. The Classical Decision Problem. Springer.  Borger E. Gradel E. and Gurevich Y. 1997. The Classical Decision Problem. Springer.","DOI":"10.1007\/978-3-642-59207-2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303996"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335207"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543646"},{"key":"e_1_2_1_11_1","unstructured":"Chang C. and Keisler H. 1977. Model Theory. North-Holland.  Chang C. and Keisler H. 1977. Model Theory. North-Holland."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the International Conference on Database Theory. Springer, 56--70","author":"Chekuri C.","unstructured":"Chekuri , C. and Rajaraman , A . 1997. Conjunctive query containment revisited . In Proceedings of the International Conference on Database Theory. Springer, 56--70 . Chekuri, C. and Rajaraman, A. 1997. Conjunctive query containment revisited. In Proceedings of the International Conference on Database Theory. Springer, 56--70."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.2307\/2963594"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'96)","author":"Dar S.","unstructured":"Dar , S. , Franklin , M. J. , J\u00f3nsson , B. T. , Srivastava , D. , and Tan , M . 1996. Semantic data caching and replacement . In Proceedings of the International Conference on Very Large Databases (VLDB'96) . 330--341. Dar, S., Franklin, M. J., J\u00f3nsson, B. T., Srivastava, D., and Tan, M. 1996. Semantic data caching and replacement. In Proceedings of the International Conference on Very Large Databases (VLDB'96). 330--341."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 25th International Conference on Very Large Databases (VLDB'99)","author":"Deutsch A.","unstructured":"Deutsch , A. , Popa , L. , and Tannen , V . 1999. Physical data independence, constraints, and optimization with universal plans . In Proceedings of the 25th International Conference on Very Large Databases (VLDB'99) . Morgan Kaufmann Publishers, San Fransisco, CA, 459--470. Deutsch, A., Popa, L., and Tannen, V. 1999. Physical data independence, constraints, and optimization with universal plans. In Proceedings of the 25th International Conference on Very Large Databases (VLDB'99). Morgan Kaufmann Publishers, San Fransisco, CA, 459--470."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/263661.263674"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Ebbinghaus H.-D. and Flum J. 1995. Finite Model Theory. Springer.  Ebbinghaus H.-D. and Flum J. 1995. Finite Model Theory. Springer.","DOI":"10.1007\/3-540-28788-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00030-8"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Grumbach S. Lacroix Z. and Lindell S. 1995. Generalized implicit definitions on finite structures. In Selected Papers from the 9th International Workshop on Computer Science Logic (CSL'95). Springer 252--265.   Grumbach S. Lacroix Z. and Lindell S. 1995. Generalized implicit definitions on finite structures. In Selected Papers from the 9th International Workshop on Computer Science Logic (CSL'95). Springer 252--265.","DOI":"10.1007\/3-540-61377-3_42"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303994"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00033-8"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/2586808"},{"key":"e_1_2_1_23_1","first-page":"25","article-title":"The word problem for some classes of semigroups","volume":"5","author":"Gurevich Y.","year":"1966","unstructured":"Gurevich , Y. 1966 . The word problem for some classes of semigroups . Algebra Logic 5 , 4, 25 -- 35 . In Russian. Gurevich, Y. 1966. The word problem for some classes of semigroups. Algebra Logic 5, 4, 25--35. In Russian.","journal-title":"Algebra Logic"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10849-005-5789-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220198"},{"key":"e_1_2_1_26_1","series-title":"An Eatcs Series","volume-title":"Elements of Finite Model Theory. Texts in Theoretical Computer Science","author":"Libkin L.","unstructured":"Libkin , L. 2004. Elements of Finite Model Theory. Texts in Theoretical Computer Science . An Eatcs Series . Springer . Libkin, L. 2004. Elements of Finite Model Theory. Texts in Theoretical Computer Science. An Eatcs Series. Springer."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265534"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_5"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.2307\/420966"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220199"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065174"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00172286"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/645502.656100"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 23rdInternational Conference on Very Large Databases (VLDB'97)","author":"Vassalos V.","unstructured":"Vassalos , V. and Papakonstantinou , Y . 1997. Describing and using query capabilities of heterogeneous sources . In Proceedings of the 23rdInternational Conference on Very Large Databases (VLDB'97) . Morgan Kaufmann Publishers, San Fransisco, CA, 256--265. Vassalos, V. and Papakonstantinou, Y. 1997. Describing and using query capabilities of heterogeneous sources. In Proceedings of the 23rdInternational Conference on Very Large Databases (VLDB'97). Morgan Kaufmann Publishers, San Fransisco, CA, 256--265."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 13th International Conference on Very Large Databases (VLDB'87)","author":"Yang H. Z.","unstructured":"Yang , H. Z. and Larson , P . -A. 1987. Query transformation for psj-queries . In Proceedings of the 13th International Conference on Very Large Databases (VLDB'87) . Morgan Kaufmann Publishers, San Fransisco, CA, 245--254. Yang, H. Z. and Larson, P.-A. 1987. Query transformation for psj-queries. In Proceedings of the 13th International Conference on Very Large Databases (VLDB'87). Morgan Kaufmann Publishers, San Fransisco, CA, 245--254."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806907.1806913","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1806907.1806913","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:37Z","timestamp":1750246777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806907.1806913"}},"subtitle":["Determinacy and rewriting"],"short-title":[],"issued":{"date-parts":[[2010,7]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["10.1145\/1806907.1806913"],"URL":"https:\/\/doi.org\/10.1145\/1806907.1806913","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7]]},"assertion":[{"value":"2009-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}