[Back]


Talks and Poster Presentations (with Proceedings-Entry):

P. Barceló, R. Pichler, S. Skritek:
"Efficient Evaluation and Approximation of Well-designed Pattern Trees";
Talk: Symposium on Principles of Database Systems, PODS 2015, Melbourne, Victoria, Australia; 05-31-2015 - 06-04-2015; in: "Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS 2015, Melbourne, Victoria, Australia, May 31 - June 4, 2015", T. Milo, D. Calvanese (ed.); ACM, (2015), ISBN: 978-1-4503-2757-2; 131 - 144.



English abstract:
Conjunctive queries (CQs) fail to provide an answer when the pattern described by the query does not exactly match the data. CQs might thus be too restrictive as a querying mechanism when data is semistructured or incomplete. The semantic web therefore provides a formalism - known as well-designed pattern trees (WDPTs) - that tackles this problem: WDPTs allow us to match patterns over the data, if available, but do not fail to give an answer otherwise. Here we abstract away the specifics of semantic web applications and study WDPTs over arbitrary relational schemas. Our language properly subsumes the class of CQs. Hence, WDPT evaluation is intractable. We identify structural proper ties of WDPTs that lead to tractability of various variants of the evaluation problem. For checking if a WDPT is equivalent to one in our tractable class, we prove 2EXPTIME-membership. As a corollary, we obtain fixed-parameter tractability of (variants of) the evaluation problem. Our techniques also allow us to develop a theory of approximations for WDPTs.

Keywords:
RDF; well-designed pattern trees; effcient query answering; containment; subsumption; approximations


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1145/2745754.2745767



Related Projects:
Project Head Reinhard Pichler:
Heterogene Information Integration

Project Head Reinhard Pichler:
SEE: SPARQL Evaluation and Extensions


Created from the Publication Database of the Vienna University of Technology.