4 ms·
SPARQL is PSPACE-complete. Worst case complexity and "fast in practice" aren't really the same thing at all. I suspect average case complexity for SPARQL is muc
by kendallgclark 12y ago
SPARQL is PSPACE-complete. Worst case complexity and "fast in practice" aren't really the same thing at all. I suspect average case complexity for SPARQL is much better, which is backed up by several reasonably peformant implementations.
- rspeer 12y agoWhat are these reasonably performant implementations? Have you tried them with a billion edges? Also, if your data store is "fast in practice" but has worst cases that are PSPACE-complete, how do you prevent worst-case queries from DOSing it?
- kendallgclark 12y agoWell, I'm a vendor in the space so I like my implementation: http://stardog.com/ http://stardog.com/ -- and yes we've "tried it" with 10s of billions of edges. Worst cases are prevented from DOSing by having query management features like auto-killing queries that run too long, etc.