


Abstract:


"Comparison of XPath Containment Algorithms", (2007)

Guerra, J., Useche, L., Rivero, M., Syed, I., Orelus H., Adjouadi, M., Barreto, A., Stoute B., Graham, S., and Rishe, N. 

ABSTRACT: The complexity of implementing a sound, complete and efficient algorithm to detect containment (and by extension equivalence) in XPath fragments has frustrated previous attempts by computer scientists. Some algorithms have been developed to deal with these problems but these have lacked either in completeness, efficiency, or soundness, working only when restrictions in the type of XPath fragments are enforced.
In this paper we will attempt to evaluate a prominent algorithm in terms of time for different inputs. These inputs try to explore different behaviors of the algorithm such as: the most influential construct for the running time, the behavior of the algorithm in common cases. And the response time of the algorithm for the worst case, which covers the whole tree. We present experiments that allow us to determine the behavior of the algorithm and evaluate it via each of the above questions.



