[Zurück]

P. Barceló, R. Pichler, S. Skritek:
"Efficient Evaluation and Approximation of Well-designed Pattern Trees";
Vortrag: Symposium on Principles of Database Systems, PODS 2015, Melbourne, Victoria, Australia; 31.05.2015 - 04.06.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 (Hrg.); ACM, (2015), ISBN: 978-1-4503-2757-2; S. 131 - 144.

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.

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

http://dx.doi.org/10.1145/2745754.2745767

Projektleitung Reinhard Pichler:
Heterogene Information Integration

Projektleitung Reinhard Pichler:
SEE: SPARQL Evaluation and Extensions