Knowledge Graph OLAP

2.1.Background

Modern ATM aims to ensure safe flight operations through careful management, analysis, and advance planning of air traffic flow as well as timely provisioning of relevant information in the form of messages. The exchange of data/information between ATM stakeholders is of paramount importance in order to foster common situational awareness for improved efficiency, safety, and quality in planning and operations. In this regard, situational awareness refers to a “person’s knowledge of particular task-related events and phenomena” [78], i.e., knowledge about the world relevant for ATM, which must be accurately represented and conveyed to the various stakeholders. To this end, ATM relies on a multitude of standardized data/information (exchange) models, e.g., the Aeronautical Information Exchange Model (AIXM), the Flight Information Exchange Model (FIXM), the ICAO Meteorological Information Exchange Model (IWXXM), and the ATM Information Reference Model (AIRM).

Listing 1.

An example DNOTAM in XML notifying of a taxiway closure in Vienna due to snow removal

Among the most common types of messages exchanged in ATM are Notices to Airmen. A Notice to Airmen (NOTAM) – or Digital NOTAM (DNOTAM) when in electronic form using AIXM format – is a message that conveys important information about temporary changes in flight conditions to aircraft pilots [39], e.g., closures of aerodromes, runways, and taxiways, surface conditions, and construction activities (see [28] for a list of airport event scenarios) but also airspace restrictions. Messages shape the knowledge about the world as relevant for ATM. For example, a DNOTAM (Listing 1) may change the knowledge about the taxiways of a particular airport by announcing the temporary closure of a taxiway due to snow removal. To this end, a DNOTAM employs different time slices. A baseline timeslice defines the regular (baseline) knowledge whereas a tempdelta timeslice announces temporary changes of the baseline knowledge. Instead of the baseline, a DNOTAM typically employs snapshot timeslices, i.e., baseline blended with tempdelta knowledge. In the example DNOTAM in Listing 1, the encoded snapshot/baseline knowledge consists of the definition of the designator of Vienna airport (Lines 5–13) and the definition of various attributes of a taxiway at Vienna airport (Lines 17–27) per 12 February 2018 at 8:00 am. The tempdelta knowledge consists of the notification of a taxiway closure due to snow removal (Lines 29–50) on 12 February 2018 from 8:00 am to 10:00 am.

Fig. 2.

A contextualized KG based on the DNOTAM in Listing 1.

2.2.(Contextualized) ATM knowledge graphs

The knowledge encoded in DNOTAMs is more naturally represented using contextualized KGs [71]. Fig. 2 illustrates the contextualized representation of the knowledge encoded in the DNOTAM from Listing 1 along a temporal dimension. The all-date context defines general knowledge about various infrastructure elements, which hardly changes. The temporal context for the timespan from 8:00–10:00 am on 12 February 2018, on the other hand, defines knowledge about a temporarily reduced availability – a closed operational status – due to snow removal. Other context dimensions may also serve to organize ATM knowledge into contextualized KGs [71], e.g., geography, topic, and importance. Besides the knowledge derived from DNOTAMs according to the AIXM, an ATM KG may comprise knowledge from data items according to other ATM information (exchange) models, e.g., IWXXM for weather or FIXM for flight plans.

In our scenario, RDF serves as the common representation language for ATM knowledge even though XML is the native serialization format of DNOTAMs in the AIXM standard. AIXM, however, builds on the Geography Markup Language (GML), the initial proposal of which was based directly on RDF, with subsequent editions continuing to “borrow many ideas from RDF” [50, p. 20], including the GML’s object-property model [50, p. 16]. Similarly, other ATM information (exchange) models are easily translated into RDF.

In fact, ATM research has shown growing interest in the use of semantic technologies (see [40] for an overview), leading to the development of domain ontologies [33,85], e.g., the NASA ATM Ontology (ATMONTO) [42] and the AIRM Ontology [86]. NASA’s ATMGRAPH [41,43], in turn, is a KG for the ATM domain that builds on ATMONTO and comprises knowledge about infrastructure, flights, and operating conditions. The rationale behind ATMGRAPH lies in the integration of heterogeneous data from various sources for analysis purposes. Compared to a data lake solution storing raw files from various data sources [25], which shifts the burden of data integration largely to analysts, ATMGRAPH facilitates querying across sources [44, p. 2]. Using semantic technologies was also deemed preferable over a relational implementation due to increased flexibility regarding modifications, possibility of inferencing, and reusability of the knowledge [44, p. 3]. In summary, employing (contextualized) KGs for aeronautical information management seems promising.

In the remainder of this paper, we use example KGs for illustration purposes largely following the AIXM conceptual models [1] and the FAA’s airport operations scenarios [28]. In the following, we present two use cases for contextualized KGs in the ATM domain, which serve to motivate the KG-OLAP approach.

2.3.Use case 1: Pilot briefings

Prior to a flight, pilots receive a pre-flight information bulletin (PIB), which comprises all DNOTAMs, but also METARs, i.e., messages about weather conditions, that are even remotely relevant for the upcoming flight. Pilots then have to manually sift through an abundance of messages and decide upon the priority of each message. Among other things, the priority of a message depends on the current flight phase. For example, during take-off, a taxiway closure at the destination airport has low priority for a pilot.

Automated rule-based filtering and prioritization of DNOTAMs reduces information overload in pilot briefings [79]. Pilots formulate an interest specification [14], which comprises spatial, temporal, and aircraft interests [15]. The SemNOTAM system then matches DNOTAMs against the interest specification and assigns an importance, e.g., flight critical or operational restriction, to each DNOTAM. DNOTAMs are also classifed according to geographic scope and flight phase (spatio-temporal) as well as event scenario. The general approach is also applicable to other types of ATM information, e.g., METARs, provided appropriate filtering and prioritization rules are available.

The result of DNOTAM filtering and prioritization may be packaged into a semantic container [61]. A semantic container collects data items into a package that comprises all the data items satisfying a certain membership condition, formulated in terms of an ATM domain ontology. A membership condition may have multiple facets, e.g., geography, time, aircraft, and importance. Semantic containers foster reuse of previously compiled packages of ATM information, thus reducing processing effort, and allow for replication in order to increase availability and conserve bandwidth. Raw data items, not knowledge triples, constitute the contents of a semantic container. For example, a semantic container may comprise the relevant DNOTAMs for a flight from Dubai to Vienna on a particular day, along with additional information about the importance of each individual DNOTAM.

