PXML: a probabilistic semistructured data model and algebra

TitlePXML: a probabilistic semistructured data model and algebra
Publication TypeConference Papers
Year of Publication2003
AuthorsHung E, Getoor L, V.S. Subrahmanian
Conference NameData Engineering, 2003. Proceedings. 19th International Conference on
Date Published2003/03//
Keywordsalgebra;, data, databases;, instances;, model;, models;, probabilistic, processing;, PXML;, query, relational, semistructured, structures;, tree, XML;

Despite the recent proliferation of work on semistructured data models, there has been little work to date on supporting uncertainty in these models. We propose a model for probabilistic semistructured data (PSD). The advantage of our approach is that it supports a flexible representation that allows the specification of a wide class of distributions over semistructured instances. We provide two semantics for the model and show that the semantics are probabilistically coherent. Next, we develop an extension of the relational algebra to handle probabilistic semistructured data and describe efficient algorithms for answering queries that use this algebra. Finally, we present experimental results showing the efficiency of our algorithms.