Semantic Web: Past, Present, and Future

The Linked Data principles⁴⁰⁴⁰40http://www.w3.org/DesignIssues/LinkedData.html define the methods for representing, publishing, and using data on the Semantic Web. They can be summarized as follows:

1. 1.

   URIs are used as names for entities.

2. 2.

   The HTTP protocol’s GET method is used to retrieve descriptions for a URI.

3. 3.

   Data providers shall return relevant information in response to HTTP GET requests on URIs using standards, e. g., in RDF.

4. 4.

   Links to other URIs shall be used to facilitate knowledge discovery and use of additional information.

Publishing data using Linked Data principles allows easy access to data via HTTP. This allows exploration of resources and navigation across resources on the Semantic Web. URIs (see 1.) are dereferenced using HTTP requests (2.) to obtain additional information about a given resource. In particular, using standardized syntax (3.), this information may also contain links to other resources (4.).

Figure 3 represents an example of Linked Data about the pop group ABBA. The example describes several relationships linking entities to ABBA’s URI, such as foaf:member and rdf:type. In the figure “ABBA”, or more precisely the URI of ABBA, is the subject, “Property” refers to relationships, and “Value” represents objects of the RDF triples. The relation owl:sameAs will be explained in more in Section 6. The prefixes foaf, rdf, and owl refer to vocabularies of the FOAF ontology⁴¹⁴¹41http://xmlns.com/foaf/spec/, and the W3C language specifications of RDF and OWL, respectively.

An ontology is commonly defined as a formal, machine-readable representation of key concepts and relationships within a specific domain [111, 109]. In essence, ontologies capture a shared perspective [111] that is, the formal conceptualization of ontologies expresses a consensus view among different stakeholders. Visualizing ontologies is akin to viewing a spectrum, with a specificity of concepts, their relationships, and the granularity of meaning representation varying along this continuum  [101, 149, 148]. A controlled vocabulary corresponds to the less expressive form of ontology, comprising a restrictive list of words or terms used for labeling, indexing, or categorization. The Clinical Data Interchange Standards Consortium (CDISC) Terminology is an exemplary vocabulary that harmonizes definitions in clinical research.⁴²⁴²42https://datascience.cancer.gov/resources/cancer-vocabulary/cdisc-terminology A thesaurus is located next in the spectrum; they enhance controlled vocabularies with information about terms and their synonyms and broader/narrower relationships. The Unified Medical Language System (UMLS) integrates medical terms and their synonyms.⁴³⁴³43https://www.nlm.nih.gov/research/umls/index.html Next, taxonomies are built over controlled vocabularies to provide a hierarchical structure, e. g., parent/child relationship. SNOMED-CT⁴⁴⁴⁴44https://www.snomed.org/value-of-snomedct (Systematized Nomenclature of Medicine Clinical Terms) provides a terminology and coding system used in healthcare and medical fields; medical concepts organized in a hierarchical structure enabling a granular representation of clinical information. The Simple Knowledge Organization System (SKOS)⁴⁵⁴⁵45https://www.w3.org/TR/skos-reference/ is a W3C standard to describe knowledge about organizational systems. Lastly, ontologies are at the highest extreme of the spectrum, integrating sets of concepts with attributes and relationships to define a domain of knowledge.

Note, SKOS is a popular standard for modeling domain-specific taxonomies in the different scientific communities such as economics, social sciences, etc. to represent concepts and their relationships, most importantly narrower, broader, and related. However, it does not have the expressiveness of OWL with its complex expressions on classes and relations. For a detailed discussion, we refer to the literature such as [89] and the W3C on using OWL and SKOS⁴⁶⁴⁶46https://www.w3.org/2006/07/SWD/SKOS/skos-and-owl/master.html.

A network of ontologies, such as the example shown in Figure 1, may consist of a variety of ontologies created by different actors and communities. Ontologies may be the result of a transformation or reengineering activity of a legacy system, such as a relational database or existing taxonomy such as the Dewey Decimal Classification⁴⁷⁴⁷47http://dewey.info/ or Dublin Core. Other ontologies are created from scratch. This involves applying existing methods and tools for ontology engineering and choosing an appropriate representation language for the ontology (see Section 6).

Ontology engineering deals with the methods for creating ontologies [65] and has its origins in software engineering in the creation of domain models and in database design in the creation of conceptual models. A good overview of ontology engineering can be found in several reference books [65]. Ontologies vary greatly in their structure, size, development methods applied, and application domains considered. Complex ontologies are also distinguished in terms of their purpose and granularity.

