×

zbMATH — the first resource for mathematics

Why-provenance information for RDF, rules, and negation. (English) Zbl 1357.68210
Summary: The provenance (i.e., origins) of derived information on the Web is crucial in many applications to allow information quality assessment, trust judgments, accountability, as well as understanding the temporal and spatial status of the information. On the other hand, the inclusion of negative information in knowledge representation both in the form of negation-as-failure and explicit negation is also important to allow various forms of reasoning, provided that weakly negated information is associated with the sources (contexts) in which it holds. In this work, we consider collections of \(g\)-RDF ontologies, distributed over the web, along with a set of conflict statements expressing that information within a pair of \(g\)-RDF ontologies cannot be combined together for deriving new information. A \(g\)-RDF ontology is the combination of (i) a \(g\)-RDF graph \(G\) (i.e., a set of positive and strongly negated RDF triples, called \(g\)-RDF triples) and (ii) a \(g\)-RDF program \(P\) containing derivation rules with possibly both explicit and scoped weak negation. Information can be inferred through the \(g\)-RDF graphs or the derivation rules of the \(g\)-RDF ontologies, or through the RDFS derivation rules. We associate each derived grounded \(g\)-RDF triple \([\neg]p(s,o)\) with the set of names \(S\) of the \(g\)-RDF ontologies that contributed to its derivation. To achieve this, we define the provenance stable models of a \(g\)-RDF ontology collection. We show that our provenance \(g\)-RDF semantics faithfully extends RDFS semantics. Finally, we provide an algorithm based on Answer Set Programming that computes all provenance stable models of a \(g\)-RDF ontology collection and provides the answer to various kinds of queries. Various complexity results are provided.
MSC:
68T27 Logic in artificial intelligence
68T30 Knowledge representation
Software:
Smodels; SPARQL; TRIPLE; XSB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Amsterdamer, Y., Deutch, D., Tannen, V.: Provenance for aggregate queries. In: 13th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS-2011), pp. 153-164 (2011)
[2] Analyti, A., Antoniou, G., Damasio, C.V.: A formal theory for modular ERDF ontologies. In: 3rd International Conference Web Reasoning and Rule Systems (RR 2009), pp. 212-226 (2009) · Zbl 1271.68217
[3] Analyti, A., Antoniou, G., Damásio, C.V.: Computability and Complexity Issues of ERDF. Technical Report, FORTH-ICS, submitted for publication. Available at http://www.ics.forth.gr/analyti/Papers_2/ERDF_Complexity.pdf (2010)
[4] Analyti, A; Antoniou, G; Damásio, CV; Wagner, G, Negation and negative information in the w3c resource description framework, Ann. Math. Comput. Teleinformatics (AMCT), 1, 25-34, (2004)
[5] Analyti, A; Antoniou, G; Damásio, CV; Wagner, G, Extended RDF as a semantic foundation of rule markup languages, J. Artif. Intell. Res. (JAIR), 32, 37-94, (2008) · Zbl 1182.68157
[6] Belhajjame, K., Cheney, J., Corsar, D., Garijo, D., Soiland-Reyes, S., Zednik, S., Zhao, J.: PROV-O: the PROV ontology. In: Lebo, T., Sahoo, S., McGuinness, D. (eds.) W3C Working Draft. Consulted http://www.w3.org/TR/2012/WD-prov-o-20120724/ (2012) · Zbl 1192.68211
[7] Boley, H., Hallmark, G., Kifer, M., Paschke, A., Polleres, A., Reynolds, D.: RIF Core Dialect, 2nd edn. W3C Recommendation. Latest version available at http://www.w3.org/TR/rif-core/ (2013). Accessed 5 Feb 2013
[8] Brewka, G., Eiter, T.: Equilibria in heterogeneous nonmonotonic multi-context systems. In: 22nd AAAI Conference on Artificial Intelligence (AAAI-2007), pp. 385-390 (2007) · Zbl 1182.68157
[9] Buneman, P., Khanna, S., Tan, W.C.: Why and where: a characterization of data provenance. In: 8th International Conference on Database Theory (ICDT-2001), pp. 316-330 (2001) · Zbl 1047.68566
[10] Buneman, P., Kostylev, E.V.: Annotation algebras for RDFS. In: 2nd International Workshop on the Role of Semantic Web in Provenance Management (SWPM-2010), pp. 316-330 (2010)
[11] Carroll, J.J., Bizer, C., Hayes, P.J., Sticklerm, P.: Named graphs. J. Web Semant. 3(4) (2005) · Zbl 0885.68054
[12] Carroll, J.J., Bizer, C., Hayes, P.J., Stickler, P.: Named graphs, provenance and trust. In: 14th International Conference on World Wide Web (WWW-2005), pp. 613-622 (2005)
[13] Chen, W., Warren, D.S.: Tabled evaluation with delaying for general logic programs. J. ACM. 43(1) (1996) · Zbl 0882.68050
[14] Cheney, J; Chiticariu, L; Tan, WC, Provenance in databases: why, how, and where, Found. Trends Database, 1, 379-474, (2009)
[15] Ciccarese, P; Wu, E; Wong, G; Ocana, M; Kinoshita, J; Ruttenberg, A; Clark, T, The SWAN biomedical discourse ontology, J. Biomed. Inform., 41, 739-751, (2008)
[16] Cui, Y.: Lineage Tracing in Data Warehouses. Ph.D., Stanford InfoLab (2001)
[17] Damásio, C.V., Analyti, A., Antoniou, G.: Provenance for SPARQL queries. In: 11th International Semantic Web Conference (ISWC-2012). To appear (2012)
[18] Damásio, C.V., Analyti, A., Antoniou, G.: Justifications for logic programming. In: 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR-2013), pp. 530-542 (2013) · Zbl 1405.68053
[19] Dantsin, E; Eiter, T; Gottlob, G; Voronkov, A, Complexity and expressive power of logic programming, ACM Comput. Surv., 33, 374-425, (2001)
[20] de Bruijn, J., Franconi, E., Tessaris, S.: Logical reconstruction of normative RDF. In: OWL: Experiences and Directions Workshop (OWLED-2005). Ireland (2005)
[21] Decker, S., Sintek, M., Nejdl, W.: The Model-Theoretic Semantics of TRIPLE. Technical Report (2002) · Zbl 1048.68910
[22] Ding, L., Finin, T., Peng, Y., Joshi, A., da Silva, P.P., McGuinness, D.L.: Tracking RDF Graph Provenance using RDF Molecules. Technical Report, UMBC TR-CS-05-06 (2005) · Zbl 1207.68119
[23] Dividino, R.Q., Sizov, S., Staab, S., Schueler, B.: Querying for provenance, trust, uncertainty and other meta knowledge in RDF. J. Web Semant. 7(3) (2009)
[24] Dong, XL; Naumann, F, Data fusion - resolving data conflicts for integration, Proc. VLDB Endowment, 2, 1654-1655, (2009)
[25] Eiter, T., Faber,W., Fink, M.,Woltran, S.: Complexity results for answer set programming with bounded predicate arities and implications. Ann. Math. Artif. Intell. 51(2-4) (2007) · Zbl 1138.68017
[26] Flouris, G., Fundulaki, I., Pediaditis, P., Theoharis, Y., Christophides, V.: Coloring RDF triples to capture provenance. In: 8th International Semantic Web Conference (ISWC-2009), pp. 196-212 (2009)
[27] Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: Conflict-driven answer set solving. In: 20th International Joint Conference on Artificial Intelligence (IJCAI-2007), pp. 386-392 (2007) · Zbl 1149.68332
[28] Geerts, F., Karvounarakis, G., Christophides, V., Fundulaki, I.: Algebraic structures for capturing the provenance of SPARQL queries. In: 16th International Conference on Database Theory (ICDT-2013) (2013) · Zbl 1426.68079
[29] Geerts, F; Poggi, A, On database query languages for K-relations, J. Appl. Log., 8, 173-185, (2010) · Zbl 1192.68211
[30] Gelder, AV; Ross, KA; Schlipf, JS, The well-founded semantics for general logic programs, J. ACM, 38, 620-650, (1991) · Zbl 0799.68045
[31] Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: Kowalski, R., Bowen, K.A. (eds.) 5th International Conference on Logic Programming, pp. 1070-1080. MIT Press (1988)
[32] Gelfond, M., Lifschitz, V.: Logic programs with classical negation. In: 7th International Conference on Logic Programming, pp. 579-597 (1990) · Zbl 1367.68308
[33] Green, TJ; Ives, ZG; Tannen, V, Reconcilable differences, Theor. Comput. Syst., 49, 460-488, (2011) · Zbl 1235.68066
[34] Green, T.J., Karvounarakis, G., Tannen, V.: Provenance semirings. In: 26th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-2007), pp. 31-40 (2007)
[35] Guha, R.V., McCool, R., Fikes, R.: Contexts for the semantic web. In: 3rd International Semantic Web Conference (ISWC-2004), pp. 32-46 (2004)
[36] Hartig, O.: Provenance information in the web of data. In: WWW2008 Workshop on Linked Data on the Web (LDOW-2009) (2009)
[37] Hartig, O., Zhao, J.: Provenance Vocabulary Core Ontology Specification. Latest version available at http://trdf.sourceforge.net/provenance/ns.html (2012). Accessed 14 March 2012 · Zbl 0803.68016
[38] Hartig, O., Zhao, J.: Publishing and consuming provenance metadata on the web of linked data. In: 3rd International Provenance and Annotation Workshop (IPAW-2010), pp. 78-90 (2010)
[39] Hayes, P., Semantics, R.D.F.: W3C Recommendation. Available at http://www.w3.org/TR/2004/REC-rdf-mt-20040210/ (2004). Accessed 10 Feb 2004 · Zbl 0803.68016
[40] Heath, T., Bizer, C.: Linked Data: Evolving the Web into a Global Data Space. Morgan & Claypool (2011)
[41] Herre, H., Jaspars, J.,Wagner, G.: Partial logics with two kinds of negation as a foundation of knowledge-based reasoning. In: Gabbay, D.M., Wansing, H. (eds.) What is Negation? Kluwer Academic Publishers (1999) · Zbl 0982.03016
[42] Karvounarakis, G., Ives, Z.G., Tannen, V.: Querying data provenance. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD-2010), pp. 951-962 (2010)
[43] Kifer, M., Boley, H.: RIF Overview, 2nd edn. W3C Working Group Note 5. Latest version available at http://www.w3.org/TR/rif-overview/ (2013) · Zbl 0584.68022
[44] Kifer, M; Lausen, G; Wu, J, Logical foundations of object-oriented and frame-based languages, J. ACM, 42, 741-843, (1995) · Zbl 0885.68054
[45] Klyne, G., Carroll, J.J.: Resource Description Framework (RDF): Concepts and Abstract Syntax. W3C Recommendation. Available at http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/ (2004). Accessed 10 Feb 2004
[46] Leone, N; Pfeifer, G; Faber, W; Eiter, T; Gottlob, G; Perri, S; Scarcello, F, The DLV system for knowledge representation and reasoning, ACM Trans. Comput. Log., 7, 499-562, (2006) · Zbl 1367.68308
[47] Liu, L; Pontelli, E; Son, TC; Truszczynski, M, Logic programs with abstract constraint atoms: the role of computations, Artif. Intell., 174, 295-315, (2010) · Zbl 1207.68119
[48] Lloyd, J.W.: Foundations of Logic Programming, 2nd edn. Springer-Verlag (1987) · Zbl 0668.68004
[49] Lloyd, JW; Topor, RW, Making prolog more expressive, J. Log. Program., 1, 225-240, (1984) · Zbl 0584.68022
[50] MacGregor, R.M., Ko, I.-Y.: Representing contextualized data using semantic web tools. In: 1st International Workshop on Practical and Scalable Semantic Systems (PSSS-2003) (2003)
[51] Muñoz, S., Pe´rez, J., Gutie´rrez, C.: Minimal deductive systems for RDF. In: 4th European Semantic Web Conference (ESWC 2007), pp. 53-67 (2007)
[52] Niemela¨, I., Simons, P.: Smodels - an implementation of the stable model and well-founded semantics for normal LP. In: 4th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR-1997), pp. 421-430 (1997)
[53] Paschke, A., Morgenstern, L., Hirtle, D., Ginsberg, A., Patranjan, P.-L., McCabe, F.: RIF Use Cases and Requirements, 2nd edn. W3C Working Group Note. Latest version available at http://www.w3.org/TR/rif-ucr/ (2013)
[54] Polleres, A., Feier, C., Harth, A.: Rules with contextually scoped negation. In: 3rd European Semantic Web Conference (ESWC-2006), pp. 332-347 (2006)
[55] Prud’hommeaux, E., Seaborne, A.: SPARQL Query Language for RDF. W3C Recommendation. Available at http://www.w3.org/TR/rdf-sparql-query/ (2008). Accessed 15 Jan 2008
[56] Ram, S., Liu, J.: Understanding the semantics of data provenance to support active conceptual modeling. In: 1st International ACM-L Workshop on Active Conceptual Modeling of Learning (ACM-L-2006), pp. 17-29 (2006)
[57] Ross, KA, On negation in hilog, J. Log. Program., 18, 27-53, (1994) · Zbl 0803.68016
[58] Sagonas, K.F., Swift, T., Warren, D.S.: XSB as an efficient deductive database engine. In: Snodgrass, R.T., Winslett, M. (eds.) Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, pp. 442-453. ACM Press. Available at http://xsb.sourceforge.net/ (1994)
[59] Sintek, M., Decker, S.: TRIPLE - a query, inference, and transformation language for the semantic web. In: 1st International Semantic Web Conference (ISWC-2002), pp. 364-378. Springer-Verlag (2002) · Zbl 1048.68910
[60] Swift, T; Warren, DS, XSB: extending prolog with tabled logic programming, Theory Pract. Log. Program. (TPLP), 12, 157-187, (2012) · Zbl 1244.68021
[61] ter Horst, HJ, Completeness, decidability and complexity of entailment for rdf schema and a semantic extension involving the owl vocabulary, J. Web Semant., 3, 79-115, (2005)
[62] Yin, X., Han, J., Yu, P.S.: Truth discovery with multiple conflicting information providers on the web. In: 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2007), pp. 1048-1052 (2007)
[63] Zimmermann, A; Lopes, N; Polleres, A; Straccia, U, A general framework for representing, reasoning and querying with annotated semantic web data, J. Web Semant., 11, 72-95, (2012)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.