Anatomy of the Chase

• Autorzy: Grahne G. , Onet A.

Identyfikatory

DOI

10.3233/FI-2018-1627

• Języki publikacji: EN

Abstrakty

EN

A lot of research activity has recently taken place around the chase procedure, due to its usefulness in data integration, data exchange, query optimization, peer data exchange and data correspondence, to mention a few. As the chase has been investigated and further developed by a number of research groups and authors, many variants of the chase have emerged and associated results obtained. Due to the heterogeneous nature of the area it is frequently difficult to verify the scope of each result. In this paper we take closer look at recent developments, and provide additional results. Our analysis allows us create a taxonomy of the chase variations and the properties they satisfy. Two of the most central problems regarding the chase is termination, and discovery of restricted classes of sets of dependencies that guarantee termination of the chase. The search for the restricted classes has been motivated by a fairly recent result that shows that it is undecidable (RE-complete, to be more precise) to determine whether the chase with a given dependency set will terminate on a given instance. There is a small dissonance here, since the quest has been for classes of sets of dependencies guaranteeing termination of the chase on all instances, even though the latter problem was not known to be undecidable. We resolve the dissonance in this paper by showing that determining whether the chase with a given set of dependencies terminates on all instances is unsolvable, and on level Π⁰₂ in the Arithmetical Hierarchy. For this we use a reduction from word rewriting systems, thereby also showing the close connection between the chase and word rewriting. The same reduction also gives us the aforementioned instancedependent RE-completeness result as a byproduct. For one of the restricted classes guaranteeing termination on all instances, the stratified sets dependencies, we provide new complexity results for the problem of testing whether a given set of dependencies belongs to it. These results rectify some previous claims that have occurred in the literature.

Słowa kluczowe

EN

chase; data repair; date exchange; incomplete databases; undecidability complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 157, nr 3
• Strony: 221--270
• Opis fizyczny: Bibliogr. 33 poz., rys., tab.

Twórcy

autor

Grahne G.

• Concordia University, Montreal, Canada

autor

Onet A.

• Morgan Stanley, Montreal, Canada

Bibliografia

