Relational queries computable in polynomial time
From MaRDI portal
Publication:3753525
DOI10.1016/S0019-9958(86)80029-8zbMath0612.68086MaRDI QIDQ3753525
Publication date: 1986
Published in: Information and Control (Search for Journal in Brave)
relational calculus; finite model theory; least fixed point operator; polynomial time computable queries; fixed point query hierarchy
Related Items
On fixed-point logic with counting, The dimension of the negation of transitive closure, Tailoring recursion for complexity, The expressive power of fixed-point logic with counting, On the expressive power of counting, Computing with infinitary logic, A simple proof on the decidability of equivalence between recursive and nonrecursive Datalog programs, On the equivalence of recursive and nonrecursive Datalog programs, The alternating fixpoint of logic programs with negation, Finite-model theory -- A personal perspective, A closed-form evaluation for Datalog queries with integer (gap)-order constraints, Circumscribing DATALOG: expressive power and complexity, Arithmetizing uniform \(NC\), Datalog extensions for database queries and updates, Why not negation by fixpoint?, On the expressive power of database queries with intermediate types, A comparison between algebraic query languages for flat and nested databases, An analysis of fixed-point queries on binary trees, The expressive power of the bounded-iteration construct, The invariant problem for binary string structures and the parallel complexity theory of queries, Capturing complexity classes by fragments of second-order logic, Infinitary logics and 0-1 laws, Bounded linear logic: A modular approach to polynomial-time computability, The parallel complexity of single rule logic programs, An optimal lower bound on the number of variables for graph identification, Permutation dependency in datalog programs, On winning strategies in Ehrenfeucht-Fraïssé games, An extension of fixpoint logic with a symmetry-based choice construct, Reflective relational machines, A restricted second order logic for finite structures, Semantics and expressiveness issues in active databases, The expressive power of stratified logic programs with value invention, Positive versions of polynomial time, Hereditarily-finite sets, data bases and polynomial-time computability, Context-sensitive transitive closure operators, Non-determinism in logic-based languages, Canonization for two variables and puzzles on the square, How to define a linear order on finite models, Finitely representable databases, A query language for NC, Using automata theory for characterizing the semantics of terminological cycles, Polynomial-time computable stable models, Metafinite model theory, A probabilistic view of Datalog parallelization, \(\Delta\)-languages for sets and LOGSPACE computable graph transformers, Bounded fixpoints for complex objects, Games and total Datalog\(^{\lnot}\) queries, Generalized quantifiers and pebble games on finite structures, Directions in generalized quantifier theory, Hierarchies in transitive closure logic, stratified Datalog and infinitary logic, Complexity and undecidability results for logic programming, Linear ordering on graphs, anti-founded sets and polynomial time computability, Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus, Almost Everywhere Equivalence of Logics in Finite Model Theory, Finite Variable Logics in Descriptive Complexity Theory
