Edinburgh Research Explorer

Query Optimization for Semistructured Data using Path Constraints in a Deterministic Data Model

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://link.springer.com/chapter/10.1007%2F3-540-44543-9_13
Original languageEnglish
Title of host publicationResearch Issues in Structured and Semistructured Database Programming
Subtitle of host publication7th International Workshop on Database Programming Languages, DBPL’99 Kinloch Rannoch, UK, September 1–3,1999 Revised Papers
PublisherSpringer-Verlag GmbH
Pages208-223
Number of pages16
ISBN (Electronic)978-3-540-44543-2
ISBN (Print)978-3-540-41481-0
DOIs
Publication statusPublished - 1999

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
Volume1949
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Abstract

Path constraints have been studied for semistructured data modeled as a rooted edge-labeled directed graph [4], [11]-[13]. In this model, the implication problems associated with many natural path constraints are undecidable [11], [13]. A variant of the graph model, called the deter- ministic data model, was recently proposed in [10]. In this model, data is represented as a graph with deterministic edge relations, i.e., the edges emanating from any node in the graph have distinct labels. This model is more appropriate for representing, e.g., ACeDB [27] databases and Web sites. This paper investigates path constraints for the deterministic data model. It demonstrates the application of path constraints to, among others, query optimization. Three classes of path constraints are considered: the language Pc introduced in [11], an extension of Pc , denoted by Pcw , by including wildcards in path expressions, and a generalization of Pcw , denoted by Pc* , by representing paths as regular expressions. The implication problems for these constraint languages are studied in the context of the deterministic data model. It is shown that in contrast to the undecidability result of [11], the implication and finite implication problems for Pc are decidable in cubic-time and are finitely axiomatizable. Moreover, the implication problems are decidable for Pcw . However, the implication problems for Pc* are undecidable.

Download statistics

No data available

ID: 10624623