Domain Ontologies represent knowledge specific to a particular domain [48, 109]. Domain ontologies are used as external sources of background knowledge [48]. They can be built on foundational ontologies [110] or core ontologies [131], which provide precise structuring to the domain ontology and thus improve interoperability between different domain ontologies. Domain ontologies can be simple such as the FOAF ontology or the event ontology mentioned above, or very complex and extensive, having been developed by domain experts, such as the SNOMED medical ontology.

Core Ontologies represent a precise definition of structured knowledge in a particular domain spanning multiple application domains [131, 109]. Examples of core ontologies include core ontologies for software components and web services [109], for events and event relationships [129], or for multimedia metadata [126]. Core ontologies should thereby build on foundational ontologies to benefit from their formalization and strong axiomatization [131]. For this purpose, new concepts and relations are added to core ontologies for the application domain under consideration and are specialized by foundational ontologies.

Foundational Ontologies have a very wide scope and can be reused in a wide variety of modeling scenarios [24]. They are therefore used for reference purposes [109] and aim to model the most general and generic concepts and relations that can be used to describe almost any aspect of our world [24, 109], such as objects and events. An example is the Descriptive Ontology for Linguistic and Cognitive Engineering (DOLCE) [24]. Such basic ontologies have a rich axiomatization that is important at the developmental stage of ontologies. They help ontology engineers to have a formal and internally consistent conceptualization of the world, which can be modeled and checked for consistency. For the use of foundational ontologies in a concrete application, i. e., during the runtime of an application, the rich axiomatization can often be removed and replaced by a more lightweight version of the foundational ontology.

In contrast, domain ontologies are built specifically to allow automatic reasoning at runtime. Therefore, when designing and developing ontologies, completeness and complexity on the one hand must always be balanced with the efficiency of reasoning mechanisms on the other. In order to represent structured knowledge, such as the scenario depicted in Figure 1, interconnected ontologies are needed, which are spanned in a network over the Internet. For this purpose, the ontologies used must match and be aligned with each other.

A network of ontologies must be flexible with respect to the functional requirements imposed on it. This is because systems are modified, extended, combined, or integrated over time. In addition, the networked ontologies must lead to a common understanding of the modeled domain. This common understanding can be achieved through a sufficient level of formalization and axiomatization, and through the use of ontology patterns. An ontology pattern, similar to a design pattern in software engineering, represents a generic solution to a recurring modeling problem [131]. Ontology patterns allow to select parts from the original ontology. Either all or only certain patterns of an ontology can be reused in the network. Thus, to create a network of ontologies, e. g., existing ontologies and ontology patterns can be merged on the Web. The ontology engineer can drive or explicitly provide for the modularization of ontologies using ontology patterns. Core ontologies represent one approach to designing a network of ontologies (see in detail [131]). They allow to capture and exchange structured knowledge in complex domains. Well-defined core ontologies fulfill the properties mentioned in the previous section and allow easy integration and smooth interaction of ontologies (see also [131]). The networked ontologies approach leads to a flat structure, as shown in Figure 1, where all ontologies are used on the same level. Such structures can be managed up to a certain level of complexity.

The approach of networked core ontologies is illustrated by the example of ontology layers starting from foundational to core to domain ontologies. As shown in Figure 4, DOLCE is the foundational ontology at the bottom layer, the Multimedia Metadata Ontology (M3O) [126] as the core ontology for multimedia metadata, and an extension of M3O for the music domain. Core ontologies are typically defined in description logic and cover a field larger than the specific application domain requires [57]. Concrete information systems will typically use only a subset of core ontologies. To achieve modularization of core ontologies, they should be designed using ontology patterns. By precisely matching the concepts in the core ontology with the concepts provided in the foundational ontology, they provide a solid foundation for future extensions. New patterns can be added and existing patterns can be extended by specializing the concepts and roles. Figure 4 shows different patterns of the M3O and DOLCE ontologies.

Ideally, the ontology patterns of the core ontologies are reused in the domain ontologies [57], as shown in Figure 4. However, since it cannot be assumed that all domain ontologies are aligned with a foundational or core ontology, the option that domain ontologies are developed and maintained independently must also be considered. In this case, domain knowledge can be reused in core ontologies by applying the Descriptions and Situations (DnS) ontology pattern of the foundational ontology DOLCE. The DnS ontology pattern is an ontological formalization of context [109] by defining different views using roles. These roles can refer to domain ontologies and allow a clear separation of the structured knowledge of the core ontology and domain-specific knowledge. To model a network of ontologies, such as the example described above, the Web Ontology Language (OWL) and its ability to axiomatize using description logic [12] is used. In addition to being used to model a distributed knowledge representation and integration, OWL, is also used in particular to derive inferences from this knowledge, which is described in Section 6.

