Abstract
In this paper we focus on the problem of how lineage for existential rules knowledge bases. Given a knowledge base and an atomic ground query, we want to output all minimal provenance paths of the query (i.e. the sequence of rule applications that generates an atom from a given set of facts). Obtaining all minimal provenance paths of a query using forward chaining can be challenging due to the simplifications done during the rule applications of different chase mechanisms. We build upon the notion of Graph of Atoms Dependency (GAD) and use it to solve the problem of provenance path loss in the context of forward chaining with existential rules. We study the properties of this structure and investigate how different chase mechanisms impact its construction.
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
References
Arora, T., Ramakrishnan, R., Roth, W.G., Seshadri, P., Srivastava, D.: Explaining program execution in deductive systems. In: Ceri, S., Tanaka, K., Tsur, S. (eds.) DOOD 1993. LNCS, vol. 760, pp. 101–119. Springer, Heidelberg (1993). doi:10.1007/3-540-57530-8_7
Baget, J.-F., Garreau, F., Mugnier, M.-L., Rocher, S.: Extending acyclicity notions for existential rules. In: ECAI, pp. 39–44 (2014)
Buneman, P., Chapman, A., Cheney, J.: Provenance management in curated databases. In: Proceedings of the 2006 ACM SIGMOD international conference on Management of data, pp. 539–550. ACM (2006)
Caballero, R., García-Ruiz, Y., Sáenz-Pérez, F.: A theoretical framework for the declarative debugging of datalog programs. In: Schewe, K.-D., Thalheim, B. (eds.) SDKB 2008. LNCS, vol. 4925, pp. 143–159. Springer, Heidelberg (2008). doi:10.1007/978-3-540-88594-8_8
Calı, A., Gottlob, G., Kifer, M.: Taming the infinite chase: query answering under expressive relational constraints. In: Proceeding of KR, pp. 70–80 (2008)
Calì, A., Gottlob, G., Lukasiewicz, T.: A general datalog-based framework for tractable query answering over ontologies. Web Semant. Sci. Serv. Agents World Wide Web 14, 57–83 (2012)
Ceri, S., Gottlob, G., Tanca, L.: What you always wanted to know about datalog (and never dared to ask). IEEE Trans. Knowl. Data Eng. 1(1), 146–166 (1989)
Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L.: Data exchange: semantics and query answering. Theoret. Comput. Sci. 336(1), 89–124 (2005)
Frawley, W.J., Piatetsky-Shapiro, G., Matheus, C.J.: Knowledge discovery in databases: an overview. AI Mag. 13(3), 57 (1992)
Gallo, G., Longo, G., Pallottino, S., Nguyen, S.: Directed hypergraphs and applications. Discrete Appl. Math. 42(2), 177–201 (1993)
Hecham, A., Croitoru, M., Bisquert, P.: Argumentation-based defeasible reasoning for existential rules. In: Proceedings of AAMAS 2017 (2017, to appear)
Ikeda, R., Widom, J.: Data Lineage: A Survey (2009)
Kakas, A.C., Kowalski, R.A., Toni, F.: The role of abduction in logic programming. Handb. Logic Artif. Intell. Logic Program. 5, 235–324 (1998)
Marnette, B.: Generalized schema-mappings: from termination to tractability. In: Proceedings of the Twenty-Eighth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 13–22. ACM (2009)
Nguyen, S., Pallottino, S.: Hyperpaths and shortest hyperpaths. In: Simeone, B. (ed.) Combinatorial Optimization. LNM, vol. 1403, pp. 258–271. Springer, Heidelberg (1989). doi:10.1007/BFb0083470
Ré, C., Suciu, D.: Approximate lineage for probabilistic databases. Proc. VLDB Endowment 1(1), 797–808 (2008)
Widom, J.: Trio: a system for data, uncertainty, and lineage. In: Aggarwa, C.C. (ed.) Managing and Mining Uncertain Data, vol. 35, pp. 1–35. Springer, New York (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Hecham, A., Bisquert, P., Croitoru, M. (2017). On the Chase for All Provenance Paths with Existential Rules. In: Costantini, S., Franconi, E., Van Woensel, W., Kontchakov, R., Sadri, F., Roman, D. (eds) Rules and Reasoning. RuleML+RR 2017. Lecture Notes in Computer Science(), vol 10364. Springer, Cham. https://doi.org/10.1007/978-3-319-61252-2_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-61252-2_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-61251-5
Online ISBN: 978-3-319-61252-2
eBook Packages: Computer ScienceComputer Science (R0)