University of Twente Student Theses


Querying Uncertain Data in XML

Knippers, D. (2014) Querying Uncertain Data in XML.

[img] PDF
Abstract:This thesis describes the design and implementation of an extension for an XML DBMS which enables the execution of XPath queries over uncertain data. The challenge of querying uncertain data is that an uncertain data set represents many possible worlds; one for each combination of alternatives for all uncertain data items. A major problem is the exponential growth of the number of possible worlds with respect to the number of uncertain values. We describe a way to query the uncertain data directly; without possible world expansion. An XML data format for uncertain data is defined which supports local independence and mutual exclusion relations among different values. Query evaluation over uncertain data is achieved by transforming an input XPath query to an XQuery which keeps track of the random variable annotations that are used to select only consistent values and to compute the probabilities of resulting values. Only the transformed query is executed by the XML DBMS. In addition to regular XPath queries the aggregate functions Count, Sum, Min, and Max are also supported which yield summary values that describe the distribution of the actual result values. Min and Max also provide the top-k result values, unlike Count and Sum.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:54 computer science
Programme:Computer Science MSc (60300)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page