S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases, 1995.

G. Aluç, O. Hartig, M. T. Özsu, and K. Daudjee, Diversified stress testing of RDF data management systems, ISWC, pp.197-212, 2014.

C. Bizer and A. Schultz, The Berlin SPARQL Benchmark, Int. J. Semantic Web Inf. Syst, vol.5, issue.2, 2009.

P. Bohannon, J. Freire, P. Roy, and J. Siméon, From XML schema to relations: A cost-based approach to XML storage, 2002.

S. Campinas, R. Delbru, and G. Tummarello, Efficiency and precision trade-offs in graph summary algorithms, p.IDEAS, 2013.

?. ?ebiri?, F. Goasdoué, P. Guzewicz, and I. Manolescu, Compact Summaries of Rich Heterogeneous Graphs, INRIA and U. Rennes, vol.1, 2018.

S. Cebiric, F. Goasdoué, H. Kondylakis, D. Kotzinos, I. Manolescu et al., Summarizing Semantic Graphs: A Survey, The VLDB Journal, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01925496

?. ?ebiri?, F. Goasdoué, and I. Manolescu, A framework for efficient representative summarization of RDF graphs, ISWC (poster, 2017.

C. Chen, C. X. Lin, M. Fredrikson, M. Christodorescu, X. Yan et al., Mining graph patterns efficiently via randomized summaries, PVLDB, vol.2, issue.1, 2009.

Q. Chen, A. Lim, and K. W. Ong, D(K)-index: An adaptive structural summary for graph-structured data, 2003.

M. P. Consens, R. J. Miller, F. Rizzolo, and A. A. Vaisman, Exploring XML web collections with DescribeX. TWEB, vol.4, issue.3, 2010.

A. Deutsch, M. F. Fernández, and D. Suciu, Storing semistructured data with STORED, 1999.

W. Fan, J. Li, X. Wang, and Y. Wu, Query preserving graph compression, 2012.

Z. Galil and G. F. Italiano, Data structures and algorithms for disjoint set union problems, ACM Comput. Surv, vol.23, issue.3, pp.319-344, 1991.

F. Goasdoué, P. Guzewicz, and I. Manolescu, Incremental structural summarization of RDF graphs, EDBT, 2019.

F. Goasdoué, I. Manolescu, and A. Roati?, Efficient query answering against dynamic RDF databases, 2013.

R. Goldman and J. Widom, Dataguides: Enabling query formulation and optimization in semistructured databases, 1997.

A. Gubichev and T. Neumann, Exploiting the query structure for efficient join ordering in SPARQL queries, EDBT, pp.439-450, 2014.

Y. Guo, Z. Pan, and J. Heflin, LUBM: A benchmark for OWL knowledge base systems, J. Web Sem, vol.3, issue.2-3, 2005.

S. Gurajada, S. Seufert, I. Miliaraki, and M. Theobald, Using graph summarization for join-ahead pruning in a distributed RDF engine, SWIM Workshop, 2014.

M. R. Henzinger, T. A. Henzinger, and P. W. Kopke, Computing simulations on finite and infinite graphs, 1995.

R. Kaushik, P. Bohannon, J. F. Naughton, and H. F. Korth, Covering indexes for branching path queries, 2002.

R. Kaushik, P. Shenoy, P. Bohannon, and E. Gudes, Exploiting local similarity for indexing paths in graphstructured data, 2002.

K. Khan, W. Nawaz, and Y. Lee, Set-based approximate approach for lossless graph summarization, Computing, vol.97, issue.12, pp.1185-1207, 2015.

S. Khatchadourian and M. P. Consens, ExpLOD: Summary-based exploration of interlinking and RDF usage in the linked open data cloud, 2010.

S. Khatchadourian and M. P. Consens, Constructing bisimulation summaries on a multi-core graph processing framework, GRADES Workshop, 2015.

W. Le, F. Li, A. Kementsietsidis, and S. Duan, Scalable keyword search on large RDF data, IEEE TKDE, vol.26, issue.11, 2014.

K. Lefevre and E. Terzi, GraSS: Graph structure summarization, SDM, 2010.

Y. Liu, T. Safavi, A. Dighe, and D. Koutra, Graph summarization methods and applications: A survey, ACM Comput. Surv, vol.51, issue.3, 2018.

T. Milo and D. Suciu, Index structures for path expressions, 1999.

S. Navlakha, R. Rastogi, and N. Shrivastava, Graph summarization with bounded error, 2008.

T. Neumann and G. Moerkotte, Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins, 2011.

R. A. Principe, B. Spahiu, M. Palmonari, A. Rula, F. D. Paoli et al., ABSTAT 1.0: Compute, manage and share semantic profiles of RDF knowledge graphs, 2018.

M. Rudolf, M. Paradies, C. Bornhövd, and W. Lehner, SynopSys: large graph analytics in the SAP HANA database through summarization, 2013.

A. Schätzle, A. Neu, G. Lausen, and M. Przyjaciel-zablocki, Large-scale bisimulation of RDF graphs, SWIM Workshop, 2013.

Y. Tian, R. A. Hankins, and J. M. Patel, Efficient aggregation for graph summarization, 2008.

T. Tran, G. Ladwig, and S. Rudolph, Managing structured and semistructured RDF data using structure indexes, IEEE TKDE, vol.25, issue.9, 2013.

, W3C: Resource description framework

P. Zhao, J. X. Yu, and P. S. Yu, Graph indexing: Tree + delta >= graph, 2007.

M. Zneika, D. Vodislav, and D. Kotzinos, Quality metrics for RDF graph summarization, Semantic Web, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01773457

, ? , by definition of an RDF summary, there ex-2 = f (n 1 ) p f (n 2 ). Moreover, since n 1 p n 2 is in G ? , f 1 (n 1 ) p f 1 (n 2 ) is in (G ? ) /? . Therefore, since for every f, vol.2, p.1

. Similarly, ? such that n 1 type c = f 1 (n 1 ) type c. Further, if n 1 type c is in G ? , then f (n 1 ) type c is in (G /? ) ? (Theorem 1), hence f 2 (f (n 1 )) type c is in ((G /? ) ? ) /? . Therefore, ? since for every f 1 (n 1 ) type c edge in (G ? ) /? , there is an edge f 2 (f (n 1 )) type c in ((G /? ) ? ) /? , and ? since ?(f 1 (n)) = f 2 (f (n)), for n any G ? node, is a bijective function from all (G ? ) /? nodes to all, G ? ) /? , by definition of an RDF summary

, ? , by definition of an RDF summary, there exists an in (G ? ) /? . Therefore, since for every f 2 (f (n 1 )) type c edge in ((G /? ) ? ) /? , there is an edge f 1 (n 1 ) type c in (G ? ) /? , and since ?(f 1 (n)) = f 2 (f (n)), for n any G ? node, is a bijective function from all (G ? ) /? nodes to all, ? n 1 type c triples through ? ?1 (**'). From (*) and (**), and, (*') and (**')