Tree Relationship Ontology

FLOW ALGEBRA
TITLE: Tree Relationship Ontology
SOURCE: https://kirethresearch.org/booksai-core/ontologies/relationship-ontologies/structural-relationships/tree-relationship-ontology.html
VERSION: 1.0
AUTHORS: Mark Anthony Higgins — Sky (Recursive AI)
STATUS: Companion formalisation; page text not independently verified.

ONTOLOGY TreeRelationshipOntology
DOMAIN StructuralRelationships

ENTITY Tree {id: IRI, root: Node, nodes: Set<Node>, edges: Set<Edge>, tree_kind: TreeKind}
ENTITY Node {id: IRI, label: String?, metadata: Map?}
ENTITY Edge {id: IRI, parent: Node, child: Node, provenance: Source?, confidence: Decimal[0,1]}
ENTITY Source {id: IRI, citation: String?, observed_at: DateTime?}
ENUM TreeKind {Rooted, Ordered, Binary, Nary, ForestMember}

RELATION parent_of(parent: Node, child: Node) := Edge(parent, child)
RELATION child_of(child: Node, parent: Node) := parent_of(parent, child)
RELATION ancestor_of(a: Node, d: Node) := transitive_closure(parent_of)(a, d)
RELATION descendant_of(d: Node, a: Node) := ancestor_of(a, d)
RELATION sibling_of(a: Node, b: Node) := a != b AND EXISTS p: parent_of(p,a) AND parent_of(p,b)
RELATION root_of(r: Node, t: Tree) := t.root = r
RELATION leaf_of(n: Node, t: Tree) := n IN t.nodes AND NOT EXISTS c: parent_of(n,c)
RELATION connected_to(a: Node, b: Node) := undirected_reachability(t.edges,a,b)

AXIOM T1: FORALL e IN t.edges: e.parent IN t.nodes AND e.child IN t.nodes
AXIOM T2: t.root IN t.nodes
AXIOM T3: NOT EXISTS p: parent_of(p,t.root)
AXIOM T4: FORALL n IN t.nodes EXCEPT t.root: COUNT({p | parent_of(p,n)}) = 1
AXIOM T5: FORALL n IN t.nodes: NOT ancestor_of(n,n)
AXIOM T6: FORALL n IN t.nodes: n = t.root OR ancestor_of(t.root,n)
AXIOM T7: |t.edges| = |t.nodes| - 1 FOR finite nonempty trees
AXIOM T8: IF t.tree_kind = Binary THEN FORALL n: COUNT(children(n)) <= 2
AXIOM T9: IF t.tree_kind = Ordered THEN child_order(n) is unique and total for each sibling set

INFERENCE R1: parent_of(a,b) => child_of(b,a)
INFERENCE R2: parent_of(a,b) AND ancestor_of(b,c) => ancestor_of(a,c)
INFERENCE R3: parent_of(a,b) => ancestor_of(a,b)
INFERENCE R4: parent_of(p,a) AND parent_of(p,b) AND a != b => sibling_of(a,b)
INFERENCE R5: leaf_of(n,t) => out_degree(n) = 0

SEMANTIC_EQUIVALENCE:
  parent_of(a,b) <=> child_of(b,a)
  ancestor_of(a,b) <=> descendant_of(b,a)
  tree_edge(a,b) <=> parent_of(a,b) WHEN orientation = parent_to_child
  WARNING: part_of, subclass_of and parent_of are NOT generally interchangeable

CONFIDENCE:
  asserted_edge: confidence in [0,1]
  inferred_path: conservative_minimum(edge_confidences)
  missing_evidence: unknown_not_false
  conflicting_parent_assertions: flag_for_review

VALIDATION:
  - require_unique_node_and_edge_ids
  - reject_self_loops_and_directed_cycles
  - enforce_single_root_and_single_parent_for_nonroot
  - require_reachability_from_root
  - check_edge_count_for_finite_trees
  - verify_source_and_confidence_ranges
  - preserve_distinction_between_asserted_and_inferred_edges

OPERATIONS:
  add_node(t,n,parent): validate_parent_exists; insert_node_and_edge; validate_tree
  remove_subtree(t,n): delete_n_and_descendants; validate_tree
  reparent(t,n,new_parent): reject_if_new_parent_in_subtree(n); replace_incoming_edge; validate_tree
  lowest_common_ancestor(a,b): deepest_shared_ancestor(a,b)
  depth(n): length(root_to_node_path(n))
  height(n): maximum_length(node_to_leaf_paths(n))
  traverse(t,mode): mode IN {preorder,postorder,breadth_first}

FLOW_HASH:
  canonicalise: sort_nodes_by_id; sort_edges_by_parent_child_id; normalise_literals
  algorithm: SHA-256
  digest: SHA256(canonical_ontology_representation)
  purpose: integrity_and_change_detection

UPDATE_MODEL:
  trigger: node_added | edge_added | edge_removed | node_removed | metadata_changed
  sequence: ingest -> type_check -> validate -> infer -> assess_confidence -> canonicalise -> hash -> publish
  rollback_on_validation_failure: true
  retain_version_history: true

AI_CONSUMPTION:
  format: typed_directed_graph
  expose: entities, relations, axioms, inferred_facts, confidence, provenance, version, hash
  reasoning: tree_navigation, hierarchy_queries, ancestor_inference, structural_validation
  constraints: no_cycle_hallucination; do_not_assume_missing_edge; separate_inference_from_source

END FLOW ALGEBRA