Graph data can be created by transforming legacy data via a data integration system [98], which consists of a unified schema, data sources, and mapping rules. These mapping rules define the concepts within the schema and establish links to the data sources. By employing declarative definitions, knowledge graph creation promotes modularity and reusability. This approach allows users to trace the entire graph creation process, leading to improved transparency and ease of maintenance.

To enable comprehensive and extensive graph specification, mappings and transformations have been developed to convert data from various storage models into Semantic Web data models like RDF. These mappings and transformations facilitate the mapping of data into RDF, thereby supporting the integration of diverse data sources into the Semantic Web.

The mapping language R2RML [37] defines mapping rules from relational databases (relational data models) to RDF graphs. These mappings themselves are also RDF triples [15]. Because of its compact representation, Turtle is considered a user-friendly notation of RDF graphs. The structure of R2RML is illustrated in Figure 5; essentially, table contents are mapped to triples by the classes SubjectMap, PredicateMap, and ObjectMap. If the object is a reference to another table, this reference is called RefObjectMap. Here, SubjectMap contains primary key attributes of the corresponding table. Thus, there exists a mapping rule representable in RDF graphs by means of which tables of relational databases can be represented as RDF graphs.

The RDF Mapping Language (RML)[42] extends R2RML to encompass the definition of logical sources in various formats, including CSV, JSON, XML, and HTML. This enhancement enables RML to introduce new operators that facilitate the integration of data from diverse sources into the Semantic Web. Thus, instead of LogicalTable, RML includes the tag LogicalSource, to allow for the retrieval of data in several formats. Additionally, RML resorts to W3C-standardized vocabularies and enables the definition of retrieval procedures to collect data from Web APIs or databases. R2RML and RDF mapping rules are expressed in RDF, and their graphs document how classes and properties in one or various ontologies that are part of an RDF graph are populated from data collected from potentially heterogeneous data sources.

Over time, the Semantic Web community has actively contributed to addressing the challenge of integrating heterogeneous datasets, resulting in the development of several frameworks for executing declarative mapping rules [34, 28, 116]. A rich spectrum of tools (e. g., RMLMapper [42], RocketRML [136], CARML⁴⁸⁴⁸48https://github.com/carml/carml, SDM-RDFizer [87], Morph-KGC [8], and RMLStreamer [112]) offers the possibility of executing R2RML and RML rules and efficiently materializing the transformed data into RDF graphs. Van Assche et al. [10] provided an extensive survey detailing the main characteristics of these engines. Despite significant efforts in developing these solutions, certain parameters can impact the performance of the graph creation process [31]. Existing engines may face challenges when handling complex mapping rules or large data sources. Nonetheless, the community continues to collaborate and address these issues. An example of such collaboration is the Knowledge Graph Construction Workshop 2023 Challenge⁴⁹⁴⁹49https://zenodo.org/record/7689310 that took place at ESWC 2023. This community event aims to understand the strengths and weaknesses of existing approaches and devise effective methods to overcome existing limitations.

RDF graphs can also be dynamically created through the execution of queries over data sources. These queries involve the rewriting of queries expressed in terms of an ontology, based on mapping rules that establish correspondences between data sources and the ontology. Tools such as Ontop [28], Ultrawrap [135], Morph [116], Squerall [100], and Morph-CSV [32] exemplify systems that facilitate the virtual creation of RDF graphs.

Quality and validation of the graph data are crucial to maintaining the integrity of the Semantic Web [44, 38, 163]. The evaluation of integrity constraints allows for the identification of inconsistencies, inaccuracies, or contradictions within the data. They also help maintain consistency by ensuring related data elements remain coherent. Constraints are logical statements – expressed in a particular language – that impose restrictions on the values taken for target nodes in a given property.

Constraints can be expressed using OWL [144], SPARQL queries [97], or using shapes. However, the interpretation of the results depends on the semantics followed to interpret the failure of an integrity constraint. For example, constraints expressed in OWL are validated using an Open-World Assumption (OWA) (i. e., a statement cannot be inferred to be false based on failures to prove it) and under the absence of the Unique Name Assumption (UNA) (i. e., two different names may refer to the same object). These two features make it difficult to validate data in applications where data is supposed to be complete. Definitions of integrity constraint semantics in OWL using the Closed-World Assumption [103, 104, 144] overcome these issues.

Contrarily, constraints expressed using SPARQL queries or shapes will be evaluated under the Closed-World Assumption (CWA) and following the Unique Name Assumption (UNA). Nevertheless, some constraints may be difficult to express in SPARQL, and the specification process is prone to errors and difficult to maintain.

Data quality conditions and integrity constraints can also be expressed as graphs of shapes or the so-called shapes schema. A shape corresponds to a conjunction of constraints that a set of nodes in an RDF graph must satisfy [79]. These constraints can restrict the types of nodes, the cardinality of certain properties, and the expected data types or values for specific properties. A shape can target the instances of a class, the domain or range of a property, or a specific node in the RDF graph. A shape or node in a shapes graph is validated in an RDF graph, if and only if, all the target nodes in the RDF graph satisfy all the constraints in the shape. Figure 6 presents a shapes graph of three shapes targeting the classes Brand, Playcount, and MusicArtist. Each of the shapes comprises one constraint. In the shapes Brand and MusicArtist the properties title and name can take more than one value, while the shape Playcount states that each instance of the class Playcount must have exactly one value of the property count. Additionally, the instances of the class Brand must be related to valid instances of the class Playcount which should also be related to valid instances of the class MusicArtist.

There are two standards for defining shapes, ShEx (Shape Expressions) [117]) and SHACL (Shapes Constraint Language) [95]). Both define shapes over the attributes (i. e., owl:DatatypeProperties), and constraints on incoming/outgoing arcs, cardinalities, RDF syntax, and extension mechanism. These inter-class constraints induce a shape network used to validate the integrity and data quality properties of an RDF graph.

