LSV Seminar

Date

Tuesday, November 18 2014 at 11:00AM

Place

Salle de Conférence (Pavillon des Jardins)

Speaker

Thomas Schwentick (TU Dortmund)

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 [1] 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 intensely investigated query in Dynamic Complexity is the reachability query on graphs (arguably the "simplest recursive" query). It has been shown that it can be maintained in DynFO on undirected [1] or acyclic directed graphs [2] and on directed embedded planar graphs [3]. Recently it could be shown that it can be maintained in DynFO, for the class of all directed graphs.

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.

[1] Sushant Patnaik and Neil Immerman. Dyn-FO: A parallel, dynamic complexity class. J. Comput. Syst. Sci., 55(2):199--209, 1997.

[2] Guozhu Dong and Jianwen Su. Incremental and decremental evaluation of transitive closure by first-order queries. Inf. Comput., 120(1):101--106, 1995.

[3] Samir Datta, William Hesse and Raghav Kulkarni. Dynamic Complexity of Directed Reachability and Other Problems. ICALP 2014.