Querying a Web of Linked Data ：Foundations and Query Execution ( Studies on the Semantic Web )

Publication subTitle ：Foundations and Query Execution

Publication series ：Studies on the Semantic Web

Author： Hartig O.

Publisher： Ios Press‎

Publication year： 2016

E-ISBN: 9781614996316

P-ISBN(Paperback): 9781614996309

Subject： TP Automation Technology , Computer Technology

Keyword：自动化技术、计算机技术

Language： ENG

Access to resources Favorite

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Description

In recent years, an increasing number of organizations and individuals have contributed to the Semantic Web by publishing data according to the Linked Data principles. In addition, a significant body of Semantic Web research exists that studies various aspects of knowledge representation and automated reasoning over collections of such data. However, a challenge that is crucial for achieving the vision of a Semantic Web – but that has not yet been studied to a comparable extent – is to enable automated software agents to operate directly on decentralized Linked Data that is distributed over the WWW. In particular, fundamental questions related to querying this data on the WWW have received very limited research attention. This book contributes towards filling this gap by studying the foundations of declarative queries over Linked Data on the WWW. Our particular focus in this book are approaches to use the SPARQL query language and execute queries by traversing Linked Data live during the query execution process. More specifically, we first provide formal foundations to adapt SPARQL to the given context. Thereafter, we use an abstract machine model to formally show computational feasibility and related properties of the resulting types of SPARQL queries. Additionally, we investigate fundamental properties of applying the traversal-based approach to query execution that is tailored to the use case of querying Linked Data directly on the WWW.

Chapter

1.1. Linked Data on the WWW

1.2. Approaches to Query Linked Data

1.3. Problem Statement

1.4. Contributions

1.5. Thesis Outline

I. Foundations of Queries over a Web of Linked Data

2. Models for Linked Data Queries

2.1. Data Model

2.1.1. Structural Elements

2.1.2. Queries

2.1.3. Related Work

2.2. Computation Model

2.2.1. Existing Models of Computation on the WWW

2.2.2. The LD Machine

2.2.3. LD Machine Computability

2.2.4. LD Machine Decidability

3. Full-Web Query Semantics

3.1. Related Work

3.1.1. Web Query Languages

3.1.2. Navigational Query Languages for Linked Data

3.1.3. SPARQL as a Query Language for Linked Data

3.2. Definition

3.2.1. SPARQL

3.2.2. SPARQLLD

3.3. Theoretical Properties

3.3.1. Satisfiability, (Un)bounded Satisfiability, and Monotonicity

3.3.2. LD Machine Decidability of Termination

3.3.3. LD Machine Computability

3.3.4. Finiteness of Expected Query Results

3.4. Summary

4. Reachability-Based Query Semantics

4.1. Definition

4.1.1. Reachability

4.1.2. SPARQLLD(R)

4.2. Result Containment and Infiniteness

4.3. Reachability Criteria

4.3.1. Comparing Reachability Criteria

4.3.2. Combining Reachability Criteria

4.3.3. Reachability Criteria that Ensure Finiteness

4.3.4. Constant Reachability Criteria

4.4. Theoretical Properties

4.4.1. Satisfiability, (Un)bounded Satisfiability, and Monotonicity

4.4.2. LD Machine Decidability of Termination

4.4.3. LD Machine Computability

4.5. Differences between SPARQLLD and SPARQLLD(R)

II. Execution of Queries over a Web of Linked Data

5. Overview of Query Execution Techniques

5.1. Data Source Selection

5.1.1. Live Exploration Approaches

5.1.2. Index-Based Approaches

5.1.3. Hybrid Approaches

5.2. Data Source Ranking

5.3. Integration of Data Retrieval and Result Construction

5.3.1. Separated Execution Approaches

5.3.2. Integrated Execution Approaches

5.4. Traversal-Based Query Execution

5.5. Summary

6. A Traversal-Based Strategy

6.1. Conjunctive Linked Data Queries

6.2. Informal Description

6.3. Query Execution Model

6.3.1. Overview

6.3.2. Partial Solutions

6.3.3. Constructing (Partial) Solutions

6.3.4. Discovered Subwebs of the Queried Web

6.3.5. Traversing Data Links

6.3.6. Combining Construction and Traversal

6.3.7. Abstract Query Execution Procedure

6.4. Soundness and Completeness

6.5. Summary

7. An Iterator-Based Implementation

7.1. Definition

7.1.1. Iterators for Query Execution over RDF Data

7.1.2. Iterators for Traversal-Based Query Execution

7.2. Formal Analysis

7.2.1. Examples for Incompleteness

7.2.2. Alignment with the Execution Model

7.3. Experimental Analysis

7.3.1. Our Query Execution System

7.3.2. WWW-Based Experiment

7.3.3. Simulation Based Experiments

7.4. Summary

III. Conclusions

8. Conclusions

8.1. Main Results

8.2. Directions for Future Work

8.2.1. Schema Heterogeneity

8.2.2. Coreferences

8.2.3. Trustworthiness and Data Quality

8.2.4. Dynamic Environment

8.2.5. Query Expressiveness

IV. Appendix

A. Commonly Used Symbols

B. Encoding of Structures Related to Query Computation

B.1. Encoding Basic Elements

B.2. Encoding RDF Triples

B.3. Encoding Webs of Linked Data

B.4. Encoding Valuations

C. Basic Properties of SPARQL Queries

C.1. Satisfiability

C.2. Monotonicity

C.3. Bounded Satisfiability and Unbounded Satisfiability

D. Supplementary Information about the Experiments

D.1. Queries for the WWW-Based Experiment

D.2. Measurements of the WWW-Based Experiment

D.3. Queries for the Simulation-Based Experiments

E. Proofs of Auxiliary Results

E.1. Proof of Lemma 3.1

E.2. Proof of Lemma 3.2

E.3. Proof of Lemma 4.1

E.4. Proof of Lemma 4.2

E.5. Proof of Lemma 4.3

E.6. Proof of Lemma 4.4

E.7. Proof of Lemma 4.5

E.8. Proof of Lemma 4.6

E.9. Proof of Lemma 4.7

E.10.Proof of Lemma 6.1

E.11.Proof of Lemma 6.2

E.12.Proof of Lemma 6.3

The users who browse this book also browse