R. Abiteboul, V. Hull, and . 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=10.1.1.101.4120

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

P. Amarilli, P. Bourhis, and . Senellart, Provenance circuits for trees and treelike instances (extended version). CoRR, abs/1511, 2015.
DOI : 10.1007/978-3-662-47666-6_5
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.696.3395

P. Amarilli, P. Bourhis, and . 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

P. Amarilli, P. Bourhis, and . 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

B. Bárány, M. Cate, and . Otto, Queries with guarded negation, p.2012

B. Bárány, L. Cate, and . Segoufin, Guarded negation, J. ACM, vol.62, issue.3, p.2015

. Barceló, Querying graph databases, PODS, 2013.

M. Barceló, M. Y. Romero, and . Vardi, Does query evaluation tractability help query containment?, Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS '14, 2014.
DOI : 10.1145/2594538.2594553

P. Benedikt, P. Bourhis, and . Senellart, Monadic Datalog Containment, ICALP, 2012.
DOI : 10.1007/978-3-642-31585-5_11
URL : https://hal.archives-ouvertes.fr/hal-00809306

P. Benedikt, M. Bourhis, . Vanden, and . 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

G. Benedikt and . 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

B. Benedikt, M. Cate, . Vanden, 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

R. Berry, G. Pogorelcnik, and . 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

E. Berwanger and . 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=10.1.1.21.3538

-. 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.

. Cachat, Two-Way Tree Automata Solving Pushdown Games, Automata logics, and infinite games, 2002.
DOI : 10.1007/3-540-36387-4_17
URL : https://hal.archives-ouvertes.fr/hal-00019914

G. Calvanese, M. De-giacomo, M. Y. Lenzeniri, and . 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.

. 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

D. Dalvi and . 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

T. Deutch, S. Milo, V. Roy, and . Tannen, Circuits for Datalog provenance, ICDT, 2014.

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

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=10.1.1.120.8500

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

. 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

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=10.1.1.672.8161

N. Gottlob, F. Leone, and . 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

N. Gottlob, F. Leone, and . 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. 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, 2007.
DOI : 10.1145/1265530.1265535

D. Grohe and . 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=10.1.1.147.831

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

Y. Kimelfeld, Y. Kosharovsky, and . 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

P. Kimelfeld and . 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 and D. J. Spiegelhalter, Local computations with probabilities on graphical structures and their application to expert systems, J. Royal Statistical Society. Series B, 1988.

-. Leimer, Optimal decomposition by clique separators, Discrete Mathematics, vol.113, issue.1-3, 1993.
DOI : 10.1016/0012-365X(93)90510-Z
URL : http://doi.org/10.1016/0012-365x(93)90510-z

M. Leinders, J. Marx, J. V. Tyszkiewicz, and . 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
URL : http://arxiv.org/abs/cs/0407007

. Malik, Analysis of cyclic combinational circuits, ICCAD, 1993.

R. Maniu, P. Cheng, and . Senellart, ProbTree: A query-efficient representation of probabilistic graphs, BUDA, 2014.

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

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=10.1.1.51.5627

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

. 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. Riedel and J. Bruck, Cyclic Boolean circuits, Discrete Applied Mathematics, vol.160, issue.13-14, pp.13-14
DOI : 10.1016/j.dam.2012.03.039
URL : http://authors.library.caltech.edu/26130/1/etr099.pdf

P. D. Robertson and . 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

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

. 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

A. Abs15b, P. Amarilli, P. Bourhis, and . Senellart, Provenance circuits for trees and treelike instances, ICALP, 2015.

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

A. Ama16 and . Amarilli, Leveraging the structure of uncertain data, 2016.

P. Bar13 and . Barceló, Querying graph databases, PODS, 2013.

B. M. Benedikt, P. Bourhis, G. Gottlob, and P. Senellart, Monadic datalog and limited access containment
DOI : 10.1007/978-3-642-31585-5_11
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.337.9490

B. 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

B. H. Bodlaender and A. M. Koster, Treewidth computations I. Upper bounds, Information and Computation, vol.208, issue.3, 2010.
DOI : 10.1016/j.ic.2009.03.008
URL : http://doi.org/10.1016/j.ic.2009.03.008

H. Bms08a, W. Björklund, T. Martens, and . Schwentick, Optimizing conjunctive queries over trees using schema information, MFCS, 2008.

H. Bms08b, W. Björklund, T. Martens, and . Schwentick, Optimizing conjunctive queries over trees using schema information, 2008.

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

M. Btcv14, B. Benedikt, M. Cate, . Vanden, and . Boom, Effective interpolation and preservation in guarded logics, LICS, 2014.

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

C. S. Cosmadakis, H. Gaifman, P. Kanellakis, and M. Vardi, Decidable optimization problems for database logic programs, Proceedings of the twentieth annual ACM symposium on Theory of computing , STOC '88, 1988.
DOI : 10.1145/62212.62259

C. S. Chaudhuri and M. Y. Vardi, On the equivalence of recursive and nonrecursive Datalog programs, Journal of Computer and System Sciences, vol.54, issue.1, 1997.

F. J. Flum, M. Frick, and M. 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=10.1.1.120.8500

F. Gav74 and . Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combinatorial Theory, vol.16, issue.1, 1974.

T. R. Tarjan and M. Yannakakis, Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs, SIAM Journal on Computing, vol.13, issue.3, pp.566-579, 1984.
DOI : 10.1137/0213035

L. G. Val79 and . Valiant, The complexity of enumeration and reliability problems, SIAM Journal on Computing, vol.8, issue.3, 1979.