Estimating the Evaluation Cost of Regular Path Queries on Large Graphs
Van-Quyet Nguyen, Kyungbaek Kim · 2017
Regular path queries (RPQs) are widely used on a graph whose answer is a set of tuples of nodes connected by paths corresponding to a given regular expression. Traditional approaches for evaluating RPQs are restricted in the explosion of graph size and/or highly complex query (e.g., nested query). Consequently, evaluating an RPQ on a large graph often takes high cost, causing substantial memory spaces and long response time. Recently, cost-based optimizations of RPQs have been proved to be effective when they are applied to large graphs. However, these techniques could not guarantee the minimum evaluation cost all the time. Therefore, estimating the evaluation cost of RPQs is an important topic which opens the way to cost-based graph query processing.