Back to search

University of Victoria (Canada)

Towards practically feasible answering of regular path queries in LAV data integration

Abstract

dc:description.abstract

Regular path queries (RPQ’s) are given by means of regular expressions and ask for matching patterns on labeled graphs. RPQ’s have recently received great attention in the context of semistructured data, which are data whose structure is irregular, partially known, or subject to frequent changes. One of the most important problems in databases today is the integration of semistructured data from multiple sources modeled as views. In this setting, the database is not available, and given a user query, the system has to answer based solely on the information provided by the views. The problem is computationally hard, and the well-known algorithm for solving it runs in 2EXPTIME. In this paper, we provide practical evidence that this algorithm performs poorly on the average as well. Then, we propose automata- theoretic techniques which make the view-based answering of RPQ’s more feasible in practice.

Degree

thesis:*
Level thesis:degree_level
Master of Science M.Sc.
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
2007

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Tamashiro, Manuel
Advisors dc:contributor.supervisor
  • Thomo, Alex
  • Srinivasan, Venkatesh

Subjects

dc:subject × 5

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web
Language dc:language.iso
en, English

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1828/129

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Tamashiro, Manuel. Towards practically feasible answering of regular path queries in LAV data integration. Master of Science M.Sc. thesis, 2007. http://hdl.handle.net/1828/129