A. K. Chandra and P. M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing , STOC '77, pp.77-90, 1977.
DOI : 10.1145/800105.803397

P. Bernstein and D. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM, vol.28, issue.1, pp.25-40, 1981.
DOI : 10.1145/322234.322238
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.117.804

M. Yannakakis, Algorithms for acyclic database schemes, VLDB'81, pp.82-94, 1981.

D. Calvanese, G. D. Giacomo, and M. Lenzerini, Conjunctive query containment and answering under description logic constraints, ACM Transactions on Computational Logic, vol.9, issue.3, pp.22-23, 2008.
DOI : 10.1145/1352582.1352590
URL : http://arxiv.org/pdf/cs/0507067v1.pdf

M. W. Chekol, J. Euzenat, P. Genevès, and N. Layaïda, SPARQL Query Containment under RDFS Entailment Regime, IJCAR'12, pp.134-148, 2012.
DOI : 10.1007/978-3-642-31365-3_13
URL : https://hal.archives-ouvertes.fr/hal-00691610

D. Kozen, Results on the Propositional ??-Calculus, DAIMI Report Series, vol.11, issue.146, pp.333-354, 1983.
DOI : 10.7146/dpb.v11i146.7420

Y. Tanabe, K. Takahashi, M. Yamamoto, A. Tozawa, and M. Hagiya, A Decision Procedure for the Alternation-Free Two-Way Modal ??-Calculus, TABLEAUX, pp.277-291, 2005.
DOI : 10.1007/11554554_21

P. Genevès, N. Layaïda, and A. Schmitt, Efficient Static Analysis of XML Paths and Types, PLDI '07, pp.342-351, 2007.

A. Letelier, J. Pérez, R. Pichler, and S. Skritek, Static analysis and optimization of semantic web queries, PODS'12, pp.89-100, 2012.

E. Prud-'hommeaux and A. Seaborne, SPARQL query language for RDF, W3C Rec, 2008.

C. Chekuri and A. Rajaraman, Conjunctive query containment revisited, Database Theory?ICDT'97, pp.56-70, 1997.
DOI : 10.1016/s0304-3975(99)00220-0
URL : http://doi.org/10.1016/s0304-3975(99)00220-0

G. Gottlob, N. Leone, and F. Scarcello, The complexity of acyclic conjunctive queries, Journal of the ACM, vol.48, issue.3, pp.431-498, 2001.
DOI : 10.1145/382780.382783

J. Gray, Benchmark handbook: for database and transaction processing systems, 1992.

M. W. Chekol, J. Euzenat, P. Genevès, and N. Layaïda, PSPARQL query containment, DBPL'11, 2011.
URL : https://hal.archives-ouvertes.fr/inria-00598819

J. Groppe, S. Groppe, and J. Kolbaum, Optimization of SPARQL by using coreSPARQL, ICEIS, issue.1, pp.107-112, 2009.

M. Stocker, A. Seaborne, A. Bernstein, C. Kiefer, and D. Reynolds, SPARQL basic graph pattern optimization using selectivity estimation, Proceeding of the 17th international conference on World Wide Web , WWW '08, pp.595-604, 2008.
DOI : 10.1145/1367497.1367578
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.401.557

M. Schmidt, M. Meier, and G. Lausen, Foundations of SPARQL query optimization, Proceedings of the 13th International Conference on Database Theory, ICDT '10, pp.4-33, 2010.
DOI : 10.1145/1804669.1804675
URL : http://arxiv.org/abs/0812.3788

C. Bizer and A. Schultz, Benchmarking the performance of storage systems that expose SPARQL endpoints, Proc. 4 th International Workshop on Scalable Semantic Web Knowledge Base Systems (SSWS), 2008.

M. Schmidt, T. Hornung, G. Lausen, and C. Pinkel, SP?2BenchSP?2Bench: a SPARQL performance benchmark, ICDE'09. Ieee, pp.222-233, 2009.

R. N°-8128 and R. Centre-grenoble-?-rhône-alpes, Inovallée 655 avenue de l'Europe Montbonnot 38334 Saint Ismier Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria, pp.249-6399