SHACL and ShEx, although sharing a common goal, adopt distinct approaches. ShEx seeks to offer a language serving as a grammar or schema for RDF graphs, delineating RDF graph structures for validation. On the other hand, SHACL is positioned as the W3C recommendation for validating RDF graphs against a conjunction of constraints, emphasizing a constraint language for RDF. Despite their analogous roles in specifying shapes and constraints for RDF data, ShEx and SHACL differ in syntax, expressiveness, and community adoption [59].

The evaluation results of a SHACL shape network over an RDF graph are presented in validation reports using a controlled vocabulary. A validation report includes explanations about the violations, the severity of the violation, and a message describing the violation. SHACL is the language selected by the International Data Space (IDS) to express the restrictions that state the integrity over RDF graphs [96]. Besides the integrity validation of an RDF graph, SHACL can be utilized to describe data sources and the certification of a query answer [124], as metadata to enhance the performance of a SPARQL query engine [118], to certify access policies [125], and to provide provenance as a result of the validation of integrity constraints [40].

In the context of a quality assessment pipeline, one crucial step involves validating the shape schema against a graph. It is important to mention that the validation of recursive shape schemas is not explicitly addressed in the SHACL specification [95]. To address this gap, Corman et al. [36] introduce a semantic framework for validating recursive SHACL. They also demonstrated that validating full SHACL features is an NP-hard problem. Building on these insights, they proposed specific fragments of SHACL that are computationally tractable, along with a fundamental algorithm for validating shape schemas using SPARQL [35]. In a related vein, Andresel et al. [7] propose a stricter semantics for recursive SHACL, drawing inspiration from stable models employed in Answer Set Programming (ASP). This innovative approach enables the representation of SHACL constraints as logic programs and leverages existing ASP solvers for shape schema validation. Importantly, this approach allows for the inclusion of negations in recursive validations. Further, Figuera et al. [51] present Trav-SHACL, an approach that focuses on query optimization techniques aimed at enhancing the incremental behavior and scalability of shape schema validation.

While SHACL has been adopted in a broad range of use cases, given a large graph it remains a challenge how to define shapes efficiently [119]. In many industrial settings with billions of entities and facts [108] creating shapes manually simply is not an option. The current state of the art can automatically extract shapes on WikiData (ca. 2 Billion facts) in less than 1.5 hours while filtering shapes based on the well-established notions of support and confidence to avoid reporting thousands of shapes that are so rare or apply to such a small subset of the data that they become meaningless [120]. Still, more work is needed to increase scalability further and also to help users make good use of the mined shapes [121] and, e. g., interactively use them to correct and improve the quality of their graphs.

Based on formal languages representing graph data and their semantics, further (implicit) facts can be derived from the knowledge base by deductive inference. In the following, we exemplify the derivation of implicit facts from a set of explicitly given facts using the RDFS construct rdfs:subClassOf and the OWL construct owl:sameAs. The property rdfs:subClassOf describes hierarchical relationships between classes and with owl:sameAs two resources can be defined as identical.

