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

C. Bizer and A. Schultz, The Berlin SPARQL Benchmark, Int. J. Semantic Web Inf. Syst, vol.5, issue.2, pp.1-24, 2009.
DOI : 10.4018/978-1-60960-593-3.ch004

, Inria

S. Campinas, R. Delbru, and G. Tummarello, Efficiency and precision trade-offs in graph summary algorithms, Proceedings of the 17th International Database Engineering & Applications Symposium on, IDEAS '13, 2013.
DOI : 10.1145/2513591.2513654

F. Cebiri´ccebiri´c, I. Goasdoué, ?. Manolescu, F. Cebiri´ccebiri´c, I. Goasdoué et al., Query-oriented summarization of RDF graphs Query-oriented summarization of RDF graphs (demonstration ), BICOD, 2015. [5] 2015. [6] ?. ? Cebiri´cCebiri´c, 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, Proceedings of the VLDB Endowment, vol.2, issue.1, 2009.
DOI : 10.14778/1687627.1687711

C. Chen, X. Yan, F. Zhu, J. Han, and P. S. Yu, Graph OLAP: Towards Online Analytical Processing on Graphs, 2008 Eighth IEEE International Conference on Data Mining, 2008.
DOI : 10.1109/ICDM.2008.30

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

M. P. Consens, V. Fionda, S. Khatchadourian, and G. Pirrò, S+EPPs, Proceedings of the VLDB Endowment, vol.8, issue.12
DOI : 10.14778/2824032.2824128

, PVLDB, vol.8, issue.12, p.2015

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

M. P. Consens, R. J. Miller, F. Rizzolo, and A. A. Vaisman, Exploring XML web collections with DescribeX, ACM Transactions on the Web, vol.4, issue.3, 2010.
DOI : 10.1145/1806916.1806920

W. Fan, J. Li, X. Wang, and Y. Wu, Query preserving graph compression, Proceedings of the 2012 international conference on Management of Data, SIGMOD '12, 2012.
DOI : 10.1145/2213836.2213855

F. Goasdoué, I. Manolescu, and A. Roati¸sroati¸s, Efficient query answering against dynamic RDF databases, Proceedings of the 16th International Conference on Extending Database Technology, EDBT '13, 2013.
DOI : 10.1145/2452376.2452412

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

Y. Guo, Z. Pan, and J. Heflin, LUBM: A benchmark for OWL knowledge base systems, Web Semantics: Science, Services and Agents on the World Wide Web, vol.3, issue.2-3, 2005.
DOI : 10.1016/j.websem.2005.06.005

S. Gurajada, S. Seufert, I. Miliaraki, and M. Theobald, Using Graph Summarization for Join-Ahead Pruning in a Distributed RDF Engine, Proceedings of Semantic Web Information Management on Semantic Web Information Management, SWIM'14, 2014.
DOI : 10.1145/2630602.2630610

P. Guzewicz and I. Manolescu, Quotient RDF Summaries Based on Type Hierarchies, DESWeb (Data Engineering meets the Semantic Web) Workshop, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01721163

M. R. Henzinger, T. A. Henzinger, and P. W. Kopke, Computing simulations on finite and infinite graphs, Proceedings of IEEE 36th Annual Foundations of Computer Science, 1995.
DOI : 10.1109/SFCS.1995.492576

R. Kaushik, P. Bohannon, J. F. Naughton, and H. F. Korth, Covering indexes for branching path queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data , SIGMOD '02, 2002.
DOI : 10.1145/564691.564707

R. Kaushik, P. Bohannon, J. F. Naughton, H. F. Korth, R. Kaushik et al., Covering indexes for branching path queries Exploiting local similarity for indexing paths in graph-structured data, SIGMOD ICDE, 2002.
DOI : 10.1109/icde.2002.994703
URL : http://www.cs.wisc.edu/~raghav/icde2002.ps

K. Khan, W. Nawaz, and Y. Lee, Set-based approximate approach for lossless graph summarization, Computing, vol.31, issue.4, pp.1185-1207, 2015.
DOI : 10.1145/2463676.2463723

