View publication
| Title | Efficient Evaluation and Approximation of Well-designed Pattern Trees |
| Authors | Pablo Barceló, Reinhard Pichler, Sebastian Skritek |
| Publication date | 2015 |
| 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 properties 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. |
| Pages | 131-144 |
| Conference name | ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems |
| Publisher | ACM Press (New York, NY, USA) |
| Reference URL |
|