PSOA RuleML Bridges Graph and Relational Databases

From RuleML Wiki
Jump to: navigation, search

Author: Harold Boley
RuleML Technical Memo
Publication: ALP Newsletter, Feature Articles, July 6, 2018

In PSOA RuleML, Graph Databases and Relational Databases are bridged conceptually, with interoperation paths through its metamodel of three orthogonal dimensions, as well as programmatically, with transition rules realized in PSOATransRun. PSOA RuleML is introduced based on its systematics of atoms, including framepoints and relationships, as well as illustrated by PSOAMetaViz and PSOATransRun-executable examples.

1 Introduction

The gap between the graph/object vs. relational paradigms is a major concern in data modeling, as evidenced, e.g., by object-relational mapping, R2RML, NoSQL, and Multi-Model Databases. PSOA RuleML (Ref. 1) bridges the paradigms of Graph Databases (Berners-Lee et al. 2008) and Relational Databases (Maier 1983), augmented by paradigm-integrating knowledge (rule) bases on top of the paradigm-integrating data (facts): PSOA RuleML's databases (fact bases) generalize the instance level of Graph and Relational Databases; its knowledge bases complement facts by rules for deductive retrieval (extending the Datalog-level, function-free expressiveness of Deductive Databases to the Horn-logic expressiveness of Logic Programming), interoperation, and reasoning, as well as for optionally emulating part of the schema level.

The current document discusses overarching graph-relational topics. This is in continuation of earlier work on graph/object-relational interoperation with PSOA RuleML (Ref. 7).

PSOA RuleML's two bridge-building starting points are described in two dedicated documents, readable in either order, before or after the current one:

In those dedicated documents, the paradigmatic notions of graph and relation are both differentiated:

  • Graphs can be a) directed labeled graphs or b) generalized graphs (including directed labelnode hypergraphs)
  • Relations can have tables with a) the original tuple-like rows or b) the established record-like rows

The b) parts of both paradigms indicate a graph-relational convergence, which prepares PSOA RuleML's bridge building in focus of the current document.

2 Metamodel Paths

The PSOA RuleML metamodel in Ref. 15, Appendix A, Fig. 5, can be dynamically visualized as the dependency-focused cube shown in these snapshots (online: PSOAMetaViz):

de1: unit cube containing relationships

in4: unit cube of framepoints

It represents PSOA's 3-dimensional (OID, variety, dependency) qualitative design space of eighteen unit cubes (units), each having a systematic name like "de1" for oidless, tupled, dependent atoms (often constrained to a single tuple, i.e. "relationships"). This permits 'shortest paradigm-bridging paths', each a composition of (unit-to-adjacent-unit) transitions, where each transition changes the value in a dimension (to some of the one or two other possible values). Since these transitions constitute elementary steps, they make all intermediate units explicit as the most fine-grained 'conceptual pillars' for bridging any two units. We highlight an exemplary shortest de1-in4 path between the purest forms of the paradigms, which starts with the table rows of Relational Databases and, even within this paradigm, does the initial de1-de3 transition from the unit for the original tuple-like rows ("relationships") to the unit for the established record-like rows ("pairships"):

Metamodel path (four units with three transitions):

  1. (de1-constraining) oidless, single-tuple, dependent atoms, called "relationships"
    • de1-de3 transition: single-tuple → slotted
  2. (de3-corresponding) oidless, slotted, dependent atoms, called "pairships"
    • de3-de4 transition: oidless → oidful
  3. (de4-realizing) oidful, slotted, dependent atoms, called "pairpoints"
    • de4-in4 transition: dependent → independent
  4. (in4-corresponding) oidful, slotted, independent atoms, called "framepoints"

The path ends at the unit in4 for the classified-node-with-independent-labeled-outgoing-arc atoms ("framepoints") of Graph Databases, reached by the final de4-in4 transition. Classification is done with predicates in PSOA, where an untyped node is a node classified by the root predicate, Top, of the subpredicate hierarchy. Thus, a fourth dimension may distinguish atoms with non-Top vs. Top predicates. The metamodel path could first be restricted to non-Top hypercubes, e.g. refining 4. to   4a. oidful, slotted, independent, non-Top-predicate atoms, called "typed framepoints" ,   which could then be extended, by a transition   non-Top-predicate → Top-predicate,   to   4b. oidful, slotted, independent, Top-predicate atoms, called "untyped framepoints" .

The (unique) inverse in4-de1 path is obtained by inverted transitions (leading from unit 4. to 1.).

These metamodel notions can be illustrated with simple sample atoms about a traditional wedding, where different predicates Wedding1, ..., Wedding4 are used for clarity here (for the visualization of the eighteen kinds of atoms including these four see PSOAMetamodelGrailogWedding.pdf):

Example path (WeddingI atoms with abstract transitions):

  1. Wedding1(Mary John) or Wedding1(+[Mary John])
    • de1-de3 transition: single-tuple → slotted
  2. Wedding2(bride+>Mary groom+>John)
    • de3-de4 transition: oidless → oidful
  3. w31#Wedding3(bride+>Mary groom+>John)
    • de4-in4 transition: dependent → independent
  4. w41#Wedding4(bride->Mary groom->John)

In 1., a space-separated sequence, Mary John, abridges the tuple +[Mary John], which makes the couple's connection dependent (as indicated by the "+") on the predicate Wedding1 of its (dependent) relationship atom (rather than, say, on a predicate for an engagement party).

