{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T23:44:41Z","timestamp":1762472681424,"version":"build-2065373602"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T00:00:00Z","timestamp":1737072000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T00:00:00Z","timestamp":1737072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004329","name":"Slovenian Research Agency","doi-asserted-by":"crossref","award":["P1-00383"],"award-info":[{"award-number":["P1-00383"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/20102-f2101143-fpr","name":"Federal State of Salzburg","doi-asserted-by":"publisher","id":[{"id":"10.13039\/20102-f2101143-fpr","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2025,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We propose a formal model of a knowledge graph (abbr. KG) that classifies the ground triples into sets that correspond to the triple types. The triple types are partially ordered by the sub-type relation. Consequently, the sets of ground triples that are the interpretations of triple types are partially ordered by the subsumption relation. The types of triple patterns restrict the sets of ground triples, which need to be addressed in the evaluation of triple patterns, to the interpretation of the types of triple patterns. Therefore, a\n                    <jats:italic>schema graph<\/jats:italic>\n                    of a KG should include all triple types that are likely to be determined as the types of triple patterns. The stored schema graph consists of the selected triple types that are stored in a KG and the complete schema graph includes all valid triple types of KG. We propose choosing the schema graph, which consists of the triple types from a strip around the stored schema graph, i.e., the triple types from the stored schema graph and some adjacent levels of triple types with respect to the sub-type relation. Given a selected schema graph, the statistics are updated for each ground triple\n                    <jats:italic>t<\/jats:italic>\n                    from a KG. First, we determine the set of triple types\n                    <jats:italic>stt<\/jats:italic>\n                    from the schema graph that are affected by adding a triple\n                    <jats:italic>t<\/jats:italic>\n                    to an RDF store. Finally, the statistics of triple types from the set\n                    <jats:italic>stt<\/jats:italic>\n                    are updated.\n                  <\/jats:p>","DOI":"10.1007\/s10472-024-09965-3","type":"journal-article","created":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T23:16:33Z","timestamp":1737069393000},"page":"787-815","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Type-based computation of knowledge graph statistics"],"prefix":"10.1007","volume":"93","author":[{"given":"Iztok","family":"Savnik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kiyoshi","family":"Nitta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Riste","family":"Skrekovski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikolaus","family":"Augsten","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,17]]},"reference":[{"issue":"1","key":"9965_CR1","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00778-009-0165-y","volume":"19","author":"T Neumann","year":"2010","unstructured":"Neumann, T., Weikum, G.: The rdf-3x engine for scalable management of rdf data. VLDB J. 19(1), 91\u2013113 (2010)","journal-title":"VLDB J."},{"key":"9965_CR2","doi-asserted-by":"crossref","unstructured":"Stocker, M., Seaborne, A., Bernstein, A., Kiefer, C., Reynolds, D.: Sparql basic graph pattern optimization using selectivity estimation. In: WWW 2008, Semantic Web II. WWW 08, pp. 595\u2013604. ACM, New York, NY, USA (2008)","DOI":"10.1145\/1367497.1367578"},{"key":"9965_CR3","doi-asserted-by":"publisher","unstructured":"Neumann, T., Moerkotte, G.: Characteristic sets: Accurate cardinality estimation for rdf queries with multiple joins. In: Proceedings of the 2011 IEEE 27th International Conference on Data Engineering. ICDE \u201911, pp. 984\u2013994. IEEE Computer Society, Washington, DC, USA (2011). https:\/\/doi.org\/10.1109\/ICDE.2011.5767868","DOI":"10.1109\/ICDE.2011.5767868"},{"key":"9965_CR4","doi-asserted-by":"publisher","unstructured":"Gubichev, A., Neumann, T.: Exploiting the query structure for efficient join ordering in SPARQL queries. In: Amer-Yahia, S., Christophides, V., Kementsietsidis, A., Garofalakis, M.N., Idreos, S., Leroy, V. (eds.) Proceedings of the 17th International Conference on Extending Database Technology, EDBT 2014, Athens, Greece, March 24-28, 2014, pp. 439\u2013450. OpenProceedings.org, Konstanz, Germany (2014). https:\/\/doi.org\/10.5441\/002\/EDBT.2014.40","DOI":"10.5441\/002\/EDBT.2014.40"},{"key":"9965_CR5","doi-asserted-by":"publisher","unstructured":"Savnik, I., Nitta, K.: In: Milutinovic, V., Kotlar, M. (eds.) Method of Big-Graph Partitioning Using a Skeleton Graph, pp. 3\u201339. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-13803-5_1","DOI":"10.1007\/978-3-030-13803-5_1"},{"key":"9965_CR6","unstructured":"OpenLink Software Documentation Team: OpenLink Virtuoso Universal Server: Documentation. (2009). OpenLink Software Documentation Team"},{"key":"9965_CR7","unstructured":"Wilkinson, K., Sayers, C., Kuno, H., Reynolds, D.: Efficient RDF Storage and Retrieval in Jena2"},{"key":"9965_CR8","doi-asserted-by":"publisher","unstructured":"Gurajada, S., Seufert, S., Miliaraki, I., Theobald, M.: Triad: A distributed shared-nothing rdf engine based on asynchronous message passing. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. SIGMOD \u201914, pp. 289\u2013300. ACM, New York, NY, USA (2014).https:\/\/doi.org\/10.1145\/2588555.2610511. http:\/\/doi.acm.org\/10.1145\/2588555.2610511","DOI":"10.1145\/2588555.2610511"},{"issue":"1","key":"9965_CR9","doi-asserted-by":"publisher","first-page":"1008","DOI":"10.14778\/1453856.1453965","volume":"1","author":"C Weiss","year":"2008","unstructured":"Weiss, C., Karras, P., Bernstein, A.: Hexastore: sextuple indexing for semantic web data management. Proc. VLDB Endow. 1(1), 1008\u20131019 (2008)","journal-title":"Proc. VLDB Endow."},{"issue":"4","key":"9965_CR10","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/s00778-013-0337-7","volume":"23","author":"L Zou","year":"2014","unstructured":"Zou, L., \u00d6zsu, M.T., Chen, L., Shen, X., Huang, R., Zhao, D.: gstore: A graph-based sparql query engine. VLDB J. 23(4), 565\u2013590 (2014). https:\/\/doi.org\/10.1007\/s00778-013-0337-7","journal-title":"VLDB J."},{"key":"9965_CR11","doi-asserted-by":"publisher","unstructured":"Harth, A., Decker, S.: Optimized index structures for querying rdf from the web. 2005, 71\u201380 (2005). https:\/\/doi.org\/10.1109\/LAWEB.2005.25","DOI":"10.1109\/LAWEB.2005.25"},{"key":"9965_CR12","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/978-3-540-76298-0_16","volume-title":"The Semantic Web","author":"A Harth","year":"2007","unstructured":"Harth, A., Umbrich, J., Hogan, A., Decker, S.: Yars2: A federated repository for querying graph structured data from the web. In: Aberer, K., Choi, K.-S., Noy, N., Allemang, D., Lee, K.-I., Nixon, L., Golbeck, J., Mika, P., Maynard, D., Mizoguchi, R., Schreiber, G., Cudr\u00e9-Mauroux, P. (eds.) The Semantic Web, pp. 211\u2013224. Springer, Berlin, Heidelberg (2007)"},{"key":"9965_CR13","unstructured":"Harris, S., Lamb, N., Shadbolt, N.: 4store: The design and implementation of a clustered rdf store. In: Proceedings of the The 5th International Workshop on Scalable Semantic Web Knowledge Base Systems (2009)"},{"key":"9965_CR14","doi-asserted-by":"publisher","unstructured":"Webber, J.: A programmatic introduction to neo4j. In: Proceedings of the 3rd Annual Conference on Systems, Programming, and Applications: Software for Humanity. SPLASH \u201912, pp. 217\u2013218. ACM, New York, NY, USA (2012). https:\/\/doi.org\/10.1145\/2384716.2384777","DOI":"10.1145\/2384716.2384777"},{"key":"9965_CR15","doi-asserted-by":"publisher","unstructured":"Harth, A., Hose, K., Schenkel, R.: Database techniques for linked data management. In: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. SIGMOD \u201912, pp. 597\u2013600. ACM, New York, NY, USA (2012). https:\/\/doi.org\/10.1145\/2213836.2213909. http:\/\/doi.acm.org\/10.1145\/2213836.2213909","DOI":"10.1145\/2213836.2213909"},{"key":"9965_CR16","doi-asserted-by":"publisher","unstructured":"Hogan, A., Blomqvist, E., Cochez, M., D\u2019amato, C., Melo, G.D., Gutierrez, C., Kirrane, S., Gayo, J.E.L., Navigli, R., Neumaier, S., Ngomo, A.-C.N., Polleres, A., Rashid, S.M., Rula, A., Schmelzeisen, L., Sequeda, J., Staab, S., Zimmermann, A.: Knowledge graphs. ACM Comput. Surv. 54(4) (2021). https:\/\/doi.org\/10.1145\/3447772","DOI":"10.1145\/3447772"},{"issue":"6","key":"9965_CR17","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1145\/362384.362685","volume":"13","author":"EF Codd","year":"1970","unstructured":"Codd, E.F.: A relational model of data for large shared data banks. Commun. ACM 13(6), 377\u2013387 (1970). https:\/\/doi.org\/10.1145\/362384.362685","journal-title":"Commun. ACM"},{"key":"9965_CR18","unstructured":"Resource Description Framework (RDF). http:\/\/www.w3.org\/RDF\/ (2014)"},{"key":"9965_CR19","unstructured":"RDF Schema 1.1. https:\/\/www.w3.org\/TR\/rdf-schema\/ (2014)"},{"key":"9965_CR20","unstructured":"Savnik, I., Nitta, K.: Datasets: Simple and Yago-S (2021)"},{"key":"9965_CR21","doi-asserted-by":"crossref","unstructured":"Savnik, I., Nitta, K.: Algebra of rdf graphs for querying large-scale distributed triple-store. In: Proc. of CD-ARES. Lecture Notes in Computer Science. Springer, Berlin (2016)","DOI":"10.1007\/978-3-319-45507-5_1"},{"key":"9965_CR22","unstructured":"Pierce, B.C.: Types and Programming Languages, 1st edn. MIT Press (2002)"},{"key":"9965_CR23","unstructured":"Savnik, I.: Type-checking knowledge graphs. University of Primorska, Technical Report (In preparation), FAMNIT (2024)"},{"key":"9965_CR24","doi-asserted-by":"crossref","unstructured":"WordNet: An electronic lexical database. Christiane Fellbaum (Ed.). Cambridge, MA: MIT Press, 1998. Pp. 423. Applied Psycholinguistics 22(01), 131\u2013134 (2001)","DOI":"10.1017\/S0142716401221079"},{"key":"9965_CR25","unstructured":"Pierce, B.C.: Programming With Intersection Types, Union Types, and Polymorphism (1991)"},{"key":"9965_CR26","unstructured":"Ramachandran, D., Reagan, P., Goolsbey, K.: First-orderized researchcyc: Expressivity and efficiency in a common-sense ontology. In: AAAI Reports. AAAI, Washington, DC, USA (2005)"},{"key":"9965_CR27","unstructured":"Savnik, I., Nitta, K.: epsilon: data and knowledge graph database system (2021)"},{"key":"9965_CR28","unstructured":"Oracle Corporation: Oracle Berkeley DB 11g Release 2. (2011). Oracle Corporation"},{"key":"9965_CR29","doi-asserted-by":"publisher","unstructured":"Hoffart, J., Suchanek, F.M., Berberich, K., Weikum, G.: Yago2: A spatially and temporally enhanced knowledge base from wikipedia. Artif. Intell. 194(0), 28\u201361 (2013). https:\/\/doi.org\/10.1016\/j.artint.2012.06.001. Artificial Intelligence, Wikipedia and Semi-Structured Resources","DOI":"10.1016\/j.artint.2012.06.001"},{"key":"9965_CR30","unstructured":"Knublauch, H., Kontokostas, D.: Shapes Constraint Language (SHACL). Accessed 07 Sept 2024. https:\/\/www.w3.org\/TR\/shacl\/"},{"key":"9965_CR31","unstructured":"Boneva, I., Gayo, J.E.L., Prud\u2019hommeaux, E.G., Staworko, S.: Shape Expressions Schemas. https:\/\/arxiv.org\/abs\/1510.05555"},{"key":"9965_CR32","doi-asserted-by":"publisher","unstructured":"Savnik, I., Nitta, K., Skrekovski, R., Augsten, N.: Statistics of RDF store for querying knowledge graphs. In: Varzinczak, I. (ed.) Foundations of Information and Knowledge Systems - 12th International Symposium, FoIKS 2022, Helsinki, Finland, June 20-23, 2022, Proceedings. Lecture Notes in Computer Science, vol. 13388, pp. 93\u2013110. Springer, Berlin, Germany (2022). https:\/\/doi.org\/10.1007\/978-3-031-11321-5_6","DOI":"10.1007\/978-3-031-11321-5_6"},{"key":"9965_CR33","doi-asserted-by":"crossref","unstructured":"Griffiths-Selinger, P., Astrahan, M.M., Chamberlin, D.D., Lorie, A., Price, T.G.: Access path selection in a relational database management system. In: Proceedings of SIGMOD \u201979. SIGMOD, pp. 23\u201334. ACM, New York, NY, USA (1979)","DOI":"10.1145\/582095.582099"},{"key":"9965_CR34","doi-asserted-by":"crossref","unstructured":"Christodoulakis, S.: Estimating block transfers and join sizes. In: Proceedings of SIGMOD \u201983. SIGMOD, pp. 40\u201354. ACM, New York, NY, USA (1983)","DOI":"10.1145\/582192.582204"},{"key":"9965_CR35","doi-asserted-by":"crossref","unstructured":"Piatetsky-Shapiro, G., Connell, C.: Accurate estimation of number of tuples satisfying condition. In: Proceedings of SIGMOD \u201984. SIGMOD, pp. 256\u2013276. ACM, New York, NY, USA (1984)","DOI":"10.1145\/602259.602294"},{"key":"9965_CR36","unstructured":"Harris, S., Gibbins, N.: 3store: Efficient bulk rdf storage. In: 1st International Workshop on Practical and Scalable Semantic Systems (PSSS\u201903), pp. 1\u201315 (2003). Event Dates: 2003-10-20. http:\/\/eprints.soton.ac.uk\/258231\/"},{"issue":"6","key":"9965_CR37","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1109\/MIC.2002.1067737","volume":"6","author":"B McBride","year":"2002","unstructured":"McBride, B.: Jena: A semantic web toolkit. IEEE Internet Comput. 6(6), 55\u201359 (2002). https:\/\/doi.org\/10.1109\/MIC.2002.1067737","journal-title":"IEEE Internet Comput."},{"issue":"11","key":"9965_CR38","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/219717.219745","volume":"38","author":"DB Lenat","year":"1995","unstructured":"Lenat, D.B.: Cyc: A large-scale investment in knowledge infrastructure. Commun. ACM 38(11), 33\u201338 (1995). https:\/\/doi.org\/10.1145\/219717.219745","journal-title":"Commun. ACM"},{"key":"9965_CR39","volume-title":"Knowledge representation and reasoning","author":"RJ Brachman","year":"2004","unstructured":"Brachman, R.J., Levesque, H.J.: Knowledge representation and reasoning. Elsevier, Amsterdam (2004)"},{"key":"9965_CR40","volume-title":"Description Logic Handbook","author":"F Baader","year":"2002","unstructured":"Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.: Description Logic Handbook. Cambridge University Press, England (2002)"},{"key":"9965_CR41","unstructured":"Erling, O.: Implementing a SPARQL Compliant RDF Triple Store Using a SQL-ORDBMS. OpenLink Software, (2009). OpenLink Software. http:\/\/virtuoso.openlinksw.com\/dataspace\/doc\/dav\/wiki\/Main\/VOSRDFWP\/"},{"issue":"1","key":"9965_CR42","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1999","unstructured":"Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359\u2013392 (1999)","journal-title":"SIAM J. Sci. Comput."},{"key":"9965_CR43","unstructured":"Wolff, B.G.J., Fletcher, G.H.L., Lu, J.J.: An extensible framework for query optimization on triplet-based RDF stores. In: Fischer, P.M., Alonso, G., Arenas, M., Geerts, F. (eds.) Proceedings of the Workshops of the EDBT\/ICDT 2015 Joint Conference (EDBT\/ICDT), Brussels, Belgium, March 27th, 2015. CEUR Workshop Proceedings, vol. 1330, pp. 190\u2013196. CEUR-WS.org (2015). https:\/\/ceur-ws.org\/Vol-1330\/paper-31.pdf"},{"key":"9965_CR44","doi-asserted-by":"publisher","unstructured":"Sagi, T., Lissandrini, M., Pedersen, T.B., Hose, K.: A Design Space for RDF Data Representations. https:\/\/doi.org\/10.1007\/s00778-021-00725-x","DOI":"10.1007\/s00778-021-00725-x"},{"key":"9965_CR45","doi-asserted-by":"publisher","unstructured":"Rabbani, K., Lissandrini, M., Hose, K.: Extraction of Validating Shapes from Very Large Knowledge Graphs. https:\/\/doi.org\/10.14778\/3579075.3579078","DOI":"10.14778\/3579075.3579078"},{"key":"9965_CR46","doi-asserted-by":"publisher","unstructured":"Hellings, J., Gyssens, M., Paredaens, J., Wu, Y.: Implication and axiomatization of functional constraints on patterns with an application to the RDF data model. https:\/\/doi.org\/10.1007\/978-3-319-04939-7_12","DOI":"10.1007\/978-3-319-04939-7_12"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-024-09965-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10472-024-09965-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-024-09965-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T23:41:56Z","timestamp":1762472516000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10472-024-09965-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,17]]},"references-count":46,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["9965"],"URL":"https:\/\/doi.org\/10.1007\/s10472-024-09965-3","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"type":"print","value":"1012-2443"},{"type":"electronic","value":"1573-7470"}],"subject":[],"published":{"date-parts":[[2025,1,17]]},"assertion":[{"value":"24 December 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}]}}