Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
From MaRDI portal
Publication:1278038
DOI10.1006/jcss.1998.1565zbMath0936.68029OpenAlexW1980634162MaRDI QIDQ1278038
Publication date: 21 February 1999
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/e4402af68f3a2189105ef99f5da89f9ccda53b02
Related Items (8)
Dynamic conjunctive queries ⋮ SEPARATING AUXILIARY ARITY HIERARCHY OF FIRST-ORDER INCREMENTAL EVALUATION SYSTEMS USING (3K+1)-ary INPUT RELATIONS ⋮ Reachability is in DynFO ⋮ The dynamic descriptive complexity of \(k\)-clique ⋮ Incremental recomputation in local languages. ⋮ Unnamed Item ⋮ On the quantifier-free dynamic complexity of reachability ⋮ Maintenance of datalog materialisations revisited
Cites Work
- Unnamed Item
- Maintaining transitive closure in first order after node-set and edge-set deletions
- Lower bounds for constant-depth circuits in the presence of help bits
- Determining uni-connectivity in directed graphs
- Complexity models for incremental computation
- Deterministic FOIES are strictly weaker
- Finitely representable databases
- Structure and complexity of relational queries
- On monadic NP vs monadic co-NP
- Incremental and decremental evaluation of transitive closure by first- order queries
- Nonrecursive incremental evaluation of Datalog queries
- An application of games to the completeness problem for formalized theories
- Reachability is harder for directed than for undirected finite graphs
- Relative Information Capacity of Simple Relational Database Schemata
- Monadic generalized spectra
This page was built for publication: Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
