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.
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/129 |
| Date | 27 June 2007 |
| Creators | Tamashiro, Manuel |
| Contributors | Thomo, Alex, Srinivasan, Venkatesh |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.0011 seconds