Automated rule-based filtering and prioritization in combination with semantic containers may serve to construct ATM information cubes [72,73]. Fine-grained semantic containers comprising data items of different geographic and temporal scopes as well as importance levels may be arranged in a multidimensional space. A pilot could then select the appropriate containers at the right moment without being overloaded with information. Individual messages could be combined into a more abstract representation in order to obtain a management summary of relevant events. Runway closures at the destination airport, for example, may be flight critical and pilots should be aware of the fact that there are closures in effect at the destination also in the early phases of a flight, possibly with a general indication of the reason for closure, e.g., due to snow. In detail, however, the runway closures concern the pilot only upon approach of the destination, e.g., which runway directions are closed, which types of snow are found on the runways.

In this paper, rather than considering ATM information cubes with messages collected into semantic containers, we consider cubes of ATM knowledge. More general contexts establish a common schema and business term vocabulary, which is inherited and extended by the more specific contexts. The messages represent a source of knowledge about the state of the world with limited spatial, temporal, and content scope. The information contained in the messages translates into knowledge triples that are collected into contexts based on the scope of the messages.

2.4.Use case 2: Post-operational analysis

Air traffic flow and capacity management (ATFCM), which represents one of the core activities in ATM, has post-operations teams analyzing operational events in order to identify valuable lessons learned for the benefit of future operations and produces an overview of occurred incidents [62, p. 131]. A data warehouse provides the post-operations team with statistical data about past flight operations [62, p. 130].

Post-operational analytical tasks in ATFCM may also leverage contextualized ATM knowledge. The rationale is similar to ATMGRAPH’s [44], a KG having richer semantics while being more flexible and versatile than simple statistical data organized in a data warehouse. In addition to the data warehouse, the post-operations team may employ a KG-OLAP cube of contextualized ATM knowledge extracted from DNOTAMs and other types of messages, organized by temporal relevance, route or ground segment, aircraft model, and importance. By analyzing such ATM knowledge, an air traffic flow post-operations team may gain a more comprehensive picture of past air traffic operations. Using the merge operation, the post-operations team may combine ATM knowledge from different contexts. For example, the relevant ATM knowledge per day and geographic segment could be combined to obtain the ATM knowledge per month and geographic region and month. Various incarnations of the abstraction operation then serve to obtain a more abstract representation of the ATM knowledge. For example, instead of indicating specific closures of individual runways or taxiways, the abstract ATM knowledge would indicate closures of runways and taxiways in general for aircraft with certain characteristics. Besides DNOTAMs, other types of aeronautical information relevant to ATFCM, e.g., flight data in FIXM and meteorological messages in IWXXM, could similarly serve to populate the cube of ATM knowledge.

In the remainder of this paper, we employ contextualized KGs for the ATM domain to illustrate the KG-OLAP approach. In particular, we focus mainly on ATM knowledge derived from DNOTAMs. The example contextualized KGs are plausible for both pilot briefings and post-operational analysis.

2.5.Functional requirements

Based on the presented use cases from the ATM domain, we identify functional requirements that a system for performing data analysis over KGs must fulfill. Although derived from use cases in ATM, the requirements also apply to other use cases, e.g., the analysis of business situations formalized using business model ontologies [74].

In the following, we formulate the KG-OLAP cube model and query operations guided by the identified functional requirements.

3.1.KG-OLAP cube model

KG-OLAP adapts the multidimensional modeling paradigm from data warehousing (see [83]) in order to organize multidimensional KGs. Hence, the KG-OLAP cube is the central modeling element. Following the basic structure of the CKR framework, the KG-OLAP cube consists of two distinct layers: an upper and a lower layer. The upper layer describes the structure and properties of a cube’s cells; the lower layer specifies the contents of the cells. The two layers employ distinct and possibly disjoint languages.

A KG-OLAP cube’s upper layer defines the multidimensional structure of a cube and associates specific knowledge modules with individual cube cells. Intuitively, the cube’s dimensions (e.g., time, location) span a multidimensional space, the points of which are referred to as cells.11 The dimensions are hierarchically organized into levels. The definition of a cube’s dimensions and their hierarchical organization – the cube’s multidimensional structure – into levels is referred to as KG-OLAP cube schema.

Fig. 3.

A KG-OLAP cube with its dimensions and levels in DFM notation for the organization of KGs in air traffic management.

The dimension members (e.g., February 2020, Vienna) of a KG-OLAP cube are organized in a complete linear order, which is referred to as roll-up relationship. For example, the month February 2020 rolls up to the year 2020 and Vienna rolls up to Austria. Dimension members belong to levels, which define the granularity of the dimension members (e.g. month and year, country and city). The levels serve to aggregate individual cells of a cube (see Section 4). Levels are likewise organized in a complete linear order, which is similarly referred to as roll-up relationship. For example, month rolls up to year and city rolls up to country.

Fig. 4.

Example hierarchies for the context dimension members.

Fig. 5.

An example instance of the KG-OLAP cube schema in Fig. 3. The arrows denote coverage relationships between contexts; the covered context points to the covering. The contents of the knowledge modules K0-K7 are defined in Fig. 6.

The dimension members characterize the cells of a KG-OLAP cube: each cell has a set of dimension members as identifying attributes and the dimension hierarchies organize the cells into a hierarchical structure. For example, the combination of dimension members February 2020 and Austria identifies a particular cell in a two-dimensional cube with time and location dimensions. The hierarchical order of dimension members then determines the coverage relationship, which is a partial order between cells. For example, the cell identified by the combination of dimension members February 2020 and Austria covers the cell identified by the combination of dimension members 12 February 2020 and Vienna. With each cell, a KG-OLAP cube then associates a knowledge module, which comprises facts of knowledge valid in the respective context.

A KG-OLAP cube’s lower layer consists of the actual knowledge modules that are associated with the individual cells. A knowledge module contains statements valid in the context of the associated cell. The knowledge inside each module is specified using an object language and expresses the facts and axioms valid in the specific context defined by the cell. Furthermore, knowledge propagates downwards along the coverage relationships, from the more general to the more specific contexts. In the examples, we employ SROIQ-RL as the object language, which corresponds to the OWL 2 RL profile, as it will be the language of reference for our formal definition of reasoning in Section 3.2.3. We note, however, that our approach is agnostic to the language chosen for the representation of local knowledge.

Fig. 6.

Example contents of the KG-OLAP cube cells in Fig. 5.

