Query ranking in probabilistic XML data

Chang, L; Yu, JX; Qin, L

Query ranking in probabilistic XML data

Chang, L Yu, JX

Qin, L

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, EDBT'09, 2009, pp. 156 - 167
Issue Date:: 2009-09-21

Closed Access

	Filename	Description	Size
	2013002378OK.pdf		681.48 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Chang, L	en_US
dc.contributor.author	Yu, JX https://orcid.org/0000-0002-9738-827X	en_US
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062	en_US
dc.date.issued	2009-09-21	en_US
dc.identifier.citation	Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, EDBT'09, 2009, pp. 156 - 167	en_US
dc.identifier.isbn	9781605584225	en_US
dc.identifier.uri	http://hdl.handle.net/10453/28948
dc.description.abstract	Twig queries have been extensively studied as a major fragment of XPATH queries to query XML data. In this paper, we study PXML-RANK query, (Q, k), which is to rank top-k probabilities of the answers of a twig query Q in probabilistic XML (PXML) data. A new research issue is how to compute top-k probabilities of answers of a twig query Q in PXML in the presence of containment (ancestor/descendant) relationships. In the presence of the ancestor/descendant relationships, the existing dynamic programming approaches to rank top-k probabilities over a set of tuples cannot be directly applied, because any node/edge in PXML may have impacts on the top-k probabilities of answers. We propose new algorithms to compute PXML-RANK queries efficiently and give conditions under which a PXML-RANK query can be processed efficiently without enumeration of all the possible worlds. We conduct extensive performance studies using both real and large benchmark datasets, and confirm the efficiency of our algorithms. Copyright 2009 ACM.	en_US
dc.relation.ispartof	Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, EDBT'09	en_US
dc.relation.isbasedon	10.1145/1516360.1516380	en_US
dc.title	Query ranking in probabilistic XML data	en_US
dc.type	Conference Proceeding
utslib.for	0806 Information Systems	en_US
dc.location.activity	Saint-Petersburg, Russia	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US

Abstract:

Twig queries have been extensively studied as a major fragment of XPATH queries to query XML data. In this paper, we study PXML-RANK query, (Q, k), which is to rank top-k probabilities of the answers of a twig query Q in probabilistic XML (PXML) data. A new research issue is how to compute top-k probabilities of answers of a twig query Q in PXML in the presence of containment (ancestor/descendant) relationships. In the presence of the ancestor/descendant relationships, the existing dynamic programming approaches to rank top-k probabilities over a set of tuples cannot be directly applied, because any node/edge in PXML may have impacts on the top-k probabilities of answers. We propose new algorithms to compute PXML-RANK queries efficiently and give conditions under which a PXML-RANK query can be processed efficiently without enumeration of all the possible worlds. We conduct extensive performance studies using both real and large benchmark datasets, and confirm the efficiency of our algorithms. Copyright 2009 ACM.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/28948