As a first example, we consider the class foaf:Person, which is defined in the FOAF ontology, and the classes mo:Musician and mo:Group, which are defined in the music ontology. In the music ontology, there is an additional axiom that defines mo:Musician as a subclass of foaf:Person using rdfs:subClassOf. Given this axiom, it can be deduced by deductive inference that instances of mo:Musician are also instances of foaf:Person. Now if there is such a hierarchy of classes and in addition a statement that Anni-Frid Lyngstad is of type mo:Musician, then it can be inferred by inference that Anni-Frid Lyngstad is also of type foaf:Person. This means that all queries asking for entities of type foaf:Person will also include Anni-Frid Lyngstad in the query result, even if that entity is not explicitly defined as an instance of foaf:Person. Figure 7 represents these facts and the corresponding class hierarchy in RDFS as a directed graph.

In the second example, the OWL construct owl:sameAs is used to define two resources as identical, for example http://www.bbc.co.uk/music/artists/d87e52c5-bb8d-4da8-b941-9f4928627dc8#artist and http://dbpedia.org/resource/ABBA. Identical here means that these two URIs represent the same real-world object. By inference, information about ABBA from different sources can now be linked. Since ontologies are created independently on the web, and URIs are subject to local naming conventions, a real-world object may be represented by multiple URIs (in different ontologies).

OWL offers a variety of other constructs for the description of classes, relationships, and concrete facts. For example, OWL allows the declaration of transitive relations and inverse relations. For example, the relation “is-member” is inverse to “has-member”. OWL reasoning allows, among other things, consistency checking of an ontology or checking the satisfiability of classes [80]. A class is satisfiable if there can be instances of that class.

For a detailed discussion about OWL reasoning, we refer to the literature such as [80, 13]. Different reasoners for OWL have seen widespread adoption in the community such as the well-known Pellet⁵⁰⁵⁰50https://github.com/stardog-union/pellet and Hermit [62]. Finally, a combination of description logic and rules is also possible. For example, Motik et al. [105] presented a combination of description logic and rules that allows tractable inference on OWL ontologies.

In the Semantic Web, it cannot be assumed that two URIs refer to two different real-world objects (cf. unique name assumption in Section 5.2). A URI by itself, or in itself, has no identity [70]. Rather, the identity or interpretation of a URI is revealed by the context in which it is used on the Semantic Web. Determining whether or not two URIs refer to the same entity is not a simple task and has been studied extensively in data mining and language understanding in the past. For example, to identify whether or not the author names of research papers refer to the same person, it is often not sufficient to resolve the name, venue, title, and co-authors [90]. The process of determining the identity of a resource is often referred to as entity resolution [90], coreference resolution [156], object identification [123], and normalization [156, 157]. Correctly determining the identity of entities on the Web is important as more and more records appear on the Web and this presents a significant hurdle for very large Semantic Web applications [61].

To address this, a number of services exist that can recognize entities and determine their identity: Thomson Reuters offers OpenCalais⁵¹⁵¹51https://www.refinitiv.com/en/products/intelligent-tagging-text-analytics, a service that can link natural language text to other resources using entity recognition. Another commercial tool that allows for extracting knowledge graphs from text is provided by DiffBot.⁵²⁵²52https://www.diffbot.com/ Recently, the language model ChatGPT has been compared to the specialized entity and relation extraction tool REBEL [27] for the task of creating knowledge graphs from sustainability-related text [145]. The experiments suggest that large language models improve the accuracy of creating knowledge graphs [145]. The sameAs⁵³⁵³53http://sameas.org/ service aims to detect duplicate resources on the Semantic Web using the OWL relationship owl:sameAs. This can be used to resolve coreferences between different datasets. For example, for the query with the URI http://dbpedia.org/resource/ABBA, a list of over 100 URIs is returned that also references the music group ABBA. One of them is BBC with the resource http://www.bbc.co.uk/music/artists/d87e52c5-bb8d-4da8-b941-9f4928627dc8#artist.

Furthermore, the problem of schema matching [157] is very related to the problem of entity resolution, co-reference resolution, and normalization. The goal of schema matching is to address the question of how to integrate data [157], which is non-trivial even for small schemas. In the Semantic Web, schema matching means the matching of different ontologies, respectively the concepts defined in these ontologies. Various (semi-)automatic or machine learning techniques for matching ontologies have been developed in the past [49, 46, 22]. Core ontologies as illustrated in Figure 4.3 represent generic modeling frameworks for integration and alignment with other ontologies. In addition, core ontologies can also integrate Linked Open Data, which typically contains no or very little schema information. The YAGO ontology [140] was generated from the fusion of Wikipedia and Wordnet using rule-based and heuristic methods. A manual assessment showed an accuracy of 95%.

