On the expressive power of Datalog: tools and a case study.
From MaRDI portal
Publication:960526
DOI10.1006/jcss.1995.1055zbMath1360.68397OpenAlexW4212857488MaRDI QIDQ960526
Moshe Y. Vardi, Phokion G. Kolaitis
Publication date: 21 December 2008
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1995.1055
Database theory (68P15) Logic in computer science (03B70) Model theory of finite structures (03C13) Logic programming (68N17)
Related Items (17)
On Monotonic Determinacy and Rewritability for Recursive Queries and Views ⋮ Semantic Acyclicity on Graph Databases ⋮ How to define a linear order on finite models ⋮ On the speed of constraint propagation and the time complexity of arc consistency testing ⋮ A More General Theory of Static Approximations for Conjunctive Queries ⋮ Arboreal Categories: An Axiomatic Theory of Resources ⋮ On digraph coloring problems and treewidth duality ⋮ On the Decision Problem for Two-Variable First-Order Logic ⋮ A combinatorial characterization of resolution width ⋮ Inherent complexity of recursive queries ⋮ Universal algebra and hardness results for constraint satisfaction problems ⋮ Expressive power and complexity of partial models for disjunctive deductive databases ⋮ OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT ⋮ How many variables are needed to express an existential positive query? ⋮ A more general theory of static approximations for conjunctive queries ⋮ Dualities for Constraint Satisfaction Problems ⋮ Conjunctive-query containment and constraint satisfaction
This page was built for publication: On the expressive power of Datalog: tools and a case study.
