A closed-form evaluation for Datalog queries with integer (gap)-order constraints

DOI10.1016/0304-3975(93)90222-FzbMath0785.68026OpenAlexW2022530540WikidataQ57641771 ScholiaQ57641771MaRDI QIDQ688670

Peter Z. Revesz

Publication date: 17 April 1994

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90222-f

zbMATH Keywords

datalogquantifier eliminationrecursionmodel theorydata complexityclosed formbottom-up evaluationconstraint query languagesgap-order constraintsgeneralized database

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Computable structure theory, computable model theory (03C57)

Related Items (17)

Verification of Gap-Order Constraint Abstractions of Counter Systems ⋮ Constraint Answer Set Programming without Grounding ⋮ The complexity of query evaluation in indefinite temporal constraint databases ⋮ Interprocedural Reachability for Flat Integer Programs ⋮ Queries with arithmetical constraints ⋮ Monotonic Abstraction for Programs with Dynamic Memory Heaps ⋮ Early detection of temporal constraint violations ⋮ Verification of gap-order constraint abstractions of counter systems ⋮ First-order rewritability of ontology-mediated queries in linear temporal logic ⋮ Estimating the maximum rise in temperature according to climate models using abstract interpretation ⋮ Handling Parameterized Systems with Non-atomic Global Conditions ⋮ A technique for proving decidability of containment and equivalence of linear constraint queries ⋮ Constraint-generating dependencies ⋮ Monotonic Abstraction in Parameterized Verification ⋮ Approximated parameterized verification of infinite-state processes with global conditions ⋮ Data Multi-Pushdown Automata ⋮ Monotonic Abstraction in Action

Uses Software

• CHIP
• Datalog

Cites Work

• The method of forced enumeration for nondeterministic automata
• Parallel complexity of logical query programs
• On the relationship of congruence closure and unification
• Computable queries for relational data bases
• Elementary induction on abstract structures
• An efficient decision procedure for the theory of rational order
• The computational complexity of logical theories
• Domain independence and the relational calculus
• Handling infinite temporal data
• General recursive functions of natural numbers
• Horn clause queries and generalizations
• Relational queries computable in polynomial time
• Nondeterministic Space is Closed under Complementation
• A relational model of data for large shared data banks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A closed-form evaluation for Datalog queries with integer (gap)-order constraints