ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Autres revues >>

Ingénierie des Systèmes d'Information

Networking and Information Systems
1633-1311
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 20/5 - 2015  - pp.53-75  - doi:10.3166/isi.20.5.53-75
TITRE
Possibilité pour le XML probabiliste

TITLE
Possibility in probabilistic XML

RÉSUMÉ
Nous considérons le problème de possibilité, qui consiste à déterminer si un document est un monde possible d’un document XML probabiliste. Cette question élémentaire est un cas particulier des problèmes de réponse aux requêtes ou d’évaluation d’automates d’arbres, mais elle a des applications pratiques spécifiques, comme vérifier si une issue d’un document probabiliste proposée par l’utilisateur est effectivement possible ou suffisamment probable. Ce travail s’intéresse à la complexité du problème de possibilité pour le XML probabiliste, pour des modèles d’expressivité différente. Nous montrons que le problème de décision associé peut souvent être résolu efficacement en l’absence de dépendances longuedistance, mais que le problème de calcul correspondant n’est pas faisable sur des documents non ordonnés. Nous présenterons également une version du problème avec correspondances explicites, qui couvre les situations pratiques où les étiquettes de nœuds sont non ambiguës. Cette condition garantit la faisabilité du problème de possibilité, même sous des dépendances longue-distance, du moment que les conjonctions d’événements ne sont pas permises. Nos résultats classifient intégralement la frontière entre cas faisables et infaisables, pour toutes les variantes du problème considérées.


ABSTRACT
We consider the possibility problem of determining whether a document is a possible world of a probabilistic document, in the setting of probabilistic XML. This basic question is a special case of query answering or tree automata evaluation, but it has specific practical uses, such as checking whether an user-provided probabilistic document outcome is possible or sufficiently likely. In this paper, we study the complexity of the possibility problem for probabilistic XML models of varying expressiveness. We show that the decision problem is often tractable in the absence of long-distance dependencies, but that its computation variant is intractable on unordered documents. We also introduce an explicit matches variant to generalize practical situations where node labels are unambiguous; this ensures tractability of the possibility problem, even under long-distance dependencies, provided event conjunctions are disallowed. Our results entirely classify the tractability boundary over all considered problem variants.


AUTEUR(S)
Antoine AMARILLI

MOTS-CLÉS
XML probabiliste, possibilité, probabilité, automates d’arbres, NP-complétude.

KEYWORDS
probablistic XML, possibility, probability, tree automata, NP-completeness.

LANGUE DE L'ARTICLE
Anglais

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (326 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier