L'expressivité de SPARQL fait qu'effectivement résoudre une requête SPARQL est probablement NP-complet, oui.
Mais si on se limite à des calculs linéaires on limite fortement l'expressivité du langage et des tas de requêtes deviennent non exprimables. On va pas se limiter à du linéaire juste pour que ce soit limité, tout dépend de l'application.
[^] # Re: Euh ???
Posté par thoasm . En réponse à la dépêche SPARQL, le SQL du Web, et Linked Data Fragment : le point sur le requêtage du Web. Évalué à 3.
L'expressivité de SPARQL fait qu'effectivement résoudre une requête SPARQL est probablement NP-complet, oui.
Mais si on se limite à des calculs linéaires on limite fortement l'expressivité du langage et des tas de requêtes deviennent non exprimables. On va pas se limiter à du linéaire juste pour que ce soit limité, tout dépend de l'application.