The complexity of regular expressions and property paths in SPARQL.
Katja LosemannWim MartensPublished in: ACM Trans. Database Syst. (2013)
Keyphrases
- regular expressions
- query language
- rdf data
- pattern matching
- finite automata
- query evaluation
- semistructured data
- tree automata
- sparql queries
- regular languages
- xml schema
- computational complexity
- expressive power
- data model
- cost model
- linked data
- rdf graphs
- deterministic finite automata
- graph databases
- integrity constraints
- matching algorithm
- query optimization
- regular path queries
- conjunctive regular path queries