Full metadata record
DC FieldValueLanguage
dc.contributor.advisorGrädel, Erich-
dc.contributor.authorZeume, Thomas-
dc.date.accessioned2015-07-23T08:54:49Z-
dc.date.available2015-07-23T08:54:49Z-
dc.date.issued2015-
dc.identifier.urihttp://hdl.handle.net/2003/34163-
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-7806-
dc.description.abstractThe re-evaluation of a query result after modifying a large database can be a time-consuming process; in particular when it is performed from scratch. For this reason previously computed information such as the old query result and (possibly) other auxiliary information is often reused in order to speed up the process. In this thesis, dynamic query evaluation is studied in a descriptive complexity framework independently introduced by Dong, Su and Topor (1992, 1993) and by Patnaik and Immerman (1994). In this framework, for a relational database subject to change, auxiliary relations are maintained with the intention to help answering a query. When a modification to the database, that is, an insertion or deletion of a tuple, occurs, every auxiliary relation is updated through a first-order query that can refer to both, the database and the auxiliary relations. Our main objective is to advance the understanding of the power of the dynamic descriptive complexity framework. We contribute by (a) providing new methods for proving in-expressibility in this dynamic context, and by (b) exploring the structure of small dynamic descriptive complexity classes and their relation to static complexity classes. One of our contributions to the latter aspect helps to confirm the conjecture by Patnaik and Immerman (1997) that reachability can be maintained by first-order update formulas. This has been one of the major open questions in this area.en
dc.language.isoende
dc.subjectDynamic complexity theoryen
dc.subjectDescriptive complexityen
dc.subjectIncremental view maintenanceen
dc.subject.ddc004-
dc.titleSmall dynamic complexity classesen
dc.typeTextde
dc.contributor.refereeSchwentick, Thomas-
dc.date.accepted2015-05-11-
dc.type.publicationtypedoctoralThesisen
dcterms.accessRightsopen access-
Appears in Collections:LS 01 Logik in der Informatik

Files in This Item:
File Description SizeFormat 
Dissertation.pdfDNB1.11 MBAdobe PDFView/Open


This item is protected by original copyright



This item is protected by original copyright rightsstatements.org