|
Session 6. Computational Logic
|
Aspects of dynamic complexity |
Thomas Schwentick, TU Dortmund University, Germany
|
|
|
In most real-life databases data changes frequently and thus makes
efficient query answering challenging. Auxiliary data might help to
avoid computing query answers from scratch all the time. One way to
study this incremental maintenance scenario is from the perspective
of dynamic algorithms with the goal to reduce (re-) computation
time. Another option is to investigate it from the perspective of
low-level parallel computational complexity [3] or
parallelizable database queries [2]. As the "lowest"
complexity class \( AC^0\) (with a suitable
unifomity condition) and the core of the standard database query
language SQL both coincide with first-order predicate logic, one
naturally arrives at the question which queries can be
answered/maintained dynamically with first-order predicate logic
DynFO.
The most prominent open question in Dynamic Complexity is whether
the reachability query on graphs (arguably the "simplest
recursive" query) can be maintained in
DynFO. It has been shown that it can be maintained in
DynFO on undirected [3] or
acyclic directed graphs [2] and on directed embedded
planar graphs [1], but the general case remains
open. Further results in [1] indicate that reachability
on graphs might be maintainable in DynFO,
after all.
Despite considerable effort in recent years, showing that a given
query can not be maintained in DynFO
is a very challenging problem, for which currently no methods are
available. Furthermore, even though
\(AC^0\) is a small complexity class in the static setting,
first-order logic is already quite powerful in the dynamic
world. These two observations have recently led to the study of
fragments of DynFO, e.g., by restricting or
forbidding quantification, with the idea to start developing
inexpressibility tools there. The talk will give an introduction
into dynamic complexity, survey some of its most important results,
and report about recent work on fragments of DynFO.
|
|
|
References- Samir Datta, William Hesse and Raghav Kulkarni,
Dynamic Complexity of Directed Reachability and Other
Problems , ICALP, 2014.
- Guozhu Dong and Jianwen Su, Incremental and
decremental evaluation of transitive closure by first-order
queries , Inf. Comput., 120(1):101--106, 1995.
- Sushant Patnaik and Neil Immerman,
Dyn-FO: A parallel, dynamic complexity class ,
J. Comput. Syst. Sci., 55(2):199--209, 1997.
|
|
| Print version |
|
