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

R. Alon, U. Yuster, and . Zwick, Finding and counting given length cycles, Algorithmica, vol.17, issue.3, 1997.
DOI : 10.1007/bf02523189

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

A. Amarilli, The possibility problem for probabilistic XML, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01190712

A. Amarilli, P. Bourhis, M. Monet, and P. Senellart, Combined tractability of query evaluation via tree automata and cycluits (extended version
URL : https://hal.archives-ouvertes.fr/hal-01439309

A. Amarilli, P. Bourhis, and P. Senellart, Provenance Circuits for Trees and Treelike Instances, ICALP, 2015.
DOI : 10.1007/978-3-662-47666-6_5

URL : https://hal.archives-ouvertes.fr/hal-01178399

A. Amarilli, P. Bourhis, and P. Senellart, Provenance circuits for trees and treelike instances (extended version). CoRR, abs/1511, 2015.

A. Amarilli, P. Bourhis, and P. Senellart, Tractable Lineages on Treelike Instances, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS '16, 2016.
DOI : 10.1145/2902251.2902301

URL : https://hal.archives-ouvertes.fr/hal-01336514

V. Bárány, M. Balder-ten-cate, and . Otto, Queries with guarded negation, p.2012

V. Bárány, L. Balder-ten-cate, and . Segoufin, Guarded negation, J. ACM, vol.62, issue.3, p.2015

P. Barceló, Querying graph databases, PODS, 2013. 11 Pablo Barceló, Miguel Romero, and Moshe Y Vardi. Does query evaluation tractability help query containment? In PODS, 2014.

M. Benedikt, P. Bourhis, and P. Senellart, Monadic Datalog Containment, ICALP, 2012.
DOI : 10.1007/978-3-642-31585-5_11

URL : https://hal.archives-ouvertes.fr/hal-00809306

M. Benedikt, P. Bourhis, and M. V. Boom, A Step Up in Expressiveness of Decidable Fixpoint Logics, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, 2016.
DOI : 10.1145/2933575.2933592

URL : https://hal.archives-ouvertes.fr/hal-01413890

M. Benedikt and G. Gottlob, The impact of virtual views on containment, Proceedings of the VLDB Endowment, vol.3, issue.1-2, p.2010
DOI : 10.14778/1920841.1920882

M. Benedikt, M. V. Balder-ten-cate, and . Boom, Effective interpolation and preservation in guarded logics, LICS, 2014.
DOI : 10.1145/2814570

URL : https://ora.ox.ac.uk/objects/uuid:d88f4697-5d57-4422-8a4c-48af0f30c8f8/datastreams/ATTACHMENT01

A. Berry, R. Pogorelcnik, and G. Simonet, An Introduction to Clique Minimal Separator Decomposition, Algorithms, vol.3, issue.2, p.2010
DOI : 10.3390/a3020197

URL : https://hal.archives-ouvertes.fr/lirmm-00485851

D. Berwanger and E. Grädel, Games and Model Checking for Guarded Logics, LPAR, 2001.
DOI : 10.1007/3-540-45653-8_5

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

C. Birget, State-complexity of finite-state devices, state compressibility and incompressibility, Mathematical Systems Theory, vol.30, issue.3, 1993.
DOI : 10.1007/BF01371727

L. Bodlaender, A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput, vol.25, issue.6, 1996.

T. Cachat, Two-Way Tree Automata Solving Pushdown Games, Automata logics, and infinite games, chapter 17, 2002.
DOI : 10.1007/3-540-36387-4_17

URL : https://hal.archives-ouvertes.fr/hal-00019914

D. Calvanese, G. D. Giacomo, M. Lenzeniri, and M. Y. Vardi, Containment of conjunctive regular path queries with inverse, KR, 2000.

B. Cohen, Y. Kimelfeld, and . Sagiv, Running tree automata on probabilistic XML, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS '09, 2009.
DOI : 10.1145/1559795.1559831

M. Comon, R. Dauchet, C. Gilleron, F. Löding, D. Jacquemard et al., Tree automata: Techniques and applications Available from http, 2007.

B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Information and Computation, vol.85, issue.1, 1990.
DOI : 10.1016/0890-5401(90)90043-H

URL : https://hal.archives-ouvertes.fr/hal-00353765

N. Dalvi and D. Suciu, Management of probabilistic data, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '07, 2007.
DOI : 10.1145/1265530.1265531

R. Diestel, Simplicial decompositions of graphs: A survey of applications, Discrete Math, vol.75, issue.1, 1989.

. Fagin, Degrees of acyclicity for hypergraphs and relational database schemes, Journal of the ACM, vol.30, issue.3, 1983.
DOI : 10.1145/2402.322390

M. Flum and . Grohe, Parameterized Complexity Theory, 2006.

M. Flum, M. Frick, and . Grohe, Query evaluation via tree-decompositions, J. ACM, vol.49, issue.6, 2002.
DOI : 10.1007/3-540-44503-x_2

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, Journal of Combinatorial Theory, Series B, vol.16, issue.1, 1974.
DOI : 10.1016/0095-8956(74)90094-X

E. Gottlob, H. Grädel, and . Veith, Datalog LITE: a deductive query language with linear time model checking, ACM Transactions on Computational Logic, vol.3, issue.1, 2002.
DOI : 10.1145/504077.504079

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

G. Gottlob, F. Greco, and . Scarcello, Treewidth and Hypertree Width, Tractability: Practical Approaches to Hard Problems, 2014.
DOI : 10.1017/CBO9781139177801.002

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

G. Gottlob, N. Leone, and F. Scarcello, Hypertree decompositions and tractable queries, JCSS, vol.64, issue.3, 2002.
DOI : 10.1006/jcss.2001.1809

URL : http://doi.org/10.1006/jcss.2001.1809

G. Gottlob, N. Leone, and F. Scarcello, Robbers, marshals, and guards, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '01, 2003.
DOI : 10.1145/375551.375579

R. Gottlob, F. Pichler, and . Wei, Monadic Datalog over finite structures of bounded treewidth, TOCL, vol.12, issue.1, 2010.
DOI : 10.1145/1838552.1838555

J. Todd, G. Green, V. Karvounarakis, and . Tannen, Provenance semirings, PODS, 2007.

M. Grohe and D. Marx, Constraint solving via fractional edge covers, TALG, vol.11, issue.1, p.2014
DOI : 10.1145/2636918

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

T. Imielinski, W. Lipski, and J. , Incomplete information in relational databases, J. ACM, vol.31, issue.4, 1984.

B. Kimelfeld, Y. Kosharovsky, and Y. Sagiv, Query efficiency in probabilistic XML models, Proceedings of the 2008 ACM SIGMOD international conference on Management of data , SIGMOD '08, 2008.
DOI : 10.1145/1376616.1376687

B. Kimelfeld and P. Senellart, Probabilistic XML: Models and Complexity, Advances in Probabilistic Databases for Uncertain Information Management, 2013.
DOI : 10.1007/978-3-642-37509-5_3

URL : https://hal.archives-ouvertes.fr/hal-00874441

L. Lauritzen, J. David, and . Spiegelhalter, Local computations with probabilities on graphical structures and their application to expert systems 43 Hanns-Georg Leimer. Optimal decomposition by clique separators, J. Royal Statistical Society. Series B Discrete Math, vol.113, pp.1-3, 1988.

D. Leinders, M. Marx, J. Tyszkiewicz, and J. Van-den-bussche, The Semijoin Algebra and the Guarded Fragment, Journal of Logic, Language and Information, vol.10, issue.3, 2005.
DOI : 10.1007/s10849-005-5789-8

S. Malik, Analysis of cyclic combinational circuits ProbTree: A query-efficient representation of probabilistic graphs, ICCAD, 1993. 46 Silviu Maniu BUDA, 2014.

D. Marx, Can you beat treewidth? Theory of Computing, 2010.
DOI : 10.1109/focs.2007.27

A. O. Mendelzon and P. T. Wood, Finding Regular Simple Paths in Graph Databases, VLDB, 1989.
DOI : 10.1137/S009753979122370X

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

A. R. Meyer, Weak monadic second order theory of succesor is not elementary-recursive, Logic Colloquium, 1975.
DOI : 10.1007/BFb0064872

M. Monet, Probabilistic Evaluation of Expressive Queries on Bounded-Treewidth Instances, Proceedings of the 2016 on SIGMOD'16 PhD Symposium, SIGMOD'16 PhD, 2016.
DOI : 10.1145/2926693.2929905

D. Marc, J. Riedel, and . Bruck, Cyclic Boolean circuits, Discrete Applied Mathematics, vol.160, pp.13-14

N. Robertson and P. D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, Journal of Algorithms, vol.7, issue.3
DOI : 10.1016/0196-6774(86)90023-4

URL : http://doi.org/10.1006/jctb.1999.1919

R. E. Tarjan, Decomposition by clique separators, Discrete Mathematics, vol.55, issue.2, 1985.
DOI : 10.1016/0012-365X(85)90051-2

URL : http://doi.org/10.1016/0012-365x(85)90051-2

A. Tarski, A lattice-theoretical fixpoint theorem and its applications, Pacific Journal of Mathematics, vol.5, issue.2, 1955.
DOI : 10.2140/pjm.1955.5.285

URL : http://projecteuclid.org/download/pdf_1/euclid.pjm/1103044538

Y. Moshe and . Vardi, The complexity of relational query languages, STOC, 1982.

M. Y. Vardi, On the complexity of bounded-variable queries, PODS, pp.266-276, 1995.

M. Yannakakis, Algorithms for acyclic database schemes, VLDB, 1981.