Simulation Subsumption or Déjà vu on the Web

Bry, François; Furche, Tim and Linse, Benedikt (2008): Simulation Subsumption or Déjà vu on the Web. Second International Conference, RR 2008, Karlsruhe, Deutschland, 31. Oktober - 1. November 2008. Calvanese, Diego (ed.) : In: Web Reasoning and Rule Systems : Second International Conference, RR 2008, Karlsruhe, Germany, October 31-November 1, 2008. Proceedings, Berlin u.a.: Springer. pp. 28-42

Abstract

Simulation unification is a special kind of unification adapted to retrieving semi-structured data on the Web. This article introduces simulation subsumption, or containment, that is, query subsumption under simulation unification. Simulation subsumption is crucial in general for query optimization, in particular for optimizing pattern-based search engines, and for the termination of recursive rule-based web languages such as the XML and RDF query language Xcerpt. This paper first motivates and formalizes simulation subsumption. Then, it establishes decidability of simulation subsumption for advanced query patterns featuring descendant constructs, regular expressions, negative subterms (or subterm exclusions), and multiple variable occurrences. Finally, we show that subsumption between two query terms can be decided in O(n!n) where n is the sum of the sizes of both query terms.

• Item Type: Conference or Workshop Item (Paper)
• Form of publication: Postprint
• Faculties: Mathematics, Computer Science and Statistics > Computer Science
• Subjects: 000 Computer science, information and general works > 004 Data processing computer science
• Place of Publication: Berlin u.a.
• Annotation: The final publication is available at link.springer.com
• Language: English