How many variables are needed to express an existential positive query?

DOI10.1007/s00224-018-9884-zzbMath1430.68079OpenAlexW2888967524MaRDI QIDQ2322719

Hubie Chen, Simone Bova

Publication date: 5 September 2019

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7054/

zbMATH Keywords

first-order logicquery optimizationfinite-variable logicsexistential positive queries

Mathematics Subject Classification ID

Database theory (68P15) Logic in computer science (03B70)

Cites Work

• Unnamed Item
• The core of a graph
• On the expressive power of Datalog: tools and a case study.
• Upper and lower bounds for first order expressibility
• Graph Theory
• Tree-width for first order formulae
• Beyond Q-Resolution and Prenex Form: A Proof System for Quantified Constraint Satisfaction
• How many variables are needed to express an existential positive query
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• On Moschovakis closure ordinals
• The tractability frontier of graph-like first-order query sets
• One hierarchy spawns another
• Computer Science Logic
• On the complexity of existential positive queries
• On the Power of k-Consistency