Incremental and decremental evaluation of transitive closure by first- order queries

DOI10.1006/INCO.1995.1102MaRDI QIDQ1898482zbMATHOpenAlexFDO

Authors Guozhu Dong, Jianwen Su

Publication date 17 September 1995

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/inco.1995.1102

zbMATH Keywords

transitive closurefirst-order queries

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Database theory (68P15)

Recommendations

• scientific article; zbMATH DE number 1953132
• On the decidability of termination of query evaluation in transitive-closure logics for polynomial constraint databases
• Nonrecursive incremental evaluation of Datalog queries
• Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
• An experimental study of dynamic algorithms for transitive closure
• An experimental study of algorithms for fully dynamic transitive closure

Cited in

(12)

• The dynamic complexity of transitive closure is in DynTC\(^{0}\).
• Reachability is in DynFO
• Maintaining transitive closure in first order after node-set and edge-set deletions
• Dyn-FO: A parallel, dynamic complexity class
• Dynamic complexity of the Dyck reachability
• Irrelevant updates and self-maintainability in transitive closure database views
• Incremental recomputation in local languages.
• Maintenance of datalog materialisations revisited
• Incremental Event Calculus for Run-Time Reasoning
• Local properties of query languages
• Arity bounds in first-order incremental evaluation and definition of polynomial time database queries
• SEPARATING AUXILIARY ARITY HIERARCHY OF FIRST-ORDER INCREMENTAL EVALUATION SYSTEMS USING (3K+1)-ary INPUT RELATIONS

This page was built for publication: Incremental and decremental evaluation of transitive closure by first- order queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1898482)