Querying Regular Graph Patterns

Simple item page
dc.contributor.authorBarcelo, Pablo
dc.contributor.authorLibkin, Leonid
dc.contributor.authorReutter, Juan L.
dc.date.accessioned2025-01-23T21:48:50Z
dc.date.available2025-01-23T21:48:50Z
dc.date.issued2014
dc.description.abstractGraph data appears in a variety of application domains, and many uses of it, such as querying, matching, and transforming data, naturally result in incompletely specified graph data, that is, graph patterns. While queries need to be posed against such data, techniques for querying patterns are generally lacking, and properties of such queries are not well understood.
dc.description.abstractOur goal is to study the basics of querying graph patterns. The key features of patterns we consider here are node and label variables and edges specified by regular expressions. We provide a classification of patterns, and study standard graph queries on graph patterns. We give precise characterizations of both data and combined complexity for each class of patterns. If complexity is high, we do further analysis of features that lead to intractability, as well as lower-complexity restrictions. Since our patterns are based on regular expressions, query answering for them can be captured by a new automata model. These automata have two modes of acceptance: one captures queries returning nodes, and the other queries returning paths. We study properties of such automata, and the key computational tasks associated with them. Finally, we provide additional restrictions for tractability, and show that some intractable cases can be naturally cast as instances of constraint satisfaction problems.
dc.fuente.origenWOS
dc.identifier.doi10.1145/2559905
dc.identifier.eissn1557-735X
dc.identifier.issn0004-5411
dc.identifier.urihttps://doi.org/10.1145/2559905
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/101765
dc.identifier.wosidWOS:000331466500008
dc.issue.numero1
dc.language.isoen
dc.revistaJournal of the acm
dc.rightsacceso restringido
dc.subjectAlgorithms
dc.subjectLanguages
dc.subjectTheory
dc.subjectGraph databases
dc.subjectgraph patterns
dc.subjectquery languages
dc.subjectcomplexity
dc.subjectautomata
dc.subjectconstraint satisfaction
dc.titleQuerying Regular Graph Patterns
dc.typeartículo
dc.volumen61
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Collections
Artículos de revistas