Example 4 illustrates how knowledge representation in KG-OLAP fulfills the functional requirements defined in the previous section. First, the represented KGs are heterogeneous (Requirement 1) regarding both the types of entities and relationships; schema variability is exemplified by the different variants of ManoeuvringAreaAvailability. The KGs comprise ontological knowledge (Requirement 2), mainly in K0, which defines properties and classes, but notably also in K1, which contains the definition of a business term, namely HeavyWakeCharacteristic, denoting the characteristic of aircraft with heavy wake turbulence. The contents are self-describing (Requirement 3), the schema information and ontological knowledge being a flexible part of the data. Knowledge is modularized (Requirement 4), namely along the context dimensions. The modules have different levels of generality (Requirement 5): K0 comprises knowledge that is generally applicable, the other modules comprise gradually more specific knowledge. For example, K1 comprises quite general knowledge for the LOVV region whereas K2–K7 have more limited scopes of applicability.

The knowledge from higher-level cells propagates to the covered lower-level cells; the knowledge associated with the lower-levels cells also specializes the more general knowledge inherited from the higher levels. The hierarchical organization facilitates the combination of knowledge across cells in the course of data analysis: the higher-level facts contain a shared conceptualization of business terms that may be extended by lower-level facts. The actual contents of lower-level cells are defined in terms of the shared conceptualization provided by the higher-level facts. The propagated knowledge is also available for reasoning.

3.2.Formalization

In the following, we adapt and extend the definitions of the CKR framework – building on the CKR definition [8,12] in a generic description logic (DL) language [4] – in order to fit the needs of KG-OLAP and its query operations (see Section 4).

3.3.Extensions

The presented KG-OLAP model can be extended in several directions in order to increase flexibility. In the following, we briefly identify possible extensions.

As in the underlying model of CKR, the KG-OLAP model assumes a centralized view on the available data: The structure of the cube and the knowledge associated to each cell is assumed to be locally available in a single knowledge base for the application of reasoning and operations on the cube. Thus, a possible extension, supported by the modular nature of the cube model, concerns the distribution of the cube structure over separate knowledge bases. This would require to revise the formalization so that both the meta and object information are distributed across more local knowledge bases and knowledge is propagated also considering the topology of the distributed knowledge bases (e.g., by introducing an additional “distribution” dimension). The reasoning procedures and OLAP operations on such distributed system have to be consequently adapted to the distributed structure and the intended knowledge propagation across local knowledge bases. On the other hand, the modularization of knowledge bases can represent an advantage to limit the load of reasoning tasks and to restrict application of operations to a limited subset of cells.

In the proposed KG-OLAP model, we assume that all the dimensions and dimensional values are known a priori and thus no context is undefined (but may have an empty module). The KG-OLAP model could be extended to consider updates of dimensions and dimensional values, which necessitate the dynamic reorganization of knowledge in the contexts that are identified by the newly introduced dimensional values. Updates of the dimensions and their dimensional values will typically be limited to extending the hierarchy with new branches rather than modifying the existing dimensional values. In this regard, however, the notion of “slowly-changing dimensions” from traditional data warehousing (see [83, pp. 139–145] for further information) may be adopted in KG-OLAP. Furthermore, in some cases, it may not be possible to determine the right dimensional value for the statements. The KG-OLAP model allows for the introduction of “unknown” or “not applicable” members in the dimensions. For example, there could be a cell containing knowledge of unknown importance, a cell containing knowledge of unknown temporal or spatial applicability. Future work may investigate the different notions and implications of such default members in the dimension hierarchies.

We note that, due to the modular structure of the model, concepts in different cells can assume different interpretations: the particular situation identified by a cell can determine the local meaning of a concept, reflecting the contextual view of the model. In this regard, we refer to the eval operator for the local propagation of knowledge [12].

The concepts that are propagated from the higher to the lower cells are assumed to be refined by the knowledge in the lower cells. Such refinement is necessarily monotonic, as the knowledge in the lower-level cells cannot truly “override” the concept definitions from the higher-level cells. In this direction, in the CKR model, a notion of defeasible axiom has been recently introduced: Defeasible axioms hold in general but can be “overridden” by the instances in the lower contexts of a contextual hierarchy [8,9,13]. Likewise, defeasible axioms could be introduced in KG-OLAP.

For the presented definition of the KG-OLAP model we consider a simple hierarchical organization of dimensional values, which can be divided into levels, i.e., ranked hierarchies [13]. While this provides an intuitive organization of the cube structure, such organization might be relaxed to allow for multiple relations and more general definitions of hierarchies. In this regard, an extensive body of research in data warehousing and OLAP is dedicated to investigate different kinds of hierarchies (see [83, pp. 94–106]), which could be adapted for the KG-OLAP framework. Regarding the CKR model, propagation of knowledge (with defeasible inheritance) in general contextual hierarchies has been studied by Bozzato et al. [10].

4.1.Contextual operations

The contextual operations select and combine cells of a KG-OLAP cube, thus satisfying Requirement 6, using its dimensions and levels. The slice-and-dice operation allows for the selection of a set of facts whereas the merge operation combines cells at finer granularities into aggregated cells at a coarser granularity, merging the contents of the modules from the finer-grained cells.

4.1.1.Slice and dice

The slice-and-dice operation restricts a cube to a set of cells with a specific subset of dimension attribute values; the operation selects a subcube of an input KG-OLAP cube. The slice-and-dice operation selects a partition of the cube for subsequent manipulation. Note that slice-and-dice operations in data warehousing literature and practice come in various forms. The definition in this section establishes a basic notion of slice-and-dice for KG-OLAP cubes. Future work may well extend this notion to provide rich query mechanisms in order to filter contexts based on complex conditions in an expressive domain ontology.

Definition 4

Definition 4(Slice and dice).

Given a cube K=⟨G,KM⟩ and a dimensional vector d‾ which defines the dice coordinates, we define the slice-and-dice operation δ(K,d‾) of K with respect to d‾ as a new cube K′=⟨G′,KM′⟩ over ⟨Γ′,Σ⟩, such that:22

• – M′=M, D′=D, and for each A∈D, LA′=LA;

• – For each A∈D, DA′={dA′∈DA∣dA′⪯dA or dA⪯dA′, with dA∈d‾};

• – F′={c∈F∣ for each dA∈cn−(c),dA∈DA′};

• – G′=GΣ∪GΓ′ (i.e., metaknowledge in G′ is equal to the formulas in GΓ that have only symbols in Γ′).

Fig. 7(a) depicts the definition of slice-and-dice operation on a one-dimensional cube. Intuitively, the slice-and-dice operation takes as argument the coordinates of a point in the cube, i.e., a dimensional vector d‾, and produces a new cube by extracting all cells, along with their associated knowledge modules, at points underneath the argument point as well as the cells that are in a coverage relationship with those cells at points underneath the argument point.

Fig. 7.

Illustration of contextual operations definitions.

Fig. 8.

