University of Victoria (Canada)
Towards practically feasible answering of regular path queries in LAV data integration
Abstract
dc:description.abstractRegular 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 × 5Rights
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