• [1] Beeri C, Vardi MY. The Implication Problem for Data Dependencies. In: ICALP. Volume 115 of Lecture Notes in Computer Science. 1981 pp. 73-85. URL https://doi.org/10.1007/3-540-10843-2_7.
• [2] Mendelzon AO. Database States and Their Tableaux. In: XP2 Workshop on Relational Database Theory. 1981. doi:DOI: 10.1145/329.318579.
• [3] Imielinski T, Jr WL. Incomplete Information in Relational Databases. J. ACM, 1984;31(4):761-791. doi:10.1145/1634.1886.
• [4] Aho AV, Beeri C, Ullman JD. The theory of joins in relational databases. ACM Trans. Database Syst., 1979;4(3):297-314. doi:http://doi.acm.org/10.1145/320083.320091.
• [5] Fagin R. Horn clauses and database dependencies. J. ACM, 1982;29(4):952-985. doi:10.1145/322344.322347.
• [6] Deutsch A, Nash A, Remmel JB. The chase revisited. In: PODS. 2008 pp. 149-158.
• [7] Calì A, Gottlob G, Kifer M. Taming the Infinite Chase: Query Answering under Expressive Relational Constraints. In: KR. 2008 pp. 70-80.
• [8] Marnette B. Generalized schema-mappings: from termination to tractability. In: PODS. 2009 pp. 13-22. doi:10.1145/1559795.1559799.
• [9] Grahne G, Onet A. Anatomy of the chase. CoRR, 2013;abs/1303.6682. URL http://arxiv.org/abs/1303.6682.
• [10] Gogacz T, Marcinkowski J. All-Instances Termination of Chase is Undecidable. In: Automata, Languages, and Programming-41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II. 2014 pp. 293-304. URL https://doi.org/10.1007/978-3-662-43951-7_25.
• [11] Hernich A, Kupke C, Lukasiewicz T, Gottlob G. Well-founded semantics for extended datalog and ontological reasoning. In: PODS. 2013 pp. 225-236. doi:10.1145/2463664.2465229.
• [12] Magka D, Krötzsch M, Horrocks I. Computing Stable Models for Nonmonotonic Existential Rules. In: IJCAI. 2013 pp. 1031-1038. ISBN:978-1-57735-633-2.
• [13] Gogacz T, Marcinkowski J. Termination of oblivious chase is undecidable [Technical Report], 2014.
• [14] Fagin R, Kolaitis PG, Miller RJ, Popa L. Data Exchange: Semantics and Query Answering. In: ICDT. 2003 pp. 207-224. URL https://doi.org/10.1007/3-540-36285-1_14.
• [15] Deutsch A, Tannen V. Reformulation of XML Queries and Constraints. In: ICDT. 2003 pp. 225-241.
• [16] Hernich A, Schweikardt N.CWA-solutions for data exchange settings with target dependencies. In: PODS. 2007 pp. 113-122. doi:10.1145/1265530.1265547.
• [17] Meier M, Schmidt M, Lausen G. On Chase Termination Beyond Stratification. PVLDB, 2009;2(1):970-981. doi:10.14778/1687627.1687737.
• [18] Spezzano F, Greco S. Chase Termination: A Constraints Rewriting Approach. PVLDB, 2010;3(1-2):93-104. doi:10.14778/1920841.1920858.
• [19] Grahne G, Onet A. On Conditional Chase Termination. In: AMW vol. 11, 2011.
• [20] Greco S, Spezzano F, Trubitsyna I. Stratification Criteria and Rewriting Techniques for Checking Chase Termination. PVLDB, 2011;4(11):1158-1168.
• [21] Abiteboul S, Hull R, Vianu V. Foundations of Databases. Addison-Wesley, 1995. ISBN: 0-201-53771-0.
• [22] Papadimitriou CH. Computational complexity. Addison-Wesley, 1994. ISBN: 978-0-201-53082-7.
• [23] Rogers H. Theory of recursive functions and effective computability (Reprint from 1967). MIT Press, 1987. ISBN: 978-0-262-68052-3. URL http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=3182.
• [24] Enderton HB. A mathematical introduction to logic. Academic Press, 1972. ISBN: 978-0-12-238450-9.
• [25] Onet A. The Chase Procedure and its Applications in Data Exchange. In: Kolaitis PG, Lenzerini M, Schweikardt N (eds.), Data Exchange, Integration, and Streams, volume 5 of Dagstuhl Follow-Ups, pp. 1-37. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. ISBN: 978-3-939897-61-3, 2013. doi:10.4230/DFU.Vol5.10452.1. URL http://dx.doi.org/10.4230/DFU.Vol5.10452.1.
• [26] Chandra AK, Merlin PM. Optimal Implementation of Conjunctive Queries in Relational Data Bases. In: STOC. 1977 pp. 77-90. doi:10.1145/800105.803397.
• [27] Rutenberg V. Complexity of generalized graph coloring. In: Proceedings of the 12th symposium on Mathematical foundations of computer science 1986. Springer-Verlag New York, Inc., New York, NY, USA. ISBN: 0387-16783-8, 1986 pp. 537-581. URL http://dl.acm.org/citation.cfm?id=22416.22478.
• [28] Stockmeyer LJ. The Polynomial-Time Hierarchy. Theor. Comput. Sci., 1976;3(1):1-22. URL https://doi.org/10.1016/0304-3975(76)90061-X.
• [29] Fagin R, Kolaitis PG, Popa L. Data exchange: getting to the core. In: PODS. 2003 pp. 90-101.
• [30] Gottlob G, Nash A. Data exchange: computing cores in polynomial time. In: PODS. 2006 pp. 40-49. doi:10.1145/1142351.1142358.
• [31] Hernich A. Computing universal models under guarded TGDs. In: ICDT. 2012 pp. 222-235. ISBN: 978-1-4503-0791-8. doi:10.1145/2274576.2274600.
• [32] Book RV, Otto F. String-rewriting systems. Texts and monographs in computer science. Springer, 1993. ISBN: 978-3-540-97965-4.
• [33] Meier M, Schmidt M, Lausen G. On Chase Termination Beyond Stratification [Technical Report and Erratum]. Website, 2009. URL http://arxiv.org/abs/0906.4228.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).