Efficient evaluation for a temporal logic on changing XML documents
Conference object, Article
Bojańczyk , Mikołaj
Figueira , Diego
- Publisher: ACM Press
Algorithms | Languages | Keywords | temporal logic | Query languages | General Terms | poral logic | F41 [Mathematical logic and formal languages]: Tem- | [ INFO.INFO-LO ] Computer Science [cs]/Logic in Computer Science [cs.LO] | H23 [Database management]: Languages— | Incremental evaluation | [ INFO.INFO-DB ] Computer Science [cs]/Databases [cs.DB] | XML | Theory
International audience; We consider a sequence t1,. .. , tk of XML documents that is produced by a sequence of local edit operations. To describe properties of such a sequence, we use a temporal logic. The logic can navigate both in time and in the document, e.g. a formula can say that every node with label a eventually gets a descendant with label b. For every fixed formula, we provide an evaluation algorithm that works in time O(k·log(n)), where k is the number of edit operations and n is the maximal size of document that is produced. In the algorithm, we represent formulas of the logic by a kind of automaton, which works on sequences of documents. The algorithm works on XML documents of bounded depth.