Certain Answers and Rewritings for Local Regular Path Queries on Graph-Structured Data

被引：1

作者：

Shoaran, Maryam ^{[1
]}

Thomo, Alex ^{[1
]}

机构：

[1] Univ Victoria, Victoria, BC, Canada

来源：

PROCEEDINGS OF THE FOURTEENTH INTERNATIONAL DATABASE ENGINEERING & APPLICATIONS SYMPOSIUM (IDEAS '10) | 2010年

关键词：

Regular path queries; Graph-structured databases; Views; Rewritings; Algorithms; Theory; Performance; CONSTRAINTS;

D O I：

10.1145/1866480.1866507

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper we explore the connection between certain answers and view-based rewritings for local regular path queries (RPQs) which are regular expressions matching paths in graph-structured data starting from a specific node. We show that differently from the case of global RPQs, which match paths starting from any node, the notions of certain answer and rewriting-based answer coincide for local RPQs. The importance of this result is that obtaining the certain answer for local RPQs can be done in polynomial time in the size of the data. We also present an automata-theoretic algorithm for computing maximal view-based rewritings. Notably, these rewritings are an exponential order of magnitude smaller than their counterparts for global RPQs.

引用

页码：186 / 192

页数：7

共 26 条

[11]

CONSENS MP, 1990, PROCEEDINGS OF THE NINTH ACM SIGACT-SIGMOD-SIGART SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS, P404, DOI 10.1145/298514.298591

[12] Algebraic rewritings for optimizing regular path queries [J].

Grahne, G ;

Thomo, A .

THEORETICAL COMPUTER SCIENCE, 2003, 296 (03) :453-471

[13]

Grahne G, 2003, LECT NOTES COMPUT SC, V2572, P242

[14]

Grahne G., 2003, PODS, P111

[15]

Grahne G., 2009, Encyclopedia of Database Systems, P315

[16]

Hurtado CA, 2009, LECT NOTES COMPUT SC, V5554, P263, DOI 10.1007/978-3-642-02121-3_22

[17]

Kochut KJ, 2007, LECT NOTES COMPUT SC, V4519, P145

[18]

Lakshmanan LaksV. S., 2006, VLDB, P571

[19]

Lenzerini Maurizio, 2002, PODS, DOI DOI 10.1145/543613.543644

[20] FINDING REGULAR SIMPLE PATHS IN GRAPH DATABASES [J].

MENDELZON, AO ;

WOOD, PT .

SIAM JOURNAL ON COMPUTING, 1995, 24 (06) :1235-1258

← 1 2 3 →