{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T16:21:27Z","timestamp":1764174087681},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,11]]},"abstract":"<jats:p>Supporting legacy applications when the database schema evolves represents a long-standing challenge of practical and theoretical importance. Recent work has produced algorithms and systems that automate the process of data migration and query adaptation; however, the problems of evolving integrity constraints and supporting legacy updates under schema and integrity constraints evolution are significantly more difficult and have thus far remained unsolved. In this paper, we address this issue by introducing a formal evolution model for the database schema structure and its integrity constraints, and use it to derive update mapping techniques akin to the rewriting techniques used for queries. Thus, we (i) propose a new set of Integrity Constraints Modification Operators (ICMOs), (ii) characterize the impact on integrity constraints of structural schema changes, (iii) devise representations that enable the rewriting of updates, and (iv) develop a unified approach for query and update rewriting under constraints. We then describe the implementation of these techniques provided by our PRISM++ system. The effectiveness of PRISM++ and its enabling technology has been verified on a testbed containing evolution histories of several scientific databases and web information systems, including the Genetic DB Ensembl (410+ schema versions in 9 years), and Wikipedia (240+ schema versions in 6 years).<\/jats:p>","DOI":"10.14778\/1921071.1921078","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"117-128","source":"Crossref","is-referenced-by-count":35,"title":["Update rewriting and integrity constraint maintenance in a schema evolution support system"],"prefix":"10.14778","volume":"4","author":[{"given":"Carlo A.","family":"Curino","sequence":"first","affiliation":[{"name":"MIT"}]},{"given":"Hyun Jin","family":"Moon","sequence":"additional","affiliation":[{"name":"NEC Labs America"}]},{"given":"Alin","family":"Deutsch","sequence":"additional","affiliation":[{"name":"UCSD"}]},{"given":"Carlo","family":"Zaniolo","sequence":"additional","affiliation":[{"name":"UCLA"}]}],"member":"320","published-online":{"date-parts":[[2010,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1145\/275487.275516","volume-title":"PODS","author":"Abiteboul S.","year":"1998","unstructured":"S. Abiteboul and O. M. Duschka . Complexity of answering queries using materialized views . In PODS , pages 254 -- 263 , 1998 . 10.1145\/275487.275516 S. Abiteboul and O. M. Duschka. Complexity of answering queries using materialized views. In PODS, pages 254--263, 1998. 10.1145\/275487.275516"},{"key":"e_1_2_1_2_1","volume-title":"Foundations of databases","author":"Abiteboul S.","year":"1995","unstructured":"S. Abiteboul , R. Hull , and V. Vianu . Foundations of databases . Addison Wesley , 1995 . S. Abiteboul, R. Hull, and V. Vianu. Foundations of databases. Addison Wesley, 1995."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/1514894.1514899","volume-title":"ICDT","author":"Afrati F. N.","year":"2009","unstructured":"F. N. Afrati and P. G. Kolaitis . Repair checking in inconsistent databases: algorithms and complexity . In ICDT , pages 31 -- 41 , 2009 . 10.1145\/1514894.1514899 F. N. Afrati and P. G. Kolaitis. Repair checking in inconsistent databases: algorithms and complexity. In ICDT, pages 31--41, 2009. 10.1145\/1514894.1514899"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1145\/303976.303983","volume-title":"PODS","author":"Arenas M.","year":"1999","unstructured":"M. Arenas , L. Bertossi , and J. Chomicki . Consistent query answers in inconsistent databases . In PODS , pages 68 -- 79 , 1999 . 10.1145\/303976.303983 M. Arenas, L. Bertossi, and J. Chomicki. Consistent query answers in inconsistent databases. In PODS, pages 68--79, 1999. 10.1145\/303976.303983"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/319628.319634"},{"key":"e_1_2_1_6_1","volume-title":"CIDR","author":"Bernstein P. A.","year":"2003","unstructured":"P. A. Bernstein . Applying model management to classical meta data problems . In CIDR , 2003 . P. A. Bernstein. Applying model management to classical meta data problems. In CIDR, 2003."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0059-9"},{"key":"e_1_2_1_8_1","first-page":"338","volume-title":"PODS","author":"Bohannon A.","year":"2006","unstructured":"A. Bohannon , B. C. Pierce , and J. A. Vaughan . Relational lenses: a language for updatable views . In PODS , pages 338 -- 347 , 2006 . 10.1145\/1142351.1142399 A. Bohannon, B. C. Pierce, and J. A. Vaughan. Relational lenses: a language for updatable views. In PODS, pages 338--347, 2006. 10.1145\/1142351.1142399"},{"key":"e_1_2_1_9_1","first-page":"409","volume-title":"GTTSE","author":"Cleve A.","year":"2006","unstructured":"A. Cleve and J.-L. Hainaut . Co-transformations in database applications evolution . In GTTSE , pages 409 -- 421 , 2006 . 10.1007\/11877028_17 A. Cleve and J.-L. Hainaut. Co-transformations in database applications evolution. In GTTSE, pages 409--421, 2006. 10.1007\/11877028_17"},{"key":"e_1_2_1_10_1","volume-title":"Pantha rei data set: http:\/\/data.schemaevolution.org\/","author":"Curino C.","year":"2009","unstructured":"C. Curino , M. Ham , F. Moroni , and C. Zaniolo . Pantha rei data set: http:\/\/data.schemaevolution.org\/ . 2009 . C. Curino, M. Ham, F. Moroni, and C. Zaniolo. Pantha rei data set: http:\/\/data.schemaevolution.org\/. 2009."},{"issue":"1","key":"e_1_2_1_11_1","first-page":"761","article-title":"Graceful database schema evolution: the prism workbench","volume":"1","author":"Curino C.","year":"2008","unstructured":"C. Curino , H. J. Moon , and C. Zaniolo . Graceful database schema evolution: the prism workbench . PVLDB , 1 ( 1 ): 761 -- 772 , 2008 . C. Curino, H. J. Moon, and C. Zaniolo. Graceful database schema evolution: the prism workbench. PVLDB, 1(1):761--772, 2008.","journal-title":"PVLDB"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/319732.319740"},{"key":"e_1_2_1_13_1","first-page":"149","volume-title":"PODS","author":"Deutsch A.","year":"2008","unstructured":"A. Deutsch , A. Nash , and J. Remmel . The chase revisited . In PODS , pages 149 -- 158 , 2008 . 10.1145\/1376916.1376938 A. Deutsch, A. Nash, and J. Remmel. The chase revisited. In PODS, pages 149--158, 2008. 10.1145\/1376916.1376938"},{"key":"e_1_2_1_14_1","first-page":"201","volume-title":"VLDB","author":"Deutsch A.","year":"2003","unstructured":"A. Deutsch and V. Tannen . Mars: A system for publishing xml from mixed and redundant storage . In VLDB , pages 201 -- 212 , 2003 . A. Deutsch and V. Tannen. Mars: A system for publishing xml from mixed and redundant storage. In VLDB, pages 201--212, 2003."},{"key":"e_1_2_1_15_1","volume-title":"Ensembl Genetic DB http:\/\/www.ensembl.org","author":"Ensembl","year":"2009","unstructured":"Ensembl development team. Ensembl Genetic DB http:\/\/www.ensembl.org , 2009 . {Online}. Ensembl development team. Ensembl Genetic DB http:\/\/www.ensembl.org, 2009. {Online}."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114249"},{"key":"e_1_2_1_17_1","first-page":"123","volume-title":"PODS","author":"Fagin R.","year":"2007","unstructured":"R. Fagin , P. G. Kolaitis , L. Popa , and W.-C. Tan . Quasi-inverses of schema mappings . In PODS , pages 123 -- 132 , 2007 . 10.1145\/1265530.1265548 R. Fagin, P. G. Kolaitis, L. Popa, and W.-C. Tan. Quasi-inverses of schema mappings. In PODS, pages 123--132, 2007. 10.1145\/1265530.1265548"},{"key":"e_1_2_1_18_1","first-page":"23","volume-title":"PODS","author":"Fagin R.","year":"2009","unstructured":"R. Fagin , P. G. Kolaitis , L. Popa , and W. C. Tan . Reverse data exchange: coping with nulls . In PODS , pages 23 -- 32 , 2009 . 10.1145\/1559795.1559800 R. Fagin, P. G. Kolaitis, L. Popa, and W. C. Tan. Reverse data exchange: coping with nulls. In PODS, pages 23--32, 2009. 10.1145\/1559795.1559800"},{"key":"e_1_2_1_19_1","volume-title":"SIGMOD, page 607","author":"Hern\u00e1ndez M. A.","year":"2001","unstructured":"M. A. Hern\u00e1ndez , R. J. Miller , and L. M. Haas . Clio: A semi-automatic tool for schema mapping . In SIGMOD, page 607 , 2001 . 10.1145\/375663.375767 M. A. Hern\u00e1ndez, R. J. Miller, and L. M. Haas. Clio: A semi-automatic tool for schema mapping. In SIGMOD, page 607, 2001. 10.1145\/375663.375767"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2005.10.003"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(85)90141-0","article-title":"Non-finite specifiability of projections of functional dependency families","volume":"39","author":"Hull R.","year":"1985","unstructured":"R. Hull . Non-finite specifiability of projections of functional dependency families . Theor. Comput. Sci. , 39 : 239 -- 265 , 1985 . R. Hull. Non-finite specifiability of projections of functional dependency families. Theor. Comput. Sci., 39:239--265, 1985.","journal-title":"Theor. Comput. Sci."},{"key":"e_1_2_1_22_1","volume-title":"ICDE, page 2","author":"Kotidis Y.","year":"2006","unstructured":"Y. Kotidis , D. Srivastava , and Y. Velegrakis . Updates through views: A new hope . In ICDE, page 2 , 2006 . 10.1109\/ICDE.2006.167 Y. Kotidis, D. Srivastava, and Y. Velegrakis. Updates through views: A new hope. In ICDE, page 2, 2006. 10.1109\/ICDE.2006.167"},{"key":"e_1_2_1_23_1","first-page":"233","volume-title":"PODS","author":"Lenzerini M.","year":"2002","unstructured":"M. Lenzerini . Data integration : A theoretical perspective . In PODS , pages 233 -- 246 , 2002 . 10.1145\/543613.543644 M. Lenzerini. Data integration: A theoretical perspective. In PODS, pages 233--246, 2002. 10.1145\/543613.543644"},{"key":"e_1_2_1_24_1","first-page":"308","volume-title":"I3E (2)","author":"Liu Y.","year":"2007","unstructured":"Y. Liu , S. ren Zhang, and M. qi Fang. Ecological analysis on evolution of information systems . In I3E (2) , pages 308 -- 315 , 2007 . Y. Liu, S. ren Zhang, and M. qi Fang. Ecological analysis on evolution of information systems. In I3E (2), pages 308--315, 2007."},{"key":"e_1_2_1_25_1","first-page":"572","volume-title":"VLDB","author":"Madhavan J.","year":"2003","unstructured":"J. Madhavan and A. Y. Halevy . Composing mappings among data sources . In VLDB , pages 572 -- 583 , 2003 . J. Madhavan and A. Y. Halevy. Composing mappings among data sources. In VLDB, pages 572--583, 2003."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1145\/872757.872782","volume-title":"SIGMOD","author":"Melnik S.","year":"2003","unstructured":"S. Melnik , E. Rahm , and P. A. Bernstein . Rondo: A programming platform for generic model management . In SIGMOD , pages 193 -- 204 , 2003 . 10.1145\/872757.872782 S. Melnik, E. Rahm, and P. A. Bernstein. Rondo: A programming platform for generic model management. In SIGMOD, pages 193--204, 2003. 10.1145\/872757.872782"},{"key":"e_1_2_1_27_1","first-page":"120","volume-title":"VLDB","author":"Miller R. J.","year":"1993","unstructured":"R. J. Miller , Y. E. Ioannidis , and R. Ramakrishnan . The use of information capacity in schema integration and translation . In VLDB , pages 120 -- 133 , 1993 . R. J. Miller, Y. E. Ioannidis, and R. Ramakrishnan. The use of information capacity in schema integration and translation. In VLDB, pages 120--133, 1993."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4379(94)90024-8"},{"issue":"1","key":"e_1_2_1_29_1","first-page":"882","article-title":"Managing and querying transaction-time databases under schema evolution","volume":"1","author":"Moon H. J.","year":"2008","unstructured":"H. J. Moon , C. Curino , A. Deutsch , C.-Y. Hou , and C. Zaniolo . Managing and querying transaction-time databases under schema evolution . PVLDB , 1 ( 1 ): 882 -- 895 , 2008 . H. J. Moon, C. Curino, A. Deutsch, C.-Y. Hou, and C. Zaniolo. Managing and querying transaction-time databases under schema evolution. PVLDB, 1(1):882--895, 2008.","journal-title":"PVLDB"},{"key":"e_1_2_1_30_1","first-page":"273","volume-title":"Intelligent Information Technology","author":"Ra Y.-G.","year":"2005","unstructured":"Y.-G. Ra . Relational schema evolution for program independency . Intelligent Information Technology , pages 273 -- 281 , 2005 . 10.1007\/978-3-540-30561-3_29 Y.-G. Ra. Relational schema evolution for program independency. Intelligent Information Technology, pages 273--281, 2005. 10.1007\/978-3-540-30561-3_29"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00219-4"},{"key":"e_1_2_1_32_1","first-page":"584","volume-title":"VLDB","author":"Velegrakis Y.","year":"2003","unstructured":"Y. Velegrakis , R. J. Miller , and L. Popa . Mapping adaptation under evolving schemas . In VLDB , pages 584 -- 595 , 2003 . Y. Velegrakis, R. J. Miller, and L. Popa. Mapping adaptation under evolving schemas. In VLDB, pages 584--595, 2003."},{"key":"e_1_2_1_33_1","first-page":"1006","volume-title":"VLDB","author":"Yu C.","year":"2005","unstructured":"C. Yu and L. Popa . Semantic adaptation of schema mappings when schemas evolve . In VLDB , pages 1006 -- 1017 , 2005 . C. Yu and L. Popa. Semantic adaptation of schema mappings when schemas evolve. In VLDB, pages 1006--1017, 2005."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1921071.1921078","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T14:41:49Z","timestamp":1689345709000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1921071.1921078"}},"subtitle":["PRISM++"],"short-title":[],"issued":{"date-parts":[[2010,11]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["10.14778\/1921071.1921078"],"URL":"https:\/\/doi.org\/10.14778\/1921071.1921078","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,11]]}}}