Size and treewidth bounds for conjunctive queries

No abstract is available for this paper.

• Publication year

  2009

• Venue

  ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

• Publication date

  2009-06-29

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1559795.1559804
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Graph Minors

  2009cited by this paper
• Size Bounds for Conjunctive Queries with General Functional Dependencies

  2009cited by this paper
• Information Theory and Network Coding

  2008cited by this paper
• Size Bounds and Query Plans for Relational Joins

  2008influential reference
• Networks, Matroids, and Non-Shannon Information Inequalities

  2007cited by this paper
• Infinitely Many Information Inequalities

  2007cited by this paper
• Efficient Datalog Abduction through Bounded Treewidth

  2007cited by this paper
• Two Constructions on Limits of Entropy Functions

  2007cited by this paper
• A logical approach to multicut problems

  2007cited by this paper
• Constraint solving via fractional edge covers

  2006influential reference
• Query reformulation with constraints

  2006cited by this paper
• Schema mappings, data exchange, and metadata management

  2005cited by this paper
• Data exchange: semantics and query answering

  2003cited by this paper
• Data integration: a theoretical perspective

  2002cited by this paper
• Query evaluation via tree-decompositions

  2001cited by this paper
• Answering Queries Using Views.

  1999cited by this paper
• An overview of query optimization in relational systems

  1998cited by this paper
• All Structured Programs have Small Tree-Width and Good Register Allocation

  1998cited by this paper
• On characterization of entropy function via information inequalities

  1998cited by this paper
• A non-Shannon-type conditional inequality of information quantities

  1997cited by this paper
• Structured Programs have Small Tree-Width and Good Register Allocation (Extended Abstract)

  1997cited by this paper
• Selectivity and Cost Estimation for Joins Based on Random Sampling

  1996cited by this paper
• The Monadic Second-order Logic of Graphs VI: On Several Representations of Graphs by Relational Structures

  1995cited by this paper
• Foundations of Databases

  1994cited by this paper
• On the Estimation of Join Result Sizes

  1994cited by this paper
• Easy Problems for Tree-Decomposable Graphs

  1991cited by this paper
• The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs

  1990cited by this paper
• Random Sampling from Database Files: A Survey

  1990cited by this paper
• Graph minors. V. Excluding a planar graph

  1986cited by this paper
• Graph Minors. II. Algorithmic Aspects of Tree-Width

  1986cited by this paper
• Query Optimization in Database Systems

  1984cited by this paper
• A Proof Procedure for Data Dependencies

  1984cited by this paper
• Linear-Time Algorithms for Testing the Satisfiability of Propositional Horn Formulae

  1984cited by this paper
• How to share a secret

  1979cited by this paper
• Testing implications of data dependencies

  1979influential reference
• Equivalences Among Relational Expressions

  1979cited by this paper
• Optimal implementation of conjunctive queries in relational data bases

  1977cited by this paper
• The theory of joins in relational data bases

  1977cited by this paper

• PANDAExpress: a Simpler and Faster PANDA Algorithm

  2025cites this paper
• Quantum Information-Theoretical Size Bounds for Conjunctive Queries with Functional Dependencies

  2025cites this paper
• Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins

  2025cites this paper
• Ambidextrous Degree Sequence Bounds for Pessimistic Cardinality Estimation

  2025cites this paper
• Intermediate Relation Size Bounds for Select-Project-Join-Union Query Plans

  2024influential citation
• PANDA: Query Evaluation in Submodular Width

  2024cites this paper
• Intermediate Relation Size Bounds for Select-Project-Join Query Plans: Asymptotically Tight Characterizations

  2024cites this paper
• The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product Problems

  2023cites this paper
• PostBOUND: PostgreSQL with Upper Bound SPJ Query Optimization

  2023cites this paper
• Join Size Bounds using ℓ 𝑝 -Norms on Degree Sequences

  2023cites this paper
• Information inequality problem over set functions

  2023cites this paper
• Size Bounds and Algorithms for Conjunctive Regular Path Queries

  2023influential citation
• ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning

  2023cites this paper
• Applications of Information Inequalities to Database Theory Problems

  2023cites this paper
• Degree Sequence Bound For Join Cardinality Estimation

  2022cites this paper
• Optimising Sargable Conjunctive Predicate Queries in the Context of Big Data

  2022cites this paper
• Synergy between Quantum Computers and Databases

  2022cites this paper
• Any-k Algorithms for Enumerating Ranked Answers to Conjunctive Queries

  2022cites this paper
• Cross-Model Conjunctive Queries over Relation and Tree-structured Data (Extended)

  2022influential citation
