×
Calautti, Marco; Pieris, Andreas

Semi-oblivious chase termination: the sticky case. (English) Zbl 1477.68088

Theory Comput. Syst. 65, No. 1, 84-121 (2021).
The chase procedure is a fundamental algorithmic tool in database theory with a variety of applications. The authors consider a prominent paradigm that led to a robust Tuple-Generating Dependencies (TGD) based formalism, called stickiness. It is shown that for sticky sets of TGDs, all-instances chase termination is decidable if focus is on the (semi-) oblivious chase, and its exact complexity is discussed. The complexity results are obtained via a graph-based syntactic characterization of chase termination that is of independent interest.
Reviewer: T. C. Mohan (Chennai)

Cited in 2 Documents

MSC:

68P15 Database theory
68Q25 Analysis of algorithms and problem complexity

Keywords:

chase procedure; tuple-generating dependencies; stickiness; termination; computational complexity

Software:

RDFox
Cite Review PDF
Full Text: DOI
OA License

References:

[1] Abiteboul, S.; Hull, R.; Vianu, V., Foundations of Databases (1995), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0848.68031
[2] Aho, AV; Sagiv, Y.; Ullman, JD, Efficient optimization of a class of relational expressions, ACM Trans. Database Syst., 4, 4, 435-454 (1979) · doi:10.1145/320107.320112
[3] Baget, J., Mugnier, M., Rudolph, S., Thomazo, M.: Walking the Complexity Lines for Generalized Guarded Existential Rules. In: IJCAI, pp 712-717 (2011)
[4] Baget, JF; Leclère, M.; Mugnier, ML; Salvat, E., On rules with existential variables: walking the decidability line, Artif. Intell., 175, 9-10, 1620-1654 (2011) · Zbl 1225.68247 · doi:10.1016/j.artint.2011.03.002
[5] Beeri, C.; Vardi, MY, A proof procedure for data dependencies, J. ACM, 31, 4, 718-741 (1984) · Zbl 0632.68097 · doi:10.1145/1634.1636
[6] Benedikt, M., Konstantinidis, G., Mecca, G., Motik, B., Papotti, P., Santoro, D., Tsamoura, E.: Benchmarking the Chase. In: PODS, pp 37-52 (2017)
[7] Bourhis, P., Leclėre, M., Mugnier, M., Tison, S., Ulliana, F., Gallois, L.: Oblivious and Semi-Oblivious Boundedness for Existential Rules. In: IJCAI, pp 1581-1587 (2019)
[8] Calautti, M., Gottlob, G., Pieris, A.: Chase Termination for Guarded Existential Rules. In: PODS, pp 91-103 (2015)
[9] Calautti, M.; Greco, S.; Molinaro, C.; Trubitsyna, I., Exploiting equality generating dependencies in checking chase termination, PVLDB, 9, 5, 396-407 (2016)
[10] Calautti, M., Pieris, A.: Oblivious Chase Termination: The Sticky Case. In: ICDT, pp 17:1-17:18 (2019) · Zbl 07561477
[11] Calì, A.; Gottlob, G.; Kifer, M., Taming the infinite chase: query answering under expressive relational constraints, J. Artif. Intell. Res., 48, 115-174 (2013) · Zbl 1361.68221 · doi:10.1613/jair.3873
[12] Calì, A.; Gottlob, G.; Lukasiewicz, T., A general Datalog-based framework for tractable query answering over ontologies, J. Web Sem., 14, 57-83 (2012) · doi:10.1016/j.websem.2012.03.001
[13] Calì, A.; Gottlob, G.; Pieris, A., Towards more expressive ontology languages: the query answering problem, Artif. Intell., 193, 87-128 (2012) · Zbl 1270.68293 · doi:10.1016/j.artint.2012.08.002
[14] Cuenca Grau, B.; Horrocks, I.; Krȯtzsch, M.; Kupke, C.; Magka, D.; Motik, B.; Wang, Z., Acyclicity notions for existential rules and their application to query answering in ontologies, J. Artif. Intell. Res., 47, 741-808 (2013) · Zbl 1270.68295 · doi:10.1613/jair.3949
[15] Deutsch, A., Nash, A., Remmel, J.B.: The Chase Revisisted. In: PODS, pp 149-158 (2008)
[16] Deutsch, A., Tannen, V.: Reformulation of XML Queries and Constraints. In: ICDT, pp 225-241 (2003) · Zbl 1022.68507
[17] Fagin, R.; Kolaitis, PG; Miller, RJ; Popa, L., Data exchange: semantics and query answering, Theor. Comput. Sci., 336, 1, 89-124 (2005) · Zbl 1080.68019 · doi:10.1016/j.tcs.2004.10.033
[18] Gogacz, T., Marcinkowski, J.: All-Instances Termination of Chase is Undecidable. In: ICALP, pp 293-304 (2014) · Zbl 1409.68083
[19] Gogacz, T., Marcinkowski, J., Pieris, A.: All-Instances Restricted Chase Termination. In: PODS. To appear (2020) · Zbl 1409.68083
[20] Grahne, G.; Onet, A., Anatomy of the chase, Fundam. Inform., 157, 3, 221-270 (2018) · Zbl 1390.68247 · doi:10.3233/FI-2018-1627
[21] Greco, S.; Spezzano, F.; Trubitsyna, I., Stratification criteria and rewriting techniques for checking chase termination, PVLDB, 4, 11, 1158-1168 (2011)
[22] Krötzsch, M., Marx, M., Rudolph, S.: The Power of the Terminating Chase (Invited Talk). In: ICDT, pp 3:1-3:17 (2019) · Zbl 07561463
[23] Krötzsch, M., Rudolph, S.: Extending Decidable Existential Rules by Joining Acyclicity and Guardedness. In: IJCAI, pp 963-968 (2011)
[24] Leclère, M., Mugnier, M., Thomazo, M., Ulliana, F.: A Single Approach to Decide Chase Termination on Linear Existential Rules. In: ICDT, pp 18:1-18:19 (2019) · Zbl 07561478
[25] Leone, N., Manna, M., Terracina, G., Veltri, P.: Efficiently Computable Datalog∃ Programs. In: KR (2012)
[26] Leone, N.; Manna, M.; Terracina, G.; Veltri, P., Fast query answering over existential rules, ACM Trans. Comput. Log., 20, 2, 12:1-12:48 (2019) · Zbl 1433.68432 · doi:10.1145/3308448
[27] Maier, D.; Mendelzon, AO; Sagiv, Y., Testing implications of data dependencies, ACM Trans Database Syst., 4, 4, 455-469 (1979) · doi:10.1145/320107.320115
[28] Marnette, B.: Generalized Schema-Mappings: from Termination to Tractability. In: PODS, pp 13-22 (2009)
[29] Meier, M.; Schmidt, M.; Lausen, G., On chase termination beyond stratification, PVLDB, 2, 1, 970-981 (2009)
[30] Nenov, Y., Piro, R., Motik, B., Horrocks, I., Wu, Z., Banerjee, J.: Rdfox: a Highly-Scalable RDF Store. In: ISWC, pp 3-20 (2015)
[31] Papadimitriou, CH, Computational complexity (1994), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0833.68049
[32] Rudolph, S., Krötzsch, M., Hitzler, P.: All Elephants are Bigger than All Mice. In: DL (2008)
[33] Urbani, J., Krötzsch, M., Jacobs, C.J.H., Dragoste, I., Carral, D.: Efficient Model Construction for Horn Logic with Vlog - System Description. In: IJCAR, pp 680-688 (2018) · Zbl 1511.68110
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.