Abstract
The chase procedure for existential rules is an indispensable tool for several database applications, where its termination guarantees decidability of these tasks. Most previous studies have focused on the Skolem chase variant and its termination analysis. It is known that the restricted chase variant is more powerful in termination analysis provided a database is given. But all-instance termination presents a challenge since the critical database and similar techniques do not work. We develop a novel technique to characterize the activeness of all possible cycles of a certain length for restricted chase, which leads to the formulation of a parameterized class of finite restricted chase, called k-\(\mathsf {safe}(\varPhi )\). This approach is applicable to any class of finite Skolem chase identified with a condition of acyclicity. More generally, we show that the approach can be applied to the entire hierarchy of bounded rule sets previously only defined for Skolem chase. Experiments on a collection of ontologies from the web show the applicability of the proposed methods on real-world ontologies.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
By the coRE-completeness upper bound established by Grahne [12], there does not exist a faithful simulation of the termination behavior under restricted chase by using a fixed database.
- 2.
In the literature of unification, \(\theta =\{x/y,y/z\}\) would have been written as \(\{x/z,y/z\}\). Following [3] we keep the substitutes like x / y for technical reasons.
- 3.
These variables play a critical role in the construction of critical databases (cf. Definition 8).
- 4.
For example, \(\langle x, {i+\kappa } \rangle \) is distinct if \(i + \kappa \) is a fresh number.
- 5.
The set of all decision problems solvable in T(n) using a deterministic Turing machine.
- 6.
Due to the limitation of this transformation, our collection does not include ontologies with nominals, number restrictions or denial constraints.
- 7.
We did not manage to complete the test for the cases with \(k \ge 7\), due to limited resources. Thus, we are uncertain about whether more terminating ontologies may exist in this collection.
References
Baget, J.-F.: Improving the forward chaining algorithm for conceptual graphs rules. In: Proceedings KR 2004, pp. 407–414 (2004)
Baget, J.-F., Leclère, M., Mugnier, M.-L., Rocher, S., Sipieter, C.: Graal: a toolkit for query answering with existential rules. In: Bassiliades, N., Gottlob, G., Sadri, F., Paschke, A., Roman, D. (eds.) RuleML 2015. LNCS, vol. 9202, pp. 328–344. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21542-6_21
Baget, J.-F., Michel, M., Mugnier, M.-L., Salvat, E.: Extending decidable cases for rules with existential variables. In: Proceedings IJCAI 2009, pp. 677–682 (2009)
Baget, J.-F., Mugnier, M.-L.: Extensions of simple conceptual graphs: the complexity of rules and constraints. J. Artif. Intell. Res. 16, 425–465 (2002)
Beeri, C., Vardi, M.Y.: The implication problem for data dependencies. In: Even, S., Kariv, O. (eds.) ICALP 1981. LNCS, vol. 115, pp. 73–85. Springer, Heidelberg (1981). https://doi.org/10.1007/3-540-10843-2_7
Beeri, C., Vardi, M.Y.: A proof procedure for data dependencies. JACM 31(4), 718–741 (1984)
Calì, A., Gottlob, G., Lukasiewicz, T., Marnette, B., Pieris, A.: Datalog+/-: a family of logical knowledge representation and query languages for new applications. In: Proceedings LICS 2010, pp. 228–242 (2010)
Carral, D., Dragoste, I., Krötzsch, M.: Restricted chase (non) termination for existential rules with disjunctions. In: Proceedings IJCAI 2017, pp. 922–928 (2017)
Carral, D., Feier, C., Cuenca Grau, B., Hitzler, P., Horrocks, I.: \(\cal{EL}\)-ifying ontologies. In: Demri, S., Kapur, D., Weidenbach, C. (eds.) IJCAR 2014. LNCS (LNAI), vol. 8562, pp. 464–479. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08587-6_36
Grau, B.C., et al.: Acyclicity notions for existential rules and their application to query answering in ontologies. J. Artif. Intell. Res. 47, 741–808 (2013)
Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L.: Data exchange: semantics and query answering. Theor. Comput. Sci. 336(1), 89–124 (2005)
Grahne, G., Onet, A.: The data-exchange chase under the microscope. CoRR, abs/1407.2279 (2014)
Karimi, A., Zhang, H., You, J.-H.: A hierarchical approach to restricted chase termination for existential rules. Technical report, University of Alberta, Edmonton, AB, Canada (2018)
Krötzsch, M., Rudolph, S.: Extending decidable existential rules by joining acyclicity and guardedness. In: Proceedings AAAI 2011 (2011)
Marnette, B.: Generalized schema-map**s: from termination to tractability. In: Proceedings PODS 2009, pp. 13–22. ACM (2009)
Matentzoglu, N., Parsia, B.: The Manchester OWL Corpus (MOWLCorp), original serialisation, July 2014
Zhang, H., Zhang, Y., You, J.-H.: Existential rule languages with finite chase: complexity and expressiveness. In Proceedings AAAI 2015, pp. 1678–1684. AAAI Press (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Karimi, A., Zhang, H., You, JH. (2018). Restricted Chase Termination: A Hierarchical Approach and Experimentation. In: Benzmüller, C., Ricca, F., Parent, X., Roman, D. (eds) Rules and Reasoning. RuleML+RR 2018. Lecture Notes in Computer Science(), vol 11092. Springer, Cham. https://doi.org/10.1007/978-3-319-99906-7_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-99906-7_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-99905-0
Online ISBN: 978-3-319-99906-7
eBook Packages: Computer ScienceComputer Science (R0)