, 1, we know that any d-SDNNF for ?(Q, I ) has size 2 ? tw(H) for some constant ? > 0 (depending only on the arity and degree bounds on I given above, which depend only on Q), which by Lemma 4.8.7 is 2 ?tw(I ) for a different constant ? > 0 and tw(I ) large enough. By definition of S k , we obtain the lower bound of 2 ?f (k) for k large enough. Now, to conclude, we must show that this lower bound also applies to any d-SDNNF for ?(Q, I)

A. Amarilli, P. Bourhis, M. Monet, and P. Senellart, Evaluating Datalog via Tree Automata and Cycluits, Theory of Computing Systems, p.57, 2018.
DOI : 10.1007/s00224-018-9901-2
URL : https://hal.archives-ouvertes.fr/hal-01891814

, Peer-Reviewed Conference Articles

A. Amarilli, P. Bourhis, M. Monet, and P. Senellart, Combined Tractability of Query Evaluation via Tree Automata and Cycluits, ICDT (cit. on pp. 57, vol.64, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01439294

A. Amarilli, S. Maniu, and M. Monet, Challenges for Efficient Query Evaluation on Structured Probabilistic Data, SUM (cit, p.144, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01360167

A. Amarilli, M. Monet, and P. Senellart, Conjunctive Queries on Probabilistic Graphs: Combined Complexity". In: PODS (cit, p.31, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01486634

A. Amarilli, M. Monet, and P. Senellart, Connecting Width and Structure in Knowledge Compilation". In: ICDT (cit, p.107, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01851564

, Peer-Reviewed Workshop Articles

M. Monet, Probabilistic Evaluation of Expressive Queries on BoundedTreewidth Instances, SIGMOD/PODS PhD Symposium, p.144, 2016.

M. Monet and D. Olteanu, Towards Deterministic Decomposable Circuits for Safe Queries, vol.141, p.12, 2018.

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

A. V. Aho and J. E. Hopcroft, The Design and Analysis of Computer Algorithms, p.19, 1974.

R. Noga-alon, U. Yuster, and . Zwick, Finding and Counting Given Length Cycles, Algorithmica (cit, p.59, 1997.

A. Amarilli, The Possibility Problem for Probabilistic XML, p.143, 2014.
DOI : 10.3166/isi.20.5.53-75
URL : https://hal.archives-ouvertes.fr/hal-01190712

A. Amarilli, Leveraging the Structure of Uncertain Data, vol.89, pp.125-127, 2016.
URL : https://hal.archives-ouvertes.fr/tel-01345836

A. Amarilli, P. Bourhis, L. Jachiet, and S. Mengel, A Circuit-Based Approach to Efficient Enumeration, ICALP (cit. on pp. 9, vol.28, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01639179

A. Amarilli, P. Bourhis, and P. Senellart, Provenance Circuits for Trees and Treelike Instances". In: ICALP (cit. on pp. 2-4, vol.148, pp.151-154, 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, Tractable Lineages on Treelike Instances: Limits and Extensions". In: PODS (cit. on pp. 9, vol.10, pp.133-135, 2016.
DOI : 10.1145/2902251.2902301
URL : https://hal.archives-ouvertes.fr/hal-01336514

S. Arnborg, D. G. Corneil, and A. Proskurowski, Complexity of Finding Embeddings in a k-tree, SIAM Journal on Algebraic and Discrete Methods (cit, p.23, 1987.
DOI : 10.1137/0608024

K. Chandra, M. Y. Ashok, and . Vardi, The Implication Problem for Functional and Inclusion Dependencies is Undecidable, SIAM Journal on Computing, p.74, 1985.
DOI : 10.1137/0214049

S. Asthana, O. D. King, F. D. Gibbons, and F. P. Roth, Predicting Protein Complex Membership Using Probabilistic Network Reliability, Genome Research, 2004.
DOI : 10.1101/gr.2203804
URL : http://genome.cshlp.org/content/14/6/1170.full.pdf

G. Audemard and L. Simon, Predicting Learnt Clauses Quality in Modern SAT Solvers". In: IJCAI (cit, p.11, 2009.

V. Bárány, M. Balder-ten-cate, and . Otto, Queries with Guarded Negation, PVLDB (cit, p.74, 2012.

V. Bárány, L. Balder-ten-cate, and . Segoufin, Guarded Negation, Journal of the ACM (cit, vol.74, p.73, 2015.

D. Barbará, H. Garcia-molina, and D. Porter, The Management of Probabilistic Data, IEEE Transactions on Knowledge and Data Engineering, 1992.

P. Barceló, Querying Graph Databases, PODS (cit. on pp. 7, 17, vol.58, p.76, 2013.

P. Barceló, M. Romero, and M. Y. Vardi, Does Query Evaluation Tractability Help Query Containment?, In: PODS (cit. on pp. 7, 58, vol.152, p.76, 2014.

P. Beame, J. Li, S. Roy, and D. Suciu, Exact Model Counting of Query Expressions: Limitations of Propositional Methods, ACM Transactions on Database Systems, p.11, 2017.

P. Beame and V. Liew, New Limits for Knowledge Compilation and Applications to Exact Model Counting". In: UAI (cit, p.109, 2015.

P. Beame, G. Van-den-broeck, E. Gribkoff, and D. Suciu, Symmetric Weighted First-order Model Counting, 2015.
DOI : 10.1145/2745754.2745760
URL : http://arxiv.org/pdf/1412.1505

M. Benedikt, P. Bourhis, and P. Senellart, Monadic Datalog Containment". In: ICALP (cit, p.64, 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, LICS (cit. on pp. 7, 58, vol.152, p.74, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01413890

M. Benedikt, M. V. Balder-ten-cate, and . Boom, Effective Interpolation and Preservation in Guarded Logics, LICS (cit, vol.74, p.73, 2014.

M. Benedikt and G. Gottlob, The Impact of Virtual Views on Containment, PVLDB (cit, p.69, 2010.

M. Benedikt and C. Koch, XPath Leashed". In: ACM Computing Surveys, p.143, 2009.

A. Berry, R. Pogorelcnik, and G. Simonet, An Introduction to Clique Minimal Separator Decomposition". In: Algorithms (cit, p.65, 2010.
URL : https://hal.archives-ouvertes.fr/lirmm-00485851

D. Berwanger and E. Grädel, Games and Model Checking for Guarded Logics, LPAR (cit. on pp. 60, vol.74, p.70, 2001.

J. Birget, State-Complexity of Finite-State Devices, State Compressibility and Incompressibility, Mathematical systems theory, p.63, 1993.

L. Hans and . Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal of Computing, vol.110, p.23, 1996.

L. Hans, A. M. Bodlaender, and . Koster, Treewidth Computations I. Upper Bounds". In: Information and Computation, p.98, 2010.

S. Bova, SDDs are Exponentially More Succinct than OBDDs, AAAI (cit, p.143, 2016.

S. Bova, F. Capelli, S. Mengel, and F. Slivovsky, A Strongly Exponential Separation of DNNFs from CNF Formulas, CoRR (cit, p.124, 2015.

S. Bova, F. Capelli, S. Mengel, and F. Slivovsky, Knowledge Compilation Meets Communication Complexity, IJCAI (cit. on pp. 10, vol.109, pp.130-132, 2016.

S. Bova and F. Slivovsky, On Compiling Structured CNFs to OBDDs, CSR (cit, p.129, 2015.

S. Bova and F. Slivovsky, On Compiling Structured CNFs to OBDDs, Theoretical Computer Science, 2017.

S. Bova and S. Szeider, Circuit Treewidth, Sentential Decision, and Query Compilation, 2017.
DOI : 10.1145/3034786.3034787
URL : http://arxiv.org/pdf/1701.04626

J. Brault-baron, Hypergraph Acyclicity Revisited". In: ArXiv e-prints, p.47, 2014.

J. Brault-baron, F. Capelli, and S. Mengel, Understanding Model Counting for ?-Acyclic CNF-Formulas, STACS (cit. on pp. 6, vol.33, pp.47-49, 2015.

R. E. Bryant, Symbolic Boolean Manipulation with Ordered BinaryDecision Diagrams, ACM Computing Surveys, vol.153, p.9, 1992.

A. A. Bulatov, The Complexity of the Counting Constraint Satisfaction Problem, Journal of the ACM (cit. on p, vol.32, 2013.

T. Cachat, Two-Way Tree Automata Solving Pushdown Games, Automata Logics, and Infinite Games (cit. on pp. 63, vol.101, p.79, 2002.
DOI : 10.1007/3-540-36387-4_17
URL : https://hal.archives-ouvertes.fr/hal-00019914

A. Calí, F. Capelli, and I. Razgon, Non-FPT Lower Bounds for Structural Restrictions of Decision DNNF, CoRR (cit, p.109, 2017.

D. Calvanese, G. D. Giacomo, M. Lenzeniri, and M. Y. Vardi, Containment of Conjunctive Regular Path Queries with Inverse". In: KR (cit, vol.76, p.17, 2000.

F. Capelli, Structural Restrictions of CNF-Formulas: Applications to Model Counting and Knowledge Compilation, 2016.

F. Capelli, Understanding the Complexity of #SAT Using Knowledge Compilation, LICS (cit, vol.130, p.109, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01836195

R. D. Cazé, M. Humphries, and B. Gutkin, Passive Dendrites Enable Single Neurons to Compute Linearly Non-separable Functions, PLOS Computational Biology. Code, p.11, 2013.

A. Ismail-ilkan-ceylan, G. Darwiche, and . Van-den-broeck, Open-World Probabilistic Databases, KR (cit, p.31, 2016.

C. Chekuri and J. Chuzhoy, Polynomial Bounds for the Grid-Minor Theorem, STOC (cit, vol.143, p.135, 2014.

E. F. Codd, A Relational Model of Data for Large Shared Data Banks, Communications of the ACM, 1970.

S. Cohen, B. Kimelfeld, and Y. Sagiv, Running Tree Automata on Probabilistic XML, 2009.

H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard et al., Tree Automata: Techniques and Applications, 2007.

B. Courcelle, The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs, Information and Computation (cit. on pp. 6, 7, 57, vol.60, p.151, 1990.
URL : https://hal.archives-ouvertes.fr/hal-00353765

R. Curticapean and D. Marx, Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover-Number Counts, FOCS (cit, p.32, 2014.

N. Nilesh, D. Dalvi, and . Suciu, Efficient Query Evaluation on Probabilistic Databases, VLDB Journal, 2007.

N. Nilesh, D. Dalvi, and . Suciu, The Dichotomy of Probabilistic Inference for Unions of Conjunctive Queries, Journal of the ACM, 2012.

E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov, Complexity and expressive power of logic programming, Comput. Surv, p.83, 2001.

A. Darwiche, On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision, Journal of Applied Non-Classical Logics (cit. on pp. 9, vol.54, 2001.

A. Darwiche, A Differential Approach to Inference in Bayesian Networks, Journal of the ACM (cit. on p, vol.113, 2003.

A. Darwiche, SDD: A New Canonical Representation of Propositional Knowledge Bases, IJCAI (cit, p.143, 2011.

D. Deutch, T. Milo, S. Roy, and V. Tannen, Circuits for Datalog Provenance, In: ICDT (cit. on pp, vol.27, 2014.

S. Devadas, Comparing Two-Level and Ordered Binary Decision Diagram Representations of Logic Functions, IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, 1993.

R. Diestel, Simplicial Decompositions of Graphs: a Survey of Applications, Discrete Mathematics, vol.75, p.64, 1989.

F. William, J. H. Dowling, and . Gallier, Linear-Time Algorithms for Testing the Satisfiability of Propositional Horn Formulae, J. Log. Program, p.83, 1984.

G. Rodney, M. R. Downey, and . Fellows, Fixed Parameter Tractability and Completeness, Complexity Theory: Current Research, 1992.

F. Feodor, F. V. Dragan, P. A. Fomin, and . Golovach, Spanners in Sparse Graphs, Journal of Computer and System Sciences, p.136, 2011.

R. Fagin, Degrees of Acyclicity for Hypergraphs and Relational Database Schemes, Journal of the ACM, p.59, 1983.

T. Feder and M. Y. Vardi, The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study Through Datalog and Group Theory, SIAM Journal on Computing, p.143, 1998.

A. Ferrara, G. Pan, and M. Y. Vardi, Treewidth in Verification: Local vs. Global". In: LPAR (cit, p.124, 2005.

D. Fierens, G. Van-den-broeck, J. Renkens, D. Shterionov, B. Gutmann et al., Inference and Learning in Probabilistic Logic Programs Using Weighted Boolean Formulas, Theory and Practice of Logic Programming, 2015.

G. S. Fishman, A Comparison of Four Monte Carlo Methods for Estimating the Probability of s-t Connectedness, IEEE Transactions on Reliability, vol.35, issue.2, 1986.

J. Flum, M. Frick, and M. Grohe, Query Evaluation via TreeDecompositions, Journal of the ACM, 2002.
DOI : 10.1145/602220.602222

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

L. Galárraga, S. Razniewski, A. Amarilli, and F. M. Suchanek, Predicting Completeness in Knowledge Bases, WSDM (cit, p.144, 2017.

F. Gavril, The Intersection Graphs of Subtrees in Trees are Exactly the Chordal Graphs, Journal of Combinatorial Theory, vol.98, p.65, 1974.

G. Gottlob, E. Grädel, and H. Veith, Datalog LITE: a Deductive Query Language with Linear Time Model Checking, ACM Transactions on Computational Logic, p.60, 2002.

G. Gottlob, G. Greco, and F. Scarcello, Treewidth and Hypertree Width, Tractability: Practical Approaches to Hard Problems. Cambridge University Press. Chap. 1 (cit, p.59, 2014.
DOI : 10.1017/cbo9781139177801.002
URL : https://www.mat.unical.it/%7Eggreco/files/GottlobGrecoScarcello.pdf

G. Gottlob, C. Koch, and K. U. Schulz, Conjunctive Queries Over Trees, Journal of the ACM (cit, vol.50, p.33, 2006.
DOI : 10.1145/1131342.1131345
URL : http://arxiv.org/pdf/cs/0602004

G. Gottlob, N. Leone, and F. Scarcello, Hypertree Decompositions and Tractable Queries, p.59, 2002.
DOI : 10.1145/303976.303979
URL : http://arxiv.org/pdf/cs/9812022v1.pdf

G. Gottlob, N. Leone, and F. Scarcello, Robbers, Marshals, and Guards: Game Theoretic and Logical Characterizations of Hypertree Width, Journal of Computer and System Sciences, p.60, 2003.

G. Gottlob, R. Pichler, and F. Wei, Monadic Datalog Over Finite Structures of Bounded Treewidth, ACM Transactions on Computational Logic (cit. on pp, vol.57, p.61, 2010.

E. Grädel, Guarded Fixed Point Logics and the Monadic Theory of Countable Trees, Theoretical of Computer Science (cit, p.74, 2002.

J. Todd, V. Green, and . Tannen, Models for Incomplete and Probabilistic Information, 2006.

G. Todd-j-green, V. Karvounarakis, and . Tannen, Provenance Semirings". In: PODS (cit. on pp, vol.27, 2007.

M. Grohe, The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side, Journal of the ACM, p.32, 2007.

M. Grohe and D. Marx, On Tree Width, Bramble Size, and Expansion, Journal of Combinatorial Theory, p.124, 2009.
DOI : 10.1016/j.jctb.2008.06.004
URL : https://doi.org/10.1016/j.jctb.2008.06.004

M. Grohe and D. Marx, Constraint Solving via Fractional Edge Covers, TALG (cit, p.59, 2014.
DOI : 10.1145/2636918
URL : http://arxiv.org/pdf/1711.04506

W. Gutjahr, E. Welzl, and G. Woeginger, Polynomial GraphColorings, Discrete Applied Mathematics (cit. on pp, vol.6, p.33, 1992.

F. Harary and A. J. Schwenk, The Number of Caterpillars, Discrete Mathematics, p.142, 1973.
DOI : 10.1016/0012-365x(73)90067-8
URL : https://doi.org/10.1016/0012-365x(73)90067-8

M. Hua and J. Pei, Probabilistic Path Queries in Road Networks: Traffic Uncertainty Aware Path Selection, 2010.
DOI : 10.1145/1739041.1739084

J. Huang, L. Antova, C. Koch, and D. Olteanu, MayBMS: a Probabilistic Database Management System, 2009.

T. Imielinski and W. Lipski, Incomplete Information in Relational Databases, Journal of the ACM (cit. on pp, vol.80, p.27, 1984.

R. Jampani, F. Xu, M. Wu, L. L. Perez, C. M. Jermaine et al., MCDB: a Monte Carlo Approach to Managing Uncertain Data, 2008.

A. Kumar-jha, D. Olteanu, and D. Suciu, Bridging the Gap Between Intensional and Extensional Query Evaluation in Probabilistic Databases, EDBT (cit. on pp. 9, vol.154, p.107, 2010.

A. Kumar-jha and D. Suciu, Knowledge Compilation Meets Database Theory: Compiling Queries to Decision Diagrams, ICDT (cit. on pp. 9, vol.154, p.107, 2011.

A. Kumar-jha and D. Suciu, On the Tractability of Query Compilation and Bounded Treewidth, ICDT (cit. on pp. 9, vol.107, 2012.

A. Jha and D. Suciu, Knowledge Compilation Meets Database Theory: Compiling Queries to Decision Diagrams, Theory of Computing Systems, p.11, 2013.
DOI : 10.1007/s00224-012-9392-5
URL : http://www.cs.washington.edu/homes/suciu/camera_ready.pdf

S. Khanna, S. Roy, and V. Tannen, Queries with Difference on Probabilistic Databases". In: PVLDB (cit, p.37, 2011.

B. Kimelfeld and P. Senellart, Probabilistic XML: Models and Complexity, Advances in Probabilistic Databases for Uncertain Information Management, vol.144, p.32, 2013.
DOI : 10.1007/978-3-642-37509-5_3
URL : https://hal.archives-ouvertes.fr/hal-00874441

V. S. Laks, N. Lakshmanan, R. B. Leone, V. S. Ross, and . Subrahmanian, ProbView: A Flexible Probabilistic Database System, ACM Transactions on Database Systems, p.1, 1997.

L. Steffen, D. J. Lauritzen, and . Spiegelhalter, Local Computations with Probabilities on Graphical Structures and their Application to Expert Systems, Journal of the Royal Statistical Society (cit. on pp, vol.9, 1988.

H. Leimer, Optimal Decomposition by Clique Separators, Discrete Mathematics, p.65, 1993.
DOI : 10.1016/0012-365x(93)90510-z
URL : https://doi.org/10.1016/0012-365x(93)90510-z

D. Leinders, M. Marx, J. Tyszkiewicz, and J. Van-den-bussche, The Semijoin Algebra and the Guarded Fragment, Journal of Logic, Language and Information, p.59, 2005.

S. Malik, Analysis of Cyclic Combinational Circuits, ICCAD (cit, p.59, 1993.

S. Maniu, R. Cheng, and P. Senellart, An Indexing Framework for Queries on Probabilistic Graphs, ACM Transactions on Database Systems, p.144, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01437580

E. A. Marshall and D. R. Wood, Circumference and Pathwidth of Highly Connected Graphs, Journal of Graph Theory, p.109, 2014.

A. O. Mendelzon and P. T. Wood, Finding Regular Simple Paths in Graph Databases, VLDB (cit, p.76, 1989.

A. R. Meyer, Weak Monadic Second Order Theory of Succesor is not Elementary-Recursive, Logic Colloquium, 1975.

J. C. Mitchell, The Implication Problem for Functional and Inclusion Dependencies, Information and Control, p.74, 1983.

N. Joakim-alme, Exploring Graph Parameters Similar to TreeWidth and Path-Width, p.125, 2017.

S. Odagiri and H. Goto, On the Greatest Number of Paths and Maximal Paths for a Class of Directed Acyclic Graphs, IEICE Transactions on Fundamentals of Electronics, 2014.

K. Other-references, A. Pipatsrisawat, and . Darwiche, New Compilation Languages Based on Structured Decomposability, AAAI (cit. on pp. 9, vol.154, p.28, 2008.

K. Pipatsrisawat and A. Darwiche, A Lower Bound on the Size of Decomposable Negation Normal Form, AAAI (cit. on pp. 109, vol.130, 2010.

, The Complexity of Counting Cuts and of Computing the Probability That a Graph is Connected, SIAM Journal of Computing, p.43, 1983.

I. Razgon, On OBDDs for CNFs of Bounded Treewidth, 2014.

C. Ré, N. Nilesh, D. Dalvi, and . Suciu, Efficient Top-k Query Evaluation on Probabilistic Data, 2007.

C. Ré and D. Suciu, Materialized Views in Probabilistic Databases: For Information Exchange and Query Optimization, 2007.

D. Marc, J. Riedel, and . Bruck, Cyclic Boolean Circuits, Discrete Applied Mathematics (cit. on pp, vol.59, 2012.

N. Robertson and P. D. Seymour, Graph Minors. III. Planar TreeWidth, Journal of Combinatorial Theory, p.21, 1984.

N. Robertson and P. D. Seymour, Graph Minors. II. Algorithmic Aspects of Tree-Width, Journal of Algorithms, p.57, 1986.

N. Robertson and P. D. Seymour, Graph Minors. X. Obstructions to Tree-Decomposition, Journal of Combinatorial Theory, p.130, 1991.

B. Schröder, Ordered Sets. An Introduction with Connections from Combinatorics to Topology. Birkhäuser (cit, vol.40, p.33, 2016.

A. A. Sherstov, Communication Complexity Theory: Thirty-Five Years of Set Disjointness, MFCS (cit, p.133, 2014.

R. Stanley, Enumerative Combinatorics, p.40, 1997.

T. Stephen and T. Yusun, Counting Inequivalent Monotone Boolean Functions, Discrete Applied Mathematics, p.11, 2014.

D. Suciu, D. Olteanu, C. Ré, and C. Koch, Probabilistic Databases. Morgan & Claypool (cit, vol.18, pp.145-147, 2011.

R. E. Tarjan, Depth-First Search and Linear Graph Algorithms, SIAM Journal on Computing, p.84, 1972.

R. E. Tarjan, Decomposition by Clique Separators, Discrete Mathematics, vol.55, 1985.

M. Robert-e-tarjan and . Yannakakis, Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs". In: SIAM Journal on computing, p.63, 1984.

A. Tarski, A Lattice-Theoretical Fixpoint Theorem and its Applications, In: Pacific Journal of Mathematics, p.81, 1955.

J. W. Thatcher and J. B. Wright, Generalized Finite Automata Theory with an Application to a Decision Problem of Second-Order Logic, Mathematical Systems Theory, 1968.

K. Thompson, Programming Techniques: Regular Expression Search Algorithm, Communications of the ACM, p.76, 1968.

L. G. Valiant, The Complexity of Enumeration and Reliability Problems, SIAM Journal on Computing, 1979.

M. Y. Vardi, The Complexity of Relational Query Languages". In: STOC (cit, p.57, 1982.

M. Y. Vardi, On the Complexity of Bounded-Variable Queries, PODS (cit, vol.60, p.35, 1995.

M. Vatshelle, New Width Parameters of Graphs, p.130, 2012.

M. Yannakakis, Algorithms for Acyclic Database Schemes, vol.57, p.147, 1981.