Manual matching of different data sources is also pursued in the Linked Open Data project of the German National Library⁵⁴⁵⁴54http://www.d-nb.de/. For example, the database containing the authors of all documents published in Germany was manually linked with DBpedia and other data sources. A particular challenge was to identify the authors, as described above. For example, former German Chancellor Helmut Kohl has a namesake whose work should not be linked to the chancellor’s DBpedia entry. Relationships between keywords used to describe publications are asserted using the SKOS (Simple Knowledge Organization System) vocabulary.⁵⁵⁵⁵55https://www.w3.org/TR/2009/REC-skos-reference-20090818/ For example, keywords are related to each other using the relation skos:related. Hyponyms and hypernyms are expressed by the relations skos:narrower and skos:broader. Finally, the Ontology Alignment Evaluation Initiative⁵⁶⁵⁶56http://oaei.ontologymatching.org/ should be mentioned, which aims to achieve an established consensus for evaluating ontology matching methods.

In principle, a SPARQL query is evaluated by comparing the graph pattern defined in the query to the RDF graph and reporting all matches as results. The set of results can be restricted by additional criteria, such as filters, i. e., conditions on variables and triple patterns that additionally need to be fulfilled.

As an example, let us consider the query illustrated in Figures 8 and 9 that we want to execute over our example MusicBrainz graph from Section 2. We are now interested in the musicians of ABBA who are also members of other bands. If we follow the Linked Data principles and evaluate the query using link traversal [74], this would mean first querying for triples including the IRI that represents ABBA, then navigating to the individual band members, and then following the links to all of the members’ bands and query more relevant triples.

Similar to relational database systems, there exist several dedicated graph stores (aka triple stores) that are optimized for RDF graphs and evaluating SPARQL queries. Some of the most popular triple stores are RDF4J [26], Jena [159], Virtuoso⁵⁸⁵⁸58http://virtuoso.openlinksw.com, and GraphDB⁵⁹⁵⁹59https://graphdb.ontotext.com/. They are building upon concepts and techniques known from relational database systems [83, 106] and expand them with graph-specific optimizations [153, 138, 68, 99, 50].

In addition to explicitly querying existing facts, SPARQL provides inferencing support through so-called entailment regimes. They correspond to logical consequences describing the relationship between the statements that are true when one statement logically follows from one or more statements. Entailment regimes specify an entailment relation between well-formed RDF graphs, assuming that a graph $G$ entails another graph $E$ (denoted $G$ $\vDash$ $E$) if there is a logical consequence from $G$ to $E$. A regime extends the query of explicitly existing facts with facts that can be inferred using RDFS and OWL constructs (cf. Section 6), such as the extension of facts about subclasses using rdfs:subClassOf.

Depending on the feature set of the respective SPARQL triple store, different (or even no) entailment regimes are supported. They differ in terms of their power in the supported inference capabilities over RDFS/OWL classes and relationships. SPARQL query engines such as GraphDB adopt a materialized approach, wherein they compute the closure of the input RDF graph $G$ over a set of relevant entailment rules $R$. Conversely, approaches grounded in query rewriting expand the SPARQL query itself rather than altering the RDF graph. Sub-queries are aligned with the entailment rules through backward chaining, and when the consequent of an entailment rule is matched, the antecedent of the rule is added to the query in the form of disjunctions.

Although both approaches yield equivalent answers for a given SPARQL query, their performance can diverge significantly. Materialized RDF query processing may outperform on-the-fly execution of the rewritten query, but it may consume more memory [63]. Nevertheless, various optimization techniques have been proposed to mitigate the overhead caused by the on-the-fly evaluation of entailment regimes [146]. These optimizations are required particularly in the presence of the owl:sameAs. This predicate corresponds to logical equivalence and involves the application of the Leibniz Inference Rule [66] to deduce all the equivalent triples entailed by equivalent resources based on owl:sameAs relation. This process may lead to many intermediate results, impacting the query engine’s performance. Xiao et al. [161] propose query rewriting techniques to efficiently evaluate SPARQL queries with owl:sameAs employing equivalent SQL queries.

Federations provide another perspective on querying linked data over multiple sources. A federation of knowledge graphs shares common entities while potentially providing different perspectives on those entities. Each knowledge graph within the federation operates autonomously and can be accessed through various Web interfaces, such as SPARQL endpoints or Linked Data Fragments (LDFs) [151]. SPARQL endpoints offer users the ability to execute any SPARQL query against multiple SPARQL endpoints. In contrast, LDFs enable access to specific graph patterns, such as triple patterns [150] or star-shaped graph patterns [5], allowing retrieval of fragments from an RDF knowledge graph. A star-shaped subquery is a conjunction of triple patterns in a SPARQL query that share the same subject variable [153]. An LDF client can submit requests to a server, which then delivers results based on a data shipping policy and partitions results into batches of specified page sizes. Query processing in a federation of graphs differs from querying a single source because it enables real-time data integration of graphs from multiple sources. For example, Figure 10 depicts a SPARQL query whose execution requires the evaluation of subqueries over three knowledge graphs: a Cancer Knowledge Graph (CKG) [6], DBpedia, and Wikidata. This query could not be executed over a single data source unless the three knowledge graphs were physically materialized into one. Subqueries with a specific shape (e. g., star-shaped subqueries) need to be identified and posed against the knowledge graph(s) that is able to answer a particular part of the query. The federated query engine has to decompose input queries into these subqueries, find a plan to execute them and collect and merge the answers from the subqueries to produce a federated answer.