Applying slice-and-dice and merge operations on the KG-OLAP cube instance from Fig. 5. Gray lines denote contexts that are disregarded by the slice-and-dice operation δ(KATM,{Importance:=Essential,Location:=LOWW,Date:=All-date,Aircraft:=FixedWing}), with the unnamed context shown as shaded box denoting the dice coordinates, and the dashed box denotes a merge of contexts ρ∪(KATM′,{package,segment,month,type}) into the c8 context.

Example 6

Example 6(Slice and dice).

Fig. 8 illustrates the application of the slice-and-dice operation on the KG-OLAP cube from Fig. 5, which we denote by KATM. The context shown as shaded box represents the dice coordinates {Importance:=Essential,Location:=LOWW,Date:=All-date,Aircraft:=FixedWing}. Only cells that are underneath the point identified by the dice coordinates, i.e., c4, c5, and c6, or cells that are in a coverage relationship with c4, c5, and c6, i.e., c0, c1, and c3 are kept in the result cube KATM′; the disregarded cells are shown in gray color.

In data warehousing, conceptual multidimensional models typically distinguish between dimensional attributes and non-dimensional attributes (see [30]). While the dimensional attributes identify the cell, non-dimensional attributes provide additional information that can be used for selection. Similarly, KG-OLAP cubes could be extended with non-dimensional attributes to allow for additional variants of the slice-and-dice operation.

4.2.Graph operations

Graph operations – abstraction, pivoting, and reification – alter the structure of the KGs inside the knowledge modules of a cell, thus satisfying Requirement 7. Abstraction replaces sets of entities with individual and more abstract entities. Pivoting moves metaknowledge (contextual information) inside the modules. Reification allows to represent relations as individuals.

4.2.1.Abstraction

Abstraction serves as an umbrella term for a class of graph operations that, broadly speaking, replace entities in an RDF graph with more abstract entities. This abstraction is based on various types of ontological information, e.g., class membership and grouping properties. We also refer to abstraction as ontological roll-up.

We distinguish three types of abstraction: (a) triple-generating abstraction generates new triples from existing triples, where an existing individual acts as abstraction of a set of other resources; (b) individual-generating abstraction generates a new individual that acts as abstraction of a set of resources; (c) value-generating abstraction computes a new value using some aggregation operation on a set of values.

Consider the set of asserted and inherited modules of a cell c: mod(c)={m∈M∣G⊧mod(c,m)}. We then denote the local knowledge base of cell c as:

Kmod(c)=⋃m∈mod(c)Km

Definition 6

Definition 6(Abstraction).

Given a cube K=⟨G,KM⟩, a context name c∈F, a (possibly complex) concept C of LΣ restricting abstraction to a subset of individuals, a (possibly complex) role S of LΣ – the grouping property – we define the abstraction operation αmet(K,c,C,S) as a new cube K′=⟨G′,KM′⟩ over ⟨Γ′,Σ′⟩, with met∈{T,I,V(op)} for the specific abstraction method (triple, individual or value generation), where the local knowledge module Kmod(c) is modified as follows, depending on the abstraction method:

• – M′=M∪{mg(c)}∖mod‾(c), with mg(c) a new module name and mod‾(c) the set of asserted modules of c in the original cube;

• – G′=G∪{mod(c,mg(c))}∖{mod(c,m)∣m∈mod‾(c)};

• – Kmg(c)=Kmod‾(c) and KM′=KM∪{Kmg(c)}∖{Kmod‾(c)};

• – triple generation T: for b∈NIΣ with Kmod(c)⊧C(a), let S−(b)={a∈NIΣ∣Kmod(c)⊧S(a,b)}; then:

  • ∗ for every role assertion R(a,c)∈Kmg(c) with a∈S−(b) and R≠S, add R(b,c) to Kmg(c) and remove R(a,c) from Kmg(c);

  • ∗ for every role assertion R(c,a)∈Kmg(c) with a∈S−(b) and R≠S, add R(c,b) to Kmg(c) and remove R(c,a) from Kmg(c);

• – individual generation I: for a∈NIΣ with Kmod(c)⊧C(a), let S(a)={b∈NIΣ∣Kmod(c)⊧S(a,b)}; then:

  • ∗ for every b∈S(a), add grouping(a,gb) to Kmg(c) with gb∈NIΣ′ a new individual name (associated with the grouping individual b);

  • ∗ for every role assertion R(a,c)∈Kmg(c), for every b∈S(a), add R(gb,c) to Kmg(c) and remove R(a,c) from Kmg(c);

  • ∗ resp. for every R(c,a) and C(a)∈Kmg(c).

• – value generation V(op): for a∈NIΣ with Kmod(c)⊧C(a), considering the operation op on values in the range of S, let S(a)={v∈NIΣ∣S(a,v)∈Kmg(c)}, then:

  • ∗ add to Kmg(c) the assertion S(a,op(v1,…,vm)) with {v1,…,vm}=S(a);

  • ∗ remove every S(a,v)∈Kmg(c) with v∈S(a).

Note that for simplicity we treat literal values as individuals and we do not distinguish roles across individuals and values in our language. We note that rdf:type may serve as a grouping property, provided that (newly introduced) grouping individuals represent the concepts employed for grouping and that the management of these grouping individuals is taken care of (cf. OWL punning [22]). Individual-generating abstraction may be extended for multiple grouping properties. Moreover, we note that the grouping role S is allowed to be a complex role expression, thus permitting to group, e.g., along role compositions.

Fig. 9.

Illustration of abstraction operations definitions.

Fig. 9 shows a graphical representation for definitions of the abstraction operations. Intuitively, the abstraction operation takes as input the single cell, on the knowledge module of which the operation is applied, a class C of individuals to be abstracted, and a property S, which represents the grouping relation along which the elements have to be abstracted. The kind of manipulation on the cell’s knowledge then depends on the abstraction type: (a) in triple-generating abstraction, for every instance C(a), if there is some relation of the kind S(a,b), i.e., a is “grouped” into b, then all of the role assertions of the kind R(a,c) or R(c,a) are redirected to the grouping individual b; (b) in individual-generating abstraction, for every instance C(a), if there is some relation of the kind S(a,b) then a new grouping individual gb and assertion grouping(a,gb) are added, and all of the ABox assertions of the kind R(a,c), R(c,a) and A(a) are redirected to gb; (c) in value-generating abstraction, for every element C(a), we consider all of the values v1,…,vm that are related to a by role S and we add their aggregation op(v1,…,vm) by a parameter operator op as a new S value for a.

