D. Indeed, B. , and S. , From Lemma 6 Furthermore , in the proof of Lemma 6.21, it is shown that, We have that d b ([ p[X B ]] + [q[X B ]]) = d b ([ p[X B ] + q

S. , S. Thenp, |. , and N. , Since ? b is the identity mapping, this follows from the correspondence between the boolean operations on elements in B X and boolean operations on supports (cf. Lemma 6.21) More specifically, denote by S and S the carrier sets of T and T , respectively. Furthermore, let, For sb 6

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

Y. Amsterdamer, D. Deutch, and V. Tannen, On the limitations of provenance for queries with difference, Proceedings of the 3rd USENIX Workshop on the Theory and Practice of Provenance, 2011.

Y. Amsterdamer, D. Deutch, and V. Tannen, Provenance for aggregate queries, Proceedings of the 30th symposium on Principles of database systems of data, PODS '11, 2011.
DOI : 10.1145/1989284.1989302
URL : http://arxiv.org/abs/1101.1110

R. Angles and C. Gutierrez, The Expressive Power of SPARQL, International Semantic Web Conference, pp.114-129, 2008.
DOI : 10.1007/978-3-540-74565-5_14

P. Buneman, J. Cheney, and S. Vansummeren, On the expressiveness of implicit provenance in query and update languages, ACM Transactions on Database Systems, vol.33, issue.28, p.47, 2008.

P. Buneman and E. V. Kostylev, Annotation algebras for RDFS, Proceedings of the 2nd International Workshop on the role of Semantic Web in Provenance Management. CEUR Workshop Proceedings, Article 1, 6 pages. ceur-ws.org, 2011.

S. Burris and H. P. Sankappanavar, A Course in Universal Algebra. Number 78 in Graduate Texts in Mathematics, 1981.
DOI : 10.1007/978-1-4613-8130-3

J. Carroll, C. Bizer, P. Hayes, and P. Stickler, Named graphs, Web Semantics: Science, Services and Agents on the World Wide Web, pp.247-267, 2005.
DOI : 10.1016/j.websem.2005.09.001

J. Cheney, L. Chiticariu, and W. Tan, Provenance in Databases: Why, How, and Where, Foundations and Trends in Databases, vol.1, issue.4, pp.379-474, 2009.
DOI : 10.1561/1900000006
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.165.6994

C. Viegas-damásiodam´damásio, A. Analyti, and G. Antoniou, Provenance for SPARQL Queries, Proceedings of the 11th International Conference on the Semantic Web (ISWC'12, pp.625-640, 2012.
DOI : 10.1007/978-3-642-35176-1_39

R. Dividino, S. Sizov, S. Staab, and B. Schueler, Querying for provenance, trust, uncertainty and other meta knowledge in RDF???, Web Semantics: Science, Services and Agents on the World Wide Web, vol.7, issue.3, pp.204-219, 2009.
DOI : 10.1016/j.websem.2009.07.004
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.175.1875

J. , N. Foster, T. J. Green, and V. Tannen, Annotated XML: Queries and provenance, Proceedings of the 27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS'08, pp.271-280, 2008.
DOI : 10.1145/1376916.1376954

R. Michael, D. S. Garey, and . Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.

F. Geerts and G. Karvounarakis, Vassilis Christophides, and Irini Fundulaki Algebraic structures for capturing the provenance of SPARQL queries, Proceedings of the 16th International Conference on Database Theory (ICDT'13). ACM, pp.153-164, 2013.

F. Geerts and A. Poggi, On database query languages for K-relations, Journal of Applied Logic, vol.8, issue.2, pp.173-185, 2010.
DOI : 10.1016/j.jal.2009.09.001
URL : http://doi.org/10.1016/j.jal.2009.09.001

B. Glavic and G. Alonso, Perm: Processing Provenance and Data on the Same Data Model through Query Rewriting, 2009 IEEE 25th International Conference on Data Engineering, pp.174-185, 2009.
DOI : 10.1109/ICDE.2009.15
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.172.8566

T. J. Green, Containment of conjunctive queries on annotated relations, Theory of Computing Systems, pp.429-459, 2011.
DOI : 10.1145/1514894.1514930

T. J. Green, G. Karvounarakis, and V. Tannen, Provenance semirings, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '07, pp.31-40, 2007.
DOI : 10.1145/1265530.1265535

S. Harris and A. Seaborne, SPARQL 1.1 Query Language, 2013.

O. Hartig, Specification for tSPARQL, 2008.
DOI : 10.1007/978-3-642-02121-3_5
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.363.577

O. Hartig, Querying Trust in RDF Data with tSPARQL, Proceedings of the 6th European Semantic Web Conference on The Semantic Web: Research and Applications (ESWC'09, pp.5-20, 2009.
DOI : 10.1007/978-3-642-02121-3_5
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.363.577

H. Huang and C. Liu, Query Evaluation on Probabilistic RDF Databases, Proceedings of the 10th International Conference on Web Information Systems Engineering (WISE'09), pp.307-320, 2009.
DOI : 10.1007/978-3-642-04409-0_32

V. Edward and . Huntington, Boolean algebra. A correction, Transactions of the American Mathematical Society, vol.35, issue.2, pp.557-558, 1933.

V. Edward and . Huntington, New sets of independent postulates for the algebra of logic, with special reference to Whitehead and Russell, Transactions of the American Mathematical Society, vol.35, pp.274-304, 1933.

G. Karvounarakis, T. J. Green, Z. G. Ives, and V. Tannen, Collaborative data sharing via update exchange and provenance, ACM Transactions on Database Systems, vol.38, issue.3, 2013.
DOI : 10.1145/2508020.2500127

G. Karvounarakis, Z. G. Ives, and V. Tannen, Querying data provenance, Proceedings of the 2010 international conference on Management of data, SIGMOD '10, pp.951-962, 2010.
DOI : 10.1145/1807167.1807269
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.210.2019

A. Kementsietsidis, E. Pema, and W. Tan, Query answering over incomplete and uncertain RDF, Proceedings of the 17th International Workshop on the Web and Databases, 2014.

M. Mazzieri and A. F. Dragoni, A Fuzzy Semantics for the Resource Description Framework, Lecture Notes in Computer Science, vol.114, issue.3, pp.244-261, 2008.
DOI : 10.1007/3-540-48005-6_7

W. Mccune, Prover9 and Mace4, 2005.

J. Pérez, M. Arenas, and C. Gutierrez, Semantics and complexity of SPARQL, ACM Transactions on Database Systems, vol.34, issue.16, p.45, 2009.

E. Prud-'hommeaux and A. Seaborne, SPARQL Query Language for RDF. www.w3.org/TR/ rdf-sparql-query, 2008.

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

U. Straccia, Foundations of Fuzzy Logic and Semantic Web Languages, 2013.
DOI : 10.1007/978-3-642-23963-2_2

Y. Theoharis and I. Fundulaki, On Provenance of Queries on Semantic Web Data, IEEE Internet Computing, vol.15, issue.1, pp.31-39, 2011.
DOI : 10.1109/MIC.2010.127

M. Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing , STOC '82, pp.137-146, 1982.
DOI : 10.1145/800070.802186

A. Zimmermann, N. Lopes, A. Polleres, and U. Straccia, A general framework for representing, reasoning and querying with annotated Semantic Web data, Web Semantics: Science, Services and Agents on the World Wide Web, vol.11, pp.72-95, 2012.
DOI : 10.1016/j.websem.2011.08.006
URL : https://hal.archives-ouvertes.fr/hal-01240838