• On an Information Theoretic Approach to Cardinality Estimation (Invited Talk)

  2022cites this paper
• Optimal Joins Using Compressed Quadtrees

  2022cites this paper
• Query Evaluation by Circuits

  2022influential citation
• SafeBound: A Practical System for Generating Cardinality Bounds

  2022cites this paper
• A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries

  2021cites this paper
• Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs

  2021cites this paper
• RECENT RESULTS ON CARDINALITY ESTIMATION AND INFORMATION THEORETIC INEQUALITIES

  2021cites this paper
• Join Cardinality Estimation Graphs: Analyzing Pessimistic and Optimistic Estimators Through a Common Lens

  2020cites this paper
• Querying APIs With SPARQL

  2020cites this paper
• Decision Problems in Information Theory

  2020cites this paper
• Optimal Join Algorithms Meet Top-k

  2020cites this paper
• Domain Ordering and Box Cover Problems for Beyond Worst-Case Join Processing

  2019cites this paper
• Bag Query Containment and Information Theory

  2019cites this paper
• Bag Query Containment and Information Theory

  2019cites this paper
• Box Covers and Domain Orderings for Beyond Worst-Case Join Processing

  2019cites this paper
• Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries

  2019cites this paper
• Worst-Case Optimal Radix Triejoin

  2019cites this paper
• Semantic Width of Conjunctive Queries and Constraint Satisfaction Problems

  2018cites this paper
• Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems

  2018influential citation
• Structural Decomposition Methods: Key Notions and Database Applications

  2018cites this paper
• Querying APIs with SPARQL: Language and Worst-Case Optimal Algorithms

  2018cites this paper
• From Hypertree Width to Submodular Width and Data-dependent Structural Decompositions

  2018cites this paper
• Answering UCQs under updates and in the presence of integrity constraints

  2017cites this paper
• A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries

  2017cites this paper
• Méthodes hybrides parallèles pour la résolution de problèmes d'optimisation combinatoire : application au clustering sous contraintes. (Parallel hybrid methods for solving combinatorial optimization problems : application to clustering under constraints)

  2017cites this paper
• Defining the almost-entropic regions by algebraic inequalities

  2017influential citation
• Computing Join Queries with Functional Dependencies

  2016influential citation
• ScaLeKB: scalable learning and inference over large knowledge bases

  2016cites this paper
• Constraint satisfaction: algorithms, complexity results, and applications

  2016cites this paper
• Hypertree Decompositions: Questions and Answers

  2016cites this paper
• What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another?

  2016cites this paper
• What do Shannon information inequalities , submodular width , and disjunctive datalog have to do with one another ?

  2016cites this paper
• The almost-entropic regions are not semialgebraic

  2015cites this paper
• Querying Big Data by Accessing Small Data

  2015influential citation
• Entropy Bounds for Conjunctive Queries with Functional Dependencies

  2015cites this paper
• Explorer Querying Big Data by Accessing Small Data

  2015cites this paper
• Bounded Conjunctive Queries

  2014cites this paper
• Constraint Solving via Fractional Edge Covers

  2014cites this paper
• Network coding and the model theory of linear information inequalities

  2014cites this paper
• Counting solutions to conjunctive queries: structural and hybrid tractability

  2014cites this paper
• Cooperative Parallel Decomposition Guided VNS for Solving Weighted CSP

  2014cites this paper
• Skew strikes back: new developments in the theory of join algorithms

  2013cites this paper
• Raffinement de décompositions arborescentes par fusion de clusters pour guider DGVNS

  2013cites this paper
• Exploiting Tree Decomposition for Guiding Neighborhoods Exploration for VNS

  2013cites this paper
• DGVNS guidée par les séparateurs

  2013cites this paper
• Intensification/Diversification in Decomposition Guided VNS

  2013cites this paper
• Bounds and Algorithms for Joins via Fractional Edge Covers

  2013influential citation
• Size and Treewidth Bounds for Conjunctive Queries

  2012cites this paper
• Factorised Representations of Query Results

  2011cites this paper
• Size Bounds for Conjunctive Queries with General Functional Dependencies

  2009cites this paper
• Size Bounds and Query Plans for Relational Joins

  2008cites this paper
• Testing symmetric properties of distributions

  2008cites this paper
• TreeTracker Join: A Composable Join Algorithm that Yields Optimal Acyclic Multi-Way Joins

  year unknowncites this paper
• TreeTracker Join: Killing Two Birds With One Stone

  year unknowncites this paper
• Pessimistic Cardinality Estimation ⇤

  year unknowncites this paper