The definition of individual-generating abstraction can be easily extended to allow for multiple grouping properties. For example, in individual-generating abstraction, given grouping relations S1 and S2, for every instance C(a), if there is some relation of the kind S1(a,m) and some relation of the kind S2(a,n), a new grouping individual gmn and assertion grouping(a,gmn) are added, and all of the ABox assertions of the kind R(a,c), R(c,a) and A(a) are redirected to gmn. The definition of individual-generating abstraction could be defined as follows: instead of a single grouping property S, the individual-generating abstraction would have roles S1,…,Sk as grouping properties. Then, for every a∈NIΣ with Kmod(c)⊧C(a), and for every j∈{1,…,k}, let Sj(a)={b∈NIΣ∣Kmod(c)⊧Sj(a,b)}. For every b∈S1(a)×⋯×Sk(a) add grouping(a,gb) to Kmg(c) with gb∈NIΣ′ a new individual name (associated with the grouping tuple b). For every role assertion R(a,c)∈Kmg(c), for every b∈S1(a)×⋯×Sk(a) add R(gb,c) to Kmg(c) and remove R(a,c) from Kmg(c); resp. for every R(c,a) and C(a)∈Kmg(c).

Fig. 10.

Examples of triple-, individual-, and value-generating abstraction.

Example 8

Example 8(Abstraction).

Fig. 10 illustrates the different variants of abstraction on the running example of ATM knowledge graphs. Take the K4 module of the c4 context of KATM from Fig. 6, which contains an example of taxiway contamination. Assume that the K4 module also contains a runway contamination with compactSnow, which is a kind of snow. The RDF graph at the bottom of Fig. 10 then illustrates those contents. First, a triple-generating abstraction αT(KATM,c4,⊤,kindOf) leads to the replacement of individuals drySnow and compactSnow with snow, using kindOf as grouping property. Let KATM′ denote the cube resulting from the previous triple-generating abstraction. Second, over that cube, an individual-generating abstraction αI(KATM′,c4,SurfaceContaminationLayer,contaminationType) then groups all SurfaceContaminationLayer individuals with the same contaminationType property value; the grouping property indicates which individuals have been grouped. The new individual assumes the place of the grouped individuals in the graph. Let KATM″ denote the cube resulting from the individual-generating abstraction. Third, another individual-generating abstraction αI(KATM″,c4,SurfaceContamination,layer) groups all SurfaceContamination individuals with the same layer property value. Let KATM‴ denote the cube resulting from that individual-generating abstraction. Fourth, a value-generating abstraction αV(avg)(KATM‴,c4,SurfaceContamination,depth) replaces multiple depth property values (0.2 and 0.4) by the average depth (0.3). Let KATM′′′′ denote the cube resulting from that value-generating abstraction. A final individual-generating abstraction αI(KATM′′′′,c4,Runway⊔Taxiway,contaminant) then groups all Runway and Taxiway individuals with the same contaminant property value, which after the previous individual-generating abstraction means taxiway10/004 and runway16/34. In this case, a complex concept Runway⊔Taxiway determines which individuals are candidates for abstraction. The result graph indicates, at an abstract level, the presence of snow contamination at runways and taxiways along with the average depth of contamination.

The grouping role S can be an inverse role as well as a composite (complex) role. For example, in order to perform an individual-generating abstraction that groups SurfaceContaminationLayer individuals by the infrastructure element they belong to, the composite role layer−∘contaminant− may serve as a grouping property. Similarly, a triple-generating abstraction could replace entities by another entity reached via a property path, e.g., using composite role kindOf∘kindOf to replace one entity by another two steps up the kindOf hierarchy. SPARQL-like property paths with wildcard operators could also be introduced.

Additional variants of the abstraction operation can be defined in order to adapt the concept of abstraction to the structure of the object knowledge. For example, in individual-generating abstraction, we consider an explicit grouping relation to be introduced between grouped individuals and the newly introduced group individual. The grouping may also be realized with the introduction of a new class representing the abstraction, with class membership assuming the role of the grouping relation.

We note that KG-OLAP, in general, aims at being independent from the specific ontology language chosen for the representation of local axioms and assertions. If an ontology language were employed that could express the semantics of the abstraction operations (or some variant), that ontology language, in conjunction with an automated reasoner, could serve to implement the abstraction operations. Regardless, in the case of OWL, reasoning alone cannot serve to implement the abstraction operations. For example, in case of individual-generating abstraction, since OWL does not support grouping of individuals by property value when that value is a variable, extralogical steps must be followed in addition to reasoning. In Example 8, membership reasoning for the complex concept ∃contaminationType.{snow} could serve to obtain all the individuals which have the same value snow for the contaminationType property. In OWL, snow could not be replaced by a variable, though. In order to perform individual-generating abstraction, membership reasoning would have to be performed for multiple complex concepts, replacing the constant snow with other possible types of contamination. Suppose slush and ice are the other types of contamination. Then, in order to group layers by contamination type, membership reasoning for ∃contaminationType.{slush} and ∃contaminationType.{ice} would have to be performed as well. For each of those concepts, an individual would have to be created that represents the group of members that belong to the respective concept; alternatively, the concepts could be named and used as group individuals (OWL punning). Finally, each individual representing a group would replace the individuals belonging to that group in the KG.

4.2.2.Pivoting

The pivoting operation attaches dimensional properties (dimension attribute values) of a cell to a specified set of individuals inside the cell’s object knowledge. Pivoting allows for the preservation of contextual knowledge in case of a merge operation.

Definition 7

Definition 7(Pivoting).

Given a cube K=⟨G,KM⟩, a cell name c∈F, a (possibly complex) concept C of LΣ of the objects to be labeled, and a set D={A1,…,An}⊆D of the selected set of dimension labels, we define the pivoting operation π(K,c,C,D) as a new cube K′=⟨G′,KM′⟩ over ⟨Γ′,Σ′⟩ s.t.

• – M′=M∪{mg(c)}, with mg(c) a new module name;

• – G′=G∪{mod(c,mg(c))};

• – KM′=KM∪{Kmg(c)};

• – for every e∈NIΣ with Kmod(c)⊧C(e), we add to Kmg(c) the set of assertions A1(e,dA1),…,An(e,dAn) if G⊧A1(c,dA1),…,An(c,dAn).

Note that we have to admit that Σ∩Γ≠∅ in order to use metaknowledge symbols in the local object knowledge. Fig. 11 shows an illustration of the pivoting operation definition. Intuitively, the pivoting operation takes as input a cell c and as parameters a class C as well as a set of dimensions D. The operation associates with c an additional knowledge module mg(c) that contains, for each element e of argument class C in c, a set of assertions that label the element e with the dimension attribute values of c associated with the argument dimensions in D⊆D.

Fig. 11.

Illustration of the pivoting operation definition.

