Notes et errata postérieurs à la publication

Notes ajoutées aux publications après leur parution : erreurs dans des résultats ou des preuves, précisions sur des énoncés trompeurs, développements ultérieurs qui affectent un article, coquilles. Chaque note apparaît aussi avec son entrée dans la liste des publications, et est ajoutée au PDF hébergé sur ce site, sous la forme d'un bandeau sur la première page et d'une page à la fin.

• A. Amarilli, P. Bourhis et P. Senellart, « Tractable Lineages on Treelike Instances: Limits and Extensions ». Avril 2023. arXiv abs/1604.02761. (pdf | arXiv | bib)
  Mise à jour

  • Mise à jour 27 octobre 2026 ; Sect. 5.2, Thm. 5.5 : L'introduction et la section 5.2 présentent l'hypothèse du théorème 5.5 comme l'hypothèse du temps exponentiel non uniforme. L'hypothèse réellement utilisée dans l'énoncé, et la seule dont la preuve a besoin, est plus faible : que la hiérarchie polynomiale ne soit pas incluse dans DTIME(2^o(n))/SubEXP. La distinction importe désormais : une prépublication diffusée par OpenAI le 25 octobre 2026 affirme donner un algorithme déterministe en temps 2^o(n) pour 3-SAT, ce qui réfuterait ETH et sa version non uniforme mais laisse ouverte cette hypothèse plus faible. Les autres résultats d'intractabilité de l'article (théorèmes 4.2, 5.2 et 5.7) sont inconditionnels. Il en va de même pour la version de conférence.
• A. Amarilli, M. L. Ba, D. Deutch et P. Senellart, « Possible and Certain Answers for Queries over Order-Incomplete Data ». Proc. TIME, p. 4:1‑4:19, Mons, Belgique, octobre 2017. (pdf | version étendue | doi | bib)
  Erratum

  • Erratum 27 octobre 2026 ; Thm. 19, 22, 30 : Les théorèmes 19, 22 et 30 (possibilité en temps polynomial pour les requêtes PosRA sur les bases de po-relations non ordonnées ou de ia-largeur bornée, et possibilité et certitude pour les requêtes avec accumulation en ia-largeur bornée) ne sont pas établis, et les théorèmes 19 et 22 sont faux à moins que P = NP : la preuve de la proposition 66 de la première version arXiv échoue pour les opérateurs de produit, et le théorème 92 de la version 2 de la version étendue (janvier 2018, hébergée ici) exhibe une requête PosRA pour laquelle la possibilité est NP-complète sur des po-relations non ordonnées. Cette version retire les résultats concernés et discute l'erreur dans son annexe G ; la version de journal ne contient ni les uns ni l'autre. Voir aussi les errata d'Antoine Amarilli.
• A. Amarilli, P. Bourhis et P. Senellart, « Tractable Lineages on Treelike Instances: Limits and Extensions ». Proc. PODS, p. 355‑370, San Francisco, USA, juin 2016. (pdf | version étendue | doi | bib)
  Erratum Mise à jour

  • Erratum 27 octobre 2026 ; Thm. 5.5 : La preuve du théorème 5.5, donnée dans la thèse de doctorat d'Antoine Amarilli (théorème 6.2.5) et non dans l'article, est incorrecte : la chaîne de conseil qu'elle définit dépend de l'instance et non seulement de sa taille. Une preuve corrigée est donnée en annexe de la version 2 de la version étendue sur arXiv (avril 2023), qui est celle hébergée ici. Voir aussi les errata d'Antoine Amarilli.
  • Mise à jour 27 octobre 2026 ; Sect. 5.2, Thm. 5.5 : L'introduction et la section 5.2 présentent l'hypothèse du théorème 5.5 comme l'hypothèse du temps exponentiel non uniforme. L'hypothèse réellement utilisée dans l'énoncé, et la seule dont la preuve a besoin, est plus faible : que la hiérarchie polynomiale ne soit pas incluse dans DTIME(2^o(n))/SubEXP. La distinction importe désormais : une prépublication diffusée par OpenAI le 25 octobre 2026 affirme donner un algorithme déterministe en temps 2^o(n) pour 3-SAT, ce qui réfuterait ETH et sa version non uniforme mais laisse ouverte cette hypothèse plus faible. Les autres résultats d'intractabilité de l'article (théorèmes 4.2, 5.2 et 5.7) sont inconditionnels. Il en va de même pour la version étendue.
• M. Benedikt, G. Gottlob et P. Senellart, « Determining Relevance of Accesses at Runtime (Extended Version) ». Avril 2011. arXiv abs/1104.0553. (pdf | arXiv | bib)
  Erratum

  • Erratum 27 octobre 2026 ; Thm. 5.2, 5.6 : Comme l'explique la section sur les travaux connexes de notre article de 2020 sur Datalog monadique, deux résultats sont incorrects. La preuve de la borne inférieure co2NEXPTIME du théorème 5.6, pour l'inclusion de requêtes positives sous limitations d'accès (et donc de la 2NEXPTIME-difficulté de la pertinence à long terme pour les requêtes positives), est erronée, et cette borne est incompatible, sous les hypothèses usuelles de complexité, avec la borne supérieure 2EXPTIME prouvée ensuite par Benedikt, Bourhis et Ley (ACM TODS 2015). La preuve de la borne supérieure coNEXPTIME du théorème 5.2, pour l'inclusion de requêtes conjonctives sous limitations d'accès, ne fonctionne que pour les schémas ayant une seule méthode d'accès par relation ; le cas général est ouvert. Il en va de même pour la version de conférence.
• M. Benedikt, G. Gottlob et P. Senellart, « Determining Relevance of Accesses at Runtime ». Proc. PODS, p. 211‑222, Athens, Grèce, juin 2011. (pdf | transparents | version étendue | doi | bib)
  Erratum

  • Erratum 27 octobre 2026 ; Thm. 5.2, 5.6 : Comme l'explique la section sur les travaux connexes de notre article de 2020 sur Datalog monadique, deux résultats sont incorrects. La preuve de la borne inférieure co2NEXPTIME du théorème 5.6, pour l'inclusion de requêtes positives sous limitations d'accès (et donc de la 2NEXPTIME-difficulté de la pertinence à long terme pour les requêtes positives), est erronée, et cette borne est incompatible, sous les hypothèses usuelles de complexité, avec la borne supérieure 2EXPTIME prouvée ensuite par Benedikt, Bourhis et Ley (ACM TODS 2015). La preuve de la borne supérieure coNEXPTIME du théorème 5.2, pour l'inclusion de requêtes conjonctives sous limitations d'accès, ne fonctionne que pour les schémas ayant une seule méthode d'accès par relation ; le cas général est ouvert. Il en va de même pour la version étendue.
• G. Gottlob et P. Senellart, « Schema Mapping Discovery from Data Instances ». Journal of the ACM, vol. 57, nº 2, p. 6:1‑6:37, janvier 2010. (pdf | doi | bib)
  Erratum

  • Erratum 27 octobre 2026 ; Prop. 5.8, 5.9(5); Tables II, IV : La preuve de la proposition 5.8 est erronée (voir la note 1 de ten Cate, Kolaitis, Qian et Tan, AMW 2015), et la DP-difficulté d'Optimality énoncée dans les propositions 5.8 et 5.9(5) et dans les tables II et IV n'est pas établie. Ce qui est vrai, comme l'énonce la version de conférence, est qu'Optimality est NP-difficile et coNP-difficile, et qu'Existence-Cost est NP-difficile.

Dernière modification
2026-10-27 13:36:09 UTC