Finding regular simple paths in graph databases

Simple item page
dc.contributor.authorMendelzon, Alberto O
dc.contributor.authorWood, Peter T
dc.date.accessioned2021-10-08T07:16:03Z
dc.date.available2021-10-08T07:16:03Z
dc.date.issued1995
dc.description.abstractWe consider the following problem : given a labelled directed graph G and a regular expression R, find all pairs of nodes connected by a simple path such that the concatenation of the labels along the path satisfies R. The problem is motivated by the observation that many recursive queries in relational databases can be expressed in this form, and by the implementation of query language, G+, based on this observation. We show that the problem is in general intractable, but present an algorithm than runs in polynomial time in the size of the graph when the regular expression and the graph are free of conflicts. We also present a class of languages whose expressions can always be evaluated in time polynomial in the size of both the graph and the expression, and characterize syntactically the expressions for such languages.
dc.identifier.apacitationMendelzon, A. O., & Wood, P. T. (1995). Finding regular simple paths in graph databases. <i>SIAM Journal on Computing</i>, 24(6), 1235 - 1258. http://hdl.handle.net/11427/34758en_ZA
dc.identifier.chicagocitationMendelzon, Alberto O, and Peter T Wood "Finding regular simple paths in graph databases." <i>SIAM Journal on Computing</i> 24, 6. (1995): 1235 - 1258. http://hdl.handle.net/11427/34758en_ZA
dc.identifier.citationMendelzon, A.O. & Wood, P.T. 1995. Finding regular simple paths in graph databases. <i>SIAM Journal on Computing.</i> 24(6):1235 - 1258. http://hdl.handle.net/11427/34758en_ZA
dc.identifier.issn0097-5397
dc.identifier.issn1095-7111
dc.identifier.ris TY - Journal Article AU - Mendelzon, Alberto O AU - Wood, Peter T AB - We consider the following problem : given a labelled directed graph G and a regular expression R, find all pairs of nodes connected by a simple path such that the concatenation of the labels along the path satisfies R. The problem is motivated by the observation that many recursive queries in relational databases can be expressed in this form, and by the implementation of query language, G+, based on this observation. We show that the problem is in general intractable, but present an algorithm than runs in polynomial time in the size of the graph when the regular expression and the graph are free of conflicts. We also present a class of languages whose expressions can always be evaluated in time polynomial in the size of both the graph and the expression, and characterize syntactically the expressions for such languages. DA - 1995 DB - OpenUCT DP - University of Cape Town IS - 6 J1 - SIAM Journal on Computing LK - https://open.uct.ac.za PY - 1995 SM - 0097-5397 SM - 1095-7111 T1 - Finding regular simple paths in graph databases TI - Finding regular simple paths in graph databases UR - http://hdl.handle.net/11427/34758 ER - en_ZA
dc.identifier.urihttp://hdl.handle.net/11427/34758
dc.identifier.vancouvercitationMendelzon AO, Wood PT. Finding regular simple paths in graph databases. SIAM Journal on Computing. 1995;24(6):1235 - 1258. http://hdl.handle.net/11427/34758.en_ZA
dc.language.isoeng
dc.publisher.departmentDepartment of Computer Science
dc.publisher.facultyFaculty of Science
dc.sourceSIAM Journal on Computing
dc.source.journalissue6
dc.source.journalvolume24
dc.source.pagination1235 - 1258
dc.source.urihttps://dx.doi.org/10.1137/S009753979122370X
dc.subject.otherGraph theory
dc.subject.otherAlgorithms
dc.subject.otherRelational database systems
dc.subject.otherQuery languages
dc.subject.otherDirected graph
dc.subject.otherLabelled graph
dc.subject.otherGraph path
dc.subject.otherSearch algorithm
dc.subject.otherRecursive method
dc.subject.otherRegular expression
dc.subject.otherThéorie graphe
dc.subject.otherAlgorithme
dc.subject.otherSystème base donnée relationnelle
dc.subject.otherLangage interrogation
dc.subject.otherGraphe orienté
dc.subject.otherGraphe marqué
dc.subject.otherChemin graphe
dc.subject.otherAlgorithme recherche
dc.subject.otherMéthode récursive
dc.subject.otherExpression régulière
dc.subject.otherGraphe sans conflit
dc.titleFinding regular simple paths in graph databases
dc.typeJournal Article
uct.type.publicationResearch
uct.type.resourceJournal Article
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
MendelzonAlbertoO_Finding_regular_1995.pdf
Size:
234.65 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Journal Articles