A federated SPARQL query engine typically follows a mediator and wrapper architecture, which has been established in previous research [158, 162]. Wrappers play a crucial role in translating SPARQL subqueries into requests sent to SPARQL endpoints, while also converting the endpoint responses into internal structures that the query engine can process. The mediator, on the other hand, is responsible for rewriting the original queries into subqueries that can be executed by the data sources within the federation. Additionally, the mediator collects and merges the results obtained from evaluating the subqueries to produce the final answer to the federated query. Essentially, the mediator consists of three main components:

• $\mathrm{■}$

  Source selection and query decomposition. This component decomposes queries into subqueries and selects the appropriate graphs (sources) capable of executing each subquery. Simple subqueries typically consist of a list of triple patterns that can be evaluated against at least one graph. Formally, source selection corresponds to the problem of finding the minimal number of knowledge graphs from the federation that can produce a complete answer to the input query. On the other hand, query decomposition requires partitioning the triple patterns of a query into a minimal number of subqueries, such that each subquery can be executed over at least one of the selected knowledge graphs. Commonly, federated query engines follow heuristic-based methods to solve these two problems. For example, for query decomposition, heuristics based on exclusive groups [134] or star-shaped subqueries [153, 152, 102] enable to efficiently solve source selection and query decomposition in queries free of general predicates (e. g., owl:sameAs or rdf:type).

• $\mathrm{■}$

  Query optimizer. This component identifies execution plans by combining star-shaped subqueries (SSQs) and utilizing physical operators implemented by the query engine. Formally, optimizing a query corresponds to the problem of finding a physical plan for the query that minimizes the values of a utility function (e. g., execution time or memory consumption). To maximize the utility function, query optimizers consider plans with different orders of executing operators, alternative implementations of operators, such as joins, as well as particular execution alternatives for certain query types, e. g., queries involving aggregation [86]. In general, finding an optimal solution is computationally intractable [85], while the problems of constructing a bushy tree plan [132] and finding an optimal query decomposition over the graphs [152] are NP-Hard. A bushy tree plan is a query execution plan that represents a query as a tree structure with multiple branches or subqueries, which can also be bushy-tree plans. Query plans can be generated following the traditional optimize-then-execute paradigm or re-optimize and adapt a plan on the fly according to the conditions and availability of selected graphs [47]. Alternatively, the query optimizer may resort to a cost model to guide the search on the space of query plans and identify the one that minimizes the values of the utility function [102].

• $\mathrm{■}$

  Query engine. This component of a federated query engine implements the physical operators necessary to combine tuples obtained from the graphs. These physical operators are designed to support logical SPARQL operations such as JOIN, UNION, or OPTIONAL [115]. Physical operators can be empowered to adapt execution schedulers to the current conditions of a group of selected graphs. Thus, adaptivity can be achieved at the intra-operator level, where the operators can detect when graphs become blocked or data traffic bursts. Additionally, intra-operator opportunistically produce results as quickly as data arrives from the graphs, and can produce results incrementally. Some opportunistic approaches [4, 82, 56, 3] combine producing results quickly in an incremental fashion with greedy source selection so that the system stops querying additional graphs once the user’s wishes, e. g., in terms of the minimum number of obtained results, are fulfilled.

During the query optimization process, a plan is generated as a bushy tree that comprises four join operators. This is shown in Figure 10.

In HTML documents, the structure and composition of pages can be described with tags, but not the meaning of the information. Vocabulary, schemas, and microdata can be used as mark-up in HTML documents to describe information about page content and its meaning in a way that search engines can process this information.

Schema.org⁶²⁶²62http://schema.org is a collection of vocabularies and schemas to enrich HTML pages with additional information. The vocabulary of Schema.org includes a set of classes and their properties. A universal class “thing” is the most general, which is a kind of umbrella term for all classes. Other common classes are Organization, Person, Event, and Place. Properties are used to describe classes in more detail. For example, a person has the properties such as name, address, and date of birth.

