Aus Aifbportal
Wechseln zu:Navigation, Suche

Processing Flexible Hybrid Graph Patterns over Text-Rich Data Graphs

Published: 2012 November
Institution: Institut AIFB, KIT
Erscheinungsort / Ort: Karlsruhe


Many databases today are text-rich in that they not only capture structured but also unstructured data. Towards flexible querying of this hybrid data, we propose Flexible Hybrid Graph Pattern (fHGP) as an extension to SPARQL Basic Graph Pattern. It enables users to query using keywords, instead of the precise terms in the data, and relaxed-structured constraints. With the latter users can add structure information to the query when available or just use keywords otherwise. We show that processing an fHGP is possible by translating it to several unambiguous graph patterns. We then cast it as a multi-query processing problem, for which the answers can be obtained by simultaneously processing several queries called interpretations. For this we propose a multi-query top-k processing technique that is able to share intermediate results among interpretations, and to terminate early based on tight score bounds established from some particular interpretations. Further, we propose an adaptive join order optimization technique for this top-k processing. We compare our solution with existing top-k baselines that can be adapted for this problem. The results suggest that sharing results as proposed for our approach is several (3-4) times faster, and the proposed optimization yields further improvement (50%).