S. Khatchadourian and M. P. Consens, ExpLOD: Summary-Based Exploration of Interlinking and RDF Usage in the Linked Open Data Cloud, ESWC, 2010.
DOI : 10.1007/978-3-642-13489-0_19
URL : https://link.springer.com/content/pdf/10.1007%2F978-3-642-13489-0_19.pdf

S. Khatchadourian and M. P. Consens, Constructing Bisimulation Summaries on a Multi-Core Graph Processing Framework, Proceedings of the GRADES'15 on, GRADES'15, 2015.
DOI : 10.1145/79173.79181

K. Lefevre and E. Terzi, GraSS: Graph Structure Summarization, SDM, 2010.
DOI : 10.1137/1.9781611972801.40

S. Lin, M. Yeh, and C. Li, Sampling and summarization for social networks (tutorial, p.2013

Y. Liu, T. Safavi, A. Dighe, and D. Koutra, Graph Summarization Methods and Applications, ACM Computing Surveys, vol.51, issue.3, pp.1-6234, 2018.
DOI : 10.1007/978-3-319-46523-4_39

T. Milo and D. Suciu, Index Structures for Path Expressions, ICDT, 1999.
DOI : 10.1007/3-540-49257-7_18
URL : http://oopsla.snu.ac.kr/xweet/seminar/index-semi.ps

S. Navlakha, R. Rastogi, and N. Shrivastava, Graph summarization with bounded error, Proceedings of the 2008 ACM SIGMOD international conference on Management of data , SIGMOD '08, 2008.
DOI : 10.1145/1376616.1376661
URL : http://www.cs.umd.edu/~saket/pubs/sigmod2008.pdf

F. Picalausa, Y. Luo, G. H. Fletcher, J. Hidders, and S. Vansummeren, A Structural Approach to Indexing Triples, 2012.
DOI : 10.1007/978-3-642-30284-8_34
URL : https://link.springer.com/content/pdf/10.1007%2F978-3-642-30284-8_34.pdf

E. Pietriga, H. Gözükan, C. Appert, M. Destandau, F. ?ejla?ebiri´c?ejla??ejla?ebiri´?ejla?ebiri´c et al., Browsing linked data catalogs with LODAtlas, Int'l. Semantic Web Conference (ISWC), Resources track, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01827766

M. Rudolf, M. Paradies, C. Bornhövd, and W. Lehner, SynopSys, First International Workshop on Graph Data Management Experiences and Systems, GRADES '13, 2013.
DOI : 10.1145/2484425.2484441

A. Schätzle, A. Neu, G. Lausen, and M. Przyjaciel-zablocki, Large-scale bisimulation of RDF graphs, Proceedings of the Fifth Workshop on Semantic Web Information Management, SWIM '13, 2013.
DOI : 10.1145/2484712.2484713

Y. Tian, R. A. Hankins, and J. M. Patel, Efficient aggregation for graph summarization, Proceedings of the 2008 ACM SIGMOD international conference on Management of data , SIGMOD '08, 2008.
DOI : 10.1145/1376616.1376675
URL : http://www.cs.wisc.edu/~jignesh/publ/summarization.pdf

T. Tran, G. Ladwig, and S. Rudolph, Managing Structured and Semistructured RDF Data Using Structure Indexes, IEEE Transactions on Knowledge and Data Engineering, vol.25, issue.9, p.2013
DOI : 10.1109/TKDE.2012.134

, Resource description framework, W3C

P. Zhao, J. X. Yu, and P. S. Yu, Graph indexing: Tree + delta >= graph For the interested reader, we include here the proofs of all the statements made in the paper. The main proofs are those of our general shortcut Theorems 1 and 2, those of W and S shortcuts (Theorems 3 and 4), and the correctness proofs for our incremental algorithms (Propositions 6 and 7) The other claims proved here are used in these main proofs, VLDB, 2007.