In addition to vocabularies, Schema.org also specifies the use of HTML microdata, with the goal of representing data in HTML documents in as unambiguous a form as possible so that search engines can interpret it correctly. An example of this is formats for unique dates and times, which can also describe intervals to indicate the duration of events.

Schema.org is supported by the search engines Bing, Google, and Yandex, among others. There are extensions and libraries for various programming languages, including PHP, JavaScript, Ruby, and Python, to create web pages and web applications using vocabularies and microdata from Schema.org. Likewise, there are mappings from Schema.org vocabularies and microdata to RDFS.

A classic web browser enables the display of web pages. A semantic web browser goes one step further by additionally allowing the user to visualize the underlying information of individual pages, for example in the form of RDF metadata. Semantic Web browsers are also referred to as hyperdata browsers because they allow navigation between data while also allowing one to explore the connection to information about that data. Thus, ordinary users can use and exploit Semantic Web data for their information search.

Sig.ma [147] was an application for (browsing) Semantic Web data, which may come from multiple distributed data sources. Sig.ma provided an API for automatically integrating multiple data sources on the Web. The requested data sources describe information in RDF. A search in Sig.ma was initiated by a textual query from the user. Entities such as people, places, or products can be searched for. Results of a query are presented in aggregated form, that is, properties of the searched entity, such as a person, are presented in aggregated form from different data sources. For example, in a person search, information such as e-mail address, address, or current employer can be displayed. In addition to the actual information, links to the underlying data sources are also displayed to allow users to navigate to refine their search. Sig.ma also supported structured queries in which specific characteristics can be requested for an entity, such as contact information for a specific person.

Queries to data sources occur in parallel. The results from each data source in the form of RDF graphs are summarized by using properties of links in RDF data, such as owl:sameAs, or inverse-functional predicates. When searching data sources, techniques such as indexes, logical inference, and heuristics are used for data aggregation. OntoBroker⁶³⁶³63https://www.semafora-systems.com/ontobroker-and-ontostudio-x [39] and OntoEdit [142] are ontology editors with search and inference systems for ontologies. Using OntoBroker, complex queries over distributed Semantic Web resources, e. g., represented in OWL, RDF, RDFS, SPARQL, and also F-Logic) can be efficiently processed.

There is an increasing number of knowledge bases and representations of structured data. For example, the secondary database Wikidata⁶⁴⁶⁴64https://www.wikidata.org/wiki/Wikidata:Introduction/de [154]. A secondary database includes, in addition to the (actual) statements, relationships to their sources and other databases (called secondary information). Wikidata is a shared database between Wikipedia and Wikimedia. Wikidata mainly contains a collection of objects, which are represented as triples over the objects’ properties and the corresponding values. Semantic MediaWiki⁶⁵⁶⁵65https://www.semantic-mediawiki.org/wiki/Semantic_MediaWiki is an extension of MediaWiki. It serves as a flexible knowledge base and knowledge management system. Semantic MediaWiki extends a classic wiki with the ability to enrich content in a machine-readable way using semantic annotations.

Another knowledge base was Freebase⁶⁶⁶⁶66https://www.freebase.com, also an open and collaborative platform initiated in 2007 and acquired by Google in 2010. The content from Freebase was taken from various sources, including parts from the MusicBrainz ontology mentioned earlier. The success and widespread use of Wikidata prompted Google to migrate Freebase to Wikidata [143]. This strengthened the goal to develop a comprehensive, collaborative basis of structured data.

Google offers a semantic search function with Google Knowledge Graph⁶⁷⁶⁷67http://www.google.com/insidesearch/features/search/knowledge.html^,686868https://developers.google.com/knowledge-graph/. A knowledge graph, like an RDF graphs, is a set of triples representing links between entities. This forms a semantic database. Possible entity types are described on schema.org, among others. If a search term occurs in a query, the corresponding entity is searched for in the knowledge graph. Starting from this entity, it is then possible to navigate to further entities by means of the links.

A social network is essentially a graph in which connections are formed from users to other users, e. g., in the form of a friendship relationship or to events and groups. Facebook’s Graph API describes a programming interface to the Facebook Graph (called Open Graph). Within the graph, people, events, pages, and photos are represented as objects, with each object having a unique identifier. For example, https://graph.facebook.com/abba is the identifier of ABBA’s Facebook page. There are also unique identifiers for the possible relationship types of an object, which allow navigating from one object to all connected objects with respect to a particular relationship.

The Graph API allows one to navigate the Facebook Graph and read objects, including their properties and relationships to other objects, as well as creating new objects in the Facebook Graph and deploying applications. The API also supports requests for an object’s metadata, such as when and by whom an object was created.