In 2. and 3., the slot groom+>John is dependent on the Wedding2 and Wedding3 predicates of its dependent atoms while, in 4., the slot groom->John is independent from the Wedding4 predicate of its (independent) framepoint atom. Thus, extending 3., if the wedding was celebrated at a derby, an additional atom w31#Derby(groom+>James) would create a multi-membership for w31 such that w31 as a Derby has groom James but w31 as a Wedding3 has groom John; however, extending 4., an additional atom w41#Derby(groom->James) would create a multi-membership for w41 such that w41 has a multi-valued groom slot not distinguishing James and John for Derby and Wedding4, respectively (MetamodelWeddingDerby.psoa contains a database and queries that are executable in PSOATransRun, developed in Ref. 18).

In 3. and 4., the Object IDentifier (OID) nodes w31 and w41 can be seen as the Skolem constants resulting from explicit existential wrappers of corresponding atoms Exists ?k ( ?k#Wedding3(bride+>Mary groom+>John) ) and Exists ?k ( ?k#Wedding4(bride->Mary groom->John) ), respectively. The de3-de4 transition exemplifies nine oidless → oidful transitions that map the subcube for the oidless half of the metamodel cube to its oidful subcube such that each oidless atom is equivalent to Exists ?k ( ?k#atom ), where the variable ?k does not occur in atom. This equivalence was built into a revised PSOA semantics (Ref. 12).

In 4., the non-Top predicate Wedding4 makes the atom correspond to the 4a. refinement of typed framepoints, while the complementary 4b. Top-predicate refinement of untyped framepoints is   w41#Top(bride->Mary groom->John). For untyped framepoints, the type information could be re-added via a conjoined membership, as in   And(w41#Wedding4 w41#Top(bride->Mary groom->John)).

3 Transition Rules

PSOA RuleML rules can be defined for the transitions between the sample atoms, where (for 1 ≤ J ≤ 3) an atom with predicate WeddingJ is used as a fact for a rule with a unifying condition, and the atom with predicate WeddingJ+1 is used as a query derived by the rule conclusion:

Example path (WeddingI atoms with implicit-Forall rules):

  1. Wedding1(Mary John) or Wedding1(+[Mary John])
    • Wedding2(bride+>?x groom+>?y) :- Wedding1(?x ?y)
  2. Wedding2(bride+>Mary groom+>John)
    • f3(?x ?y)#Wedding3(bride+>?x groom+>?y) :- Wedding2(bride+>?x groom+>?y), where w31 = f3(Mary John)
  3. w31#Wedding3(bride+>Mary groom+>John)
    • f4(?o)#Wedding4(bride->?x groom->?y) :- ?o#Wedding3(bride+>?x groom+>?y), where w41 = f4(w31)
  4. w41#Wedding4(bride->Mary groom->John)

The composition of these rules can be abridged to a single PSOA rule defined for the overall de1-in4-transition path between the sample atoms (the explicit Forall allows copy & paste for execution by PSOATransRun):

% Relationship-to-Framepoint Rule (R2F):
Forall ?x ?y (
  f5(?x ?y)#Wedding4(bride->?x groom->?y) :- Wedding1(?x ?y)
% Here w41 = f5(Mary John)

Likewise, the composition for the overall inverse in4-de1-transition path can be abridged (the stand-alone "?", as PSOA's anonymous variable, is used to discard the framepoint condition's OID, not needed in the relationship conclusion):

% Framepoint-to-Relationship Rule (F2R):
Forall ?x ?y (
  Wedding1(?x ?y) :- ?#Wedding4(bride->?x groom->?y)

Only the rules R2F and F2R are required for graph-relational WeddingI-atom interoperation (PSOATransRun assumes local constants, hence "_"-prefixes them in answer bindings): Based on a fact Wedding1(Mary John), rule R2F succeeds for queries f5(Mary John)#Wedding4(bride->Mary groom->John) and ?o#Wedding4(bride->Mary groom->?b), the latter with bindings ?o=_f5(_Mary _John), ?b=_John; based on a fact f5(Mary John)#Wedding4(bride->Mary groom->John), rule F2R succeeds for queries Wedding1(Mary John) and Wedding1(?a ?b), the latter with bindings ?a=_Mary, ?b=_John (for a PSOATransRun-executable knowledge base and queries see MetamodelWeddingInterop.psoa). These rules thus permit round-tripping that keeps atoms unchanged for a given OID-name ground instantiation of f5(?x ?y) such as, with our sample facts, for f5(Mary John).

4 Conclusions

PSOA RuleML is introduced as a paradigm-integrating language permitting expressive data and knowledge representation, translation, and execution (all with PSOATransRun) across the major graph-relational paradigms for databases as well as knowledge bases. The integration of different paradigms in one language facilitates the interoperation of content between these paradigms.

In particular, the maximally distant paradigms of relationships and untyped framepoints are connected by a metamodel path, which has a subpath between pairships and typed framepoints. While relationships are dependent and framepoints are independent, the path also contains oidful, slotted, dependent (de4) atoms, called "pairpoints", which can be seen as 'framepoints made dependent' and are useful for predicate-based disambiguation.

Expanding on the dependency-focused visualizations of the graph-relational-bridging metamodel cube in de1: unit cube containing relationships and in4: unit cube of framepoints, this has been complemented, in PSOAMetaViz (implemented by Alexander Kienzle using JavaScript/JSON), with user-selected variety- and OID-focused visualizations in a collaboration between RuleML Inc. and the UNB FCS HCI Lab.

The above metamodel path de1-in4 is extended and concatenated with its inverse in Exploring the PSOA RuleML Space of Core Atoms. Visualizations of core metamodel-characterized atoms can be found in PSOA RuleML Explained with Blockchain Examples. An entry point into the open development of PSOA RuleML and PSOATransRun is the PSOATransRun Development Agenda.