Example 9

Example 9(Pivoting).

Consider the K4 module of the c4 context from Fig. 6. The pivoting operation π(K,c4,SurfaceContamination,{Importance,Date}) then returns a new cube K′ with a knowledge module mg(c4) that contains the additional assertions Im-portance(taxiway10/004-contam#101,Essential) and Date(taxiway10/004-contam#101,12-02-2020).

5.1.Design and implementation

A mapping of the formal language to an actual RDF representation allows for the storage of KG-OLAP cubes in off-the-shelf quad stores with SPARQL realizations of the query operations. Context-aware rules serve to materialize roll-up relationships for levels and cells as well as inference and propagation of knowledge. Details about logical model, reasoning and queries are provided in Section 4 of the Appendix [70].

Architecture For each KG-OLAP cube, a base repository in a quad store comprises the cube knowledge (structure) and object knowledge (contents) for the cube. Using the slice-and-dice operation, the user selects a subset of the base data into a temporary repository, which then contains a working copy of the original data that can be modified using merge and abstraction.

Logical model The definition of the KG-OLAP model primitives (e.g., cell/fact, dimension, dimension members) can be easily defined in terms of RDF/OWL classes and properties. The two-layered structure of the KG-OLAP system with a global context and multiple local contexts – as in the CKR core [12] – is realized in RDF using different RDF graphs – one graph for the global knowledge and one graph for each knowledge module as well as a graph for the materialized inferred knowledge of each module.

Reasoning The reasoning procedure presented in Section 3.2.3, analogously to the CKR core [12], can be implemented using SPARQL-based forward rules that materialize the inferences, including coverage relationships between contexts. The KG-OLAP implementation employs the RDFpro framework [21] for rule execution. RDFpro supports the specification of SPARQL-based rules over multiple graphs, a feature required for reasoning inside individual cells as well as across different cells.

Queries The query operations introduced in Section 4 can be implemented using SPARQL queries. In particular, the query operations translate into SPARQL SELECT statements that return “delta” tables which consist of quads along with an indication of the operation (insert or delete). The delta tables can then be applied to the temporary repository.

5.2.Performance evaluation

In the following, we analyze performance of the core set of KG-OLAP cube operations – i.e., slice-and-dice, merge union, and abstraction. Specifically, we look at median run times for the computation of the query operations’ delta statements, i.e., the statements that must be inserted or deleted in order to perform the respective query operation, measured over multiple iterations, relative to repository size (number of statements), context size (number of contexts), and delta size (number of computed delta statements). We do not include the duration of actual insertions or deletions of the delta statements in the run times since these are not specific to contextualized KGs.

The performance experiments employed synthetic datasets based on the ATM scenario used throughout the paper, which allowed us to vary the number of dimensions, contexts, and statements while keeping the graphs similar. The generated contexts contain knowledge about airports, runways and taxiways, warnings, temporary closures of runways and taxiways for different aircraft characteristics based on weight or wingspan, layers of surface contamination with the depth of each layer, and navigation aids with their frequencies. Query operations ran on three-dimensional and four-dimensional datasets with 1365, 2501, and 3906 contexts, respectively. The contexts were not all on the same granularity but distributed over five different granularity levels (not including the root context), where the number of contexts per granularity level gradually increased with the depth; the majority of the contexts were on the most specific granularity level (see Section 5.2 of the Appendix [70] for details). Some entities were shared between contexts at different granularities to accurately study the effect of knowledge propagation. Context size was varied by adding/removing branches in the context hierarchy. In turn, for each dimensionality and context size there were three different repository sizes. In order to make for more realistic datasets, repository size was varied by increasing the number of airports, runways and taxiways, warnings, etc. per context, dependent on the granularity level, not by randomly distributing statements across contexts, which due to the structure of the context hierarchy results in differences in the repository sizes between context sizes. Additional “baseline” datasets were used in the experiments involving abstraction operations, which consisted of a single context, in order to investigate the impact of contextualization on query processing.

We remark that designing performance experiments after existing benchmarks for traditional OLAP, e.g., TCP-DS,44 would not give an accurate idea of the inherent complexity of KG-OLAP cube maintenance and query operations due to the different nature of the involved data and the queries. Traditional OLAP operates on numeric data, and does not fulfill Requirements 1–3 as well as Requirement 5 described in Section 2.5. While it would be possible to model numeric data using RDF and analyze those data using SPARQL, it would be beside the point to measure performance of atypical uses of KG-OLAP. Furthermore, related work on OLAP and information networks that aims at performance optimization, e.g., [88,89,91], does not (wholly) fulfill the requirements described in Section 2.5 (see also Section 6.3), rendering those approaches incomparable to KG-OLAP in terms of performance. Related work on ATM KGs conducting performance evaluation [44] runs general SPARQL queries over large RDF datasets but does not feature modularization (Requirement 4). Those SPARQL queries cannot be reasonably adapted to queries over multiple modules, and running SPARQL queries over a single context would only serve to replicate the results of related work, which depend on the experimental setting and require the same datasets to be used, which are not public. Finally, in this paper, we do not aim at performance optimization. Rather, we investigate complexity of KG-OLAP cube maintenance and query operations to inform future optimization efforts.

Fig. 13.

Performance of contextual operations.

The performance experiments were conducted on a virtual CentOS 6.8 machine with four cores of an Intel Xeon CPU E5-2640 v4 with 2.4 GHz, hosting a GraphDB55 8.9 instance. The Java Virtual Machine (JVM) of the GraphDB instance ran with 100 GB heap space. The JVM running the KG-OLAP system, which conducts rule evaluation, prepares queries, and caches query results, ran with 20 GB heap space.

The GraphDB instance comprised two repositories – base and temporary – with the following configuration (see [63] for further information). The entity index size was 30000000 and the entity identifier size was 32 bits. Context index, predicate list, and literal index were enabled. Reasoning and inconsistency checks were disabled; the KG-OLAP implementation takes care of reasoning via RDFpro rule evaluation.

Fig. 13(a) shows run times of the slice-and-dice operation. The plot on the left shows run time relative to repository size per dimensionality. The plot in the middle shows run time relative to repository size per context size. The plot on the right shows run time relative to the size of the delta table computed by the query operation. Hence, performance of the slice-and-dice operation primarily depends on the number of delta statements in the query result, i.e., the number of selected cells/statements from the base repository. In fact, in this example, the slice-and-dice operation performs better on the large context size (3906 contexts) due to fewer delta statements being computed because of the distribution of the statements across the contexts. Dimensionality does not play a role here. In summary, slice and dice does not involve any complex computations, consisting only of the selection of relevant contexts and their contents.

Fig. 14.

Performance of abstraction operations.

In case of the merge operation, in order to study worst-case performance, we deliberately chose dataset and formulation of the merge operation such that the result would be an almost complete reorganization of the contexts in the KG-OLAP cube. The lower-level cells contain the majority of statements, which are all affected by the merge operation. The complexity of the chosen operation is evidenced by the delta size, which is about twice the repository size: the merge operation first removes the statements from the merged cells only to insert those statements again into higher-level cells. The run time of the merge union operation, as shown in Fig. 13(b), primarily depends on the number of contexts. For each context size, we observe a linear increase in run time with respect to the repository size. For the large context size (3906 contexts) there is also a marked influence of dimensionality on run time.

Fig. 15.

Performance of rule evaluation.

For performance evaluation of the abstraction operations, we employ, on the one hand, baseline datasets which consist of a single context comprising all statements in order to gain an understanding of the inherent complexity of these operations regardless of contextualization. Such abstraction operations on a single context correspond to the formalization. On the other hand, we perform abstraction operations in a variant that performs the abstraction to each cell at a particular granularity level. Similar to the merge operation, we deliberately choose a setting where the query operations affect a large number of statements in order to study worst-case performance.

Fig. 14(a) shows run times of triple-generating abstraction. Run time grows linearly with repository size. Run times for individual-generating abstraction with a single grouping property are similar, as shown in Fig. 14(b). For triple-generating abstraction, the baseline datasets had significantly higher run times. The difference was less pronounced for individual-generating abstraction.

For value-generating abstraction, the queries resulted in smaller sizes of the computed delta tables. Fig. 14(c) shows that the run time of value-generating abstraction grows about linearly with respect to repository size with a small influence of context size and little influence of dimensionality. Run times for the baseline datasets were smaller. We note that the run times of value-generating abstraction were in general quite low.

For results of reification and pivoting operations we refer to Section 4.5.6 and Section 4.5.7, respectively, of the Appendix [70]. In summary, the reification operation grows linearly with the repository size. For the pivoting operation we observe context size as the main factor influencing run time.

The proof-of-concept implementation relies on materialization of coverage relationships and inferences, which requires evaluation of a set of rules over the base repository in order to initialize the KG-OLAP cube. Fig. 15 shows run times for the evaluation of different rulesets relative to the repository sizes before and after reasoning – input and output repository size, respectively – as well as number of contexts for three-dimensional and four-dimensional KG-OLAP cubes. Reasoning in the performance experiments was conducted with the entire repository loaded into main memory first. Performance of two different rulesets was evaluated. The first ruleset, at the local level, i.e., within each context, performs membership reasoning under consideration of subclass relationships. For example, if Runway is a subclass of RunwayTaxiway and the fact Runway(runway16/34) is known, then RunwayTaxiway(runway16/34) is inferred. The second ruleset considers subclass relationships as well as domain and range of the properties. For example, if AirportHeliport is the range of the isSituatedAt property, and isSituatedAt(runway16/34,airportLOWW) is known, then AirportHeliport(airportLOWW) can be inferred. Fig. 15(a) shows the results for the first ruleset, Fig. 15(b) for the second. Note that the datasets were different regarding class membership assertions: most membership assertions were omitted in the input dataset for domain/range reasoning and left to be inferred during the reasoning process. Domain/range reasoning had significant implications on the runtime of rule evaluation. In both cases, however, the main factor influencing run time turned out to be the number of contexts. The reasoning task was complicated by the fact that the relevant knowledge for reasoning was distributed over multiple modules, evidenced by the fact that rule evaluation without any form of local inferencing takes only a couple of seconds. We leave the investigation of complexity and efficient implementation of reasoning in a contextualized setting under different ontology languages to future work.

5.3.Discussion

The purpose of the implementation was to get an idea of the complexity of KG-OLAP cube maintenance and query operations. Even though optimization was not a main goal of this paper, performance is already more than satisfactory for certain use cases. In order to handle big KGs, however, future work will consider a distributed, parallelized implementation. Nevertheless, optimization requires a thorough definition of the framework’s fundamental concepts, which we provide in this work.

In the following, we briefly discuss the implications of the results of the performance evaluation regarding the use cases presented in Section 2.

6.1.Contextualized knowledge graphs

The choice of CKR as base formalism for the definition of the KG-OLAP cube model was motivated by the explicit representation of dimensions and the organization of dimensions into levels which, as discussed in the previous sections, is compatible with the multidimensional perspective of OLAP. The idea of associating contexts with dimensions traces back to the theoretical works of Lenat [53] and the “context as a box” paradigm from Benerecetti et al. [7] for representation of contexts in knowledge representation.

The problem of annotation and contextualization of knowledge in KGs has been present since the early years of semantic web technologies. Different ways of introducing a notion of modularization in the RDF data model or KG implementations have been proposed [16,38,45]. Such approaches, however, often do not provide a formal (logic-based) definition of the resulting contextual model, which goes against Requirement 2 (ontological knowledge).

The need for formalization of the notion of context in KGs led to the proposal of several (description) logic-based approaches for the contextualization of knowledge bases: apart from the CKR [12,75], we can cite [46,80,82,92], for example. While these models explicitly introduce contexts as a primitive in knowledge bases, these proposals do not always take into account an explicit representation of the notion of dimensions and/or level hierarchies, which is important – as of Requirement 4 for modularization and Requirement 5 for hierarchical decomposition of KGs into more general and more specific knowledge along with knowledge propagation – to qualify the different situations represented by contexts, and to have a clear separation of knowledge bases associated with each context.

Krötzsch et al. [48] propose an approach for adding annotations in a logic-based reading of KGs. While that model formally introduces annotations to local description logic axioms and assertions, it does not provide definite criteria for knowledge propagation across contextual structures as in the KG-OLAP coverage hierarchy (cf. Requirement 5, general and specific knowledge).

6.2.OLAP and semantic web technologies

Semantic technologies have been used for a variety of tasks in the context of OLAP (see [3] for an overview). Related to KG-OLAP are techniques for data analysis over RDF data. The RDF data cube vocabulary (QB) [24] and its extension, QB4OLAP [26], provide an RDF representation format for publishing traditional OLAP cubes with numeric measures on the Semantic Web, with often SPARQL-based operators that emulate traditional OLAP queries for analyzing multidimensional data in QB [57] and QB4OLAP [27,84]. Such statistical linked data are just different serialization and publication formats of traditional OLAP cubes. Other work has suggested “lenses” over RDF data [20] for the purpose of RDF data analysis, i.e., analytical schemas which can be used for OLAP queries on RDF data. Similarly, superimposed multidimensional schemas [37] define a mapping between a multidimensional model and a KG in order to allow for the formulation of OLAP queries. Contrary to these approaches, KG-OLAP focuses on RDF graphs as the “measures” of OLAP cubes rather than numeric measures that are aggregated using aggregation operators such as Sum and Avg.

Fusion cubes [2] supplement traditional OLAP cubes with external data in RDF format, particularly linked open data where typically the data are not owned by the analyst. Fusion cubes are traditional OLAP cubes with numeric measures that can be populated dynamically with statistical data from RDF sources. Fusion cubes store contextual information about provenance and data quality of the external sources. Other similar work [59] extracts traditional OLAP cubes with numeric measures from RDF data sources and ontologies, which analysts may then query using a traditional OLAP language, namely MDX. The Semantic Cockpit project [60] employed ontologies for the definition of a shared understanding of business terms and analysis situations among business analysts. With respect to these approaches, KG-OLAP cubes may have some similarities to a structured data lake (see [69] for more information on data lakes), which stores the data of interest in a semantically richer format than plain numeric measures, but unlike conventional data lakes, which store raw data, provides a certain degree of integration and cleaning as well as dedicated query operations.

6.3.OLAP and information networks

KG-OLAP is related to applications of OLAP technology for analysis of information networks. Among the first, and arguably the most prominent, of these approaches was Graph OLAP (also known as InfoNetOLAP) [18,19], which through its informational and topological OLAP queries provides rich query facilities suitable for graph analysis. In Graph OLAP, graphs are associated with dimensional attributes, which yields a graph cube, i.e., the contents of the cube cells are graphs. The edges of the graphs themselves are weighted; the weights represent the measures to be analyzed. Typical applications of Graph OLAP are analysis of co-author and similar social graphs from different time periods, geographic locations, and so on. Graph OLAP distinguishes between informational roll-up and topological roll-up, which corresponds to the distinction between contextual and graph operations in KG-OLAP. The focus of Graph OLAP are weighted directed graphs with highly structured and homogeneous data. Hence, Graph OLAP does not consider heterogeneity (Requirement 1) and ontological knowledge (Requirement 2). Schema information, e.g., about roll-up hierarchies, are external to the data, i.e., graphs in Graph OLAP are not self-describing (Requirement 3), resulting in rigid, inflexible graph schema and queries. Graph OLAP also does not consider the systematic propagation of knowledge from more general to more specific contexts (Requirement 5); graph data are only associated with the most specific granularity in the cube.

Since the original proposal of Graph OLAP, other approaches that apply OLAP to information networks have been proposed, which can be compared along different criteria, most notably the type of network, i.e., homogeneous or heterogeneous [67]. KGs have been likened to “schema-rich” heterogeneous information networks [77] and, therefore, only approaches applying OLAP to heterogeneous networks can be accurately compared to KG-OLAP. Yet, even approaches applying OLAP technology to heterogeneous information networks, e.g., [29,55,88,89,91], do not consider schema variability, i.e., Requirement 1(c), or ontological knowledge (Requirement 2). Furthermore, unlike KG-OLAP, approaches to OLAP on information networks also lack a systematic way of structuring large bodies of knowledge, which comes with the decomposition of large knowledge graphs into hierarchically structured modules, from more general to more specific, in conjunction with knowledge propagation (Requirement 5). Schema and instance data are also firmly separated, i.e., the data are not self-describing (Requirement 3), reducing flexibility of the query operations. Another approach [56] aims to reconcile statistical/multidimensional linked data in QB and QB4OLAP with the informational/topological view of OLAP on information networks. Regarding the requirements, that approach does not consider schema variability, i.e., Requirement 1(c), ontological knowledge (Requirement 2), distinction between more general and more specific knowledge in conjunction with knowledge propagation (Requirement 5), and knowledge abstraction (Requirement 7). Some approaches, e.g., [88], offer abstraction operations that are similar to the KG-OLAP operations, but less flexible due to lack of self-describing data (Requirement 3), which allow for a more flexible formulation of roll-up paths within the graph structure. Furthermore, KG-OLAP allows for the use of complex concepts and roles in abstraction (in line with Requirement 2, ontological knowledge), allowing for flexible query formulation. For example, individual-generating abstraction with complex concepts such as Runway⊔Taxiway as selection criteria and complex roles such as layer−∘contaminant− as the grouping properties would not be possible in OLAP on information networks.

Techniques for optimization of OLAP on information networks may inform the optimization of KG-OLAP. Precomputation and materialization of aggregate views [88,89] is the most prevalent optimization technique for OLAP on information networks, which may not be applicable directly to KG-OLAP due to the heterogeneous data and highly flexible query formulation in KG-OLAP. Adopting a MapReduce-based implementation like Pagrol’s [89] or Process OLAP’s [6] is an interesting perspective for KG-OLAP as well.

Work on the analysis (or mining) of heterogeneous information networks [76] and Semantic Web databases [51] is orthogonal to KG-OLAP. Such approaches calculate, for example, degree distribution or PageRank, but may also serve to predict links and as the basis for recommender systems. Just like data mining may use OLAP cubes, information network mining may use KG-OLAP cubes.

6.4.(Knowledge) graph summarization

The KG-OLAP query operations also invite comparison with (knowledge) graph summarization techniques [17,54], which aim at making KGs more accessible to end users and applications by providing a condensed view on the represented knowledge. Use cases for KG summarization include visualization and exploration of KGs as well as facilitating query formulation and processing. Broadly speaking, KG (or RDF) summarization techniques may be divided into structural summarization, mining-based, and statistical summarization [17]. Statistical summarization computes quantitative measures that characterize a graph whereas mining-based (or pattern-based) summarization employs graph mining to extract frequent patterns that act as a summary. Structural summarization aims at finding a summary graph that preserves characteristics of the original graph while considerably reducing the size of the graph, making the graph easier to handle and comprehend.

Among the structural summarization approaches for RDF graphs, quotient RDF summaries represent a type of summaries that produce an RDF graph where multiple nodes from the source graph are replaced by a single summary node in the RDF summary. Accordingly, the results of abstraction operations in KG-OLAP may be considered structural quotient RDF summaries [17]. Unlike most structural approaches towards RDF summarization, KG-OLAP allows for ad hoc summarization based on user-specified, application-specific summarization criteria.

Unlike KG-OLAP, existing work on graph and KG summarization largely ignores modularization and contextuality in KGs (Requirement 4). In fact, existing work on KG summarization is orthogonal to the KG-OLAP approach. Consequently, future work may adapt summarization algorithms to serve as graph operators in KG-OLAP.