Loading...
Please wait, while we are loading the content...
Similar Documents
Abstract towards practically feasible answering of regular path queries in lav data integration.
| Content Provider | CiteSeerX |
|---|---|
| Author | Tamashiro, Manuel |
| Abstract | Regular path queries (RPQ’s) are given by means of regular expressions and ask for matching patterns on labeled graphs. RPQ’s have 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. The well-know paradigm of computing first a view-based rewriting of the query, and then evaluating the rewriting on the view extensions is indeed possible for RPQ’s. However, computing the rewriting is computationally hard as it can only be done (in the worst case) in not less than 2EXPTIME. In this paper, we provide practical evidence that computing the rewriting is hard on the average as well. On the positive side, we propose automatatheoretic techniques, which efficiently compute and utilize instead the complement of the rewriting. Notably using the latter, it is possible to answer a query, and this makes the view-based answering of RPQ’s fairly feasible in practice. 1. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | View-based Rewriting View-based Answering View Extension Automatatheoretic Technique Abstract Towards Practically Feasible Answering Practical Evidence Regular Path Query Multiple Source Well-know Paradigm Positive Side Great Attention Regular Expression Database Today Important Problem Frequent Change Labeled Graph Lav Data Integration |
| Content Type | Text |
