Cost-based Optimization for SPARQL Property Path Queries

点击翻译按钮获取中文摘要

Much information comes looking like a network. People know people. Web pages link to other other web pages. Proteins interact with certain other proteins in ways that make life itself possible. These types of information are graphs; with people, web pages, or proteins as the nodes of the graph, and relationships (e.g., "knows"), links, or interactions as the edges of the graph. Useful data of this form is being collected nowadays in copious amounts; e.g., for social networks like Facebook, following people and their friends; in the World Wide Web, with its pages and links between pages; and by scientists, collecting vast evidence of protein and gene interactions.***To extract useful information-that is, to answer questions-against such data stores is done by asking questions, called queries, that are written in a specialized query language to the database system that is managing the data to answer. A most successful query language is SQL, which is widely used to query relational data, information that stored in tabular, spreadsheet-like format. The technology behind these relational database management systems and SQL has evolved over the last forty years to where SQL queries can often be answered quite efficiently, even over very large data collections. This has led the way to database systems being used behind the scenes in almost every aspect of our daily lives, from keeping proper track of our financial statements and transactions to enabling doctors and scientists to sift effortlessly through millions of experimental results to find the most relevant ones.***SPARQL is a query language for RDF data stores (graph-like data). RDF and SPARQL were created recently, designed to enable the Web's information to be automatically explored, within an effort that has been named the Semantic Web. But answering queries posed in SPARQL is not nearly as efficient as in SQL, yet. As was with SQL before, hard work is now needed for us to learn how to improve the process of answering SPARQL queries (the steps of query optimization and evaluation).***This work is about accomplishing that. SPARQL can then become a truly useful tool to query graph data. This would make exploring graph information much easier, letting people discover new connections, enabling new Web applications not before possible, and helping scientists to make new breakthroughs.