Dependency Graph Ontology

FLOW ALGEBRA
TITLE: Dependency Graph Ontology
DOMAIN: Relationship Ontologies / Information Relationships
SOURCE: https://kirethresearch.org/booksai-core/ontologies/relationship-ontologies/information-relationships/dependency-graph-ontology.html
VERSION: 1.0
AUTHORS: Mark Anthony Higgins — Sky (Recursive AI)
STATUS: Companion formalisation; source-page specification not independently verified.

flow "DependencyGraphOntology" v1.0 {
  ontology:
    id: "dependency-graph-ontology"
    parent: "information-relationships"
    purpose: "Represent, analyse and validate directed dependencies between information resources, tasks, processes and artefacts."

  types:
    DependencyNode: {id: string, kind: enum[dataset, document, service, task, process, model, module, other], version: string?, provenance: string?}
    DependencyEdge: {id: string, dependent: string, prerequisite: string, kind: enum[requires, derives_from, imports, references, blocks, optional], strength: number?, confidence: number, evidence: string[]}
    DependencyGraph: {id: string, nodes: string[], edges: string[], directed: bool, version: string}
    ChangeEvent: {id: string, target: string, change_type: string, timestamp: datetime, provenance: string}
    AnalysisResult: {graph_id: string, ordering: string[]?, cycles: string[][], impacted_nodes: string[], provenance: string}

  predicates:
    depends_on(dependent: DependencyNode, prerequisite: DependencyNode)
    directly_depends_on(dependent: DependencyNode, prerequisite: DependencyNode)
    transitively_depends_on(dependent: DependencyNode, prerequisite: DependencyNode)
    optional_dependency(dependent: DependencyNode, prerequisite: DependencyNode)
    blocks(prerequisite: DependencyNode, dependent: DependencyNode)
    impacted_by(node: DependencyNode, change: ChangeEvent)
    belongs_to(node: DependencyNode, graph: DependencyGraph)

  constraints:
    - "Every edge endpoint must resolve to a node in its graph."
    - "Dependency direction is dependent -> prerequisite; do not silently reverse it."
    - "Confidence must be within [0,1]; evidence and provenance must be retained."
    - "A dependency edge does not by itself imply causal necessity, temporal precedence or ownership."
    - "Optional, conditional and mandatory dependencies must remain distinguishable."
    - "Cycles are permitted in general graphs but must be flagged when an acyclic execution order is required."
    - "Self-dependencies must be explicitly justified or rejected by the graph policy."

  inference:
    rule direct_dependency:
      if edge(e) and e.kind == requires and e.dependent == a and e.prerequisite == b
      then directly_depends_on(a,b)
      confidence: "inherit evidence and edge context"
    rule dependency_reachability:
      if directly_depends_on(a,b) and transitively_depends_on(b,c) and compatible_context(a,b,c)
      then transitively_depends_on(a,c)
      confidence: "track full path and source uncertainty"
    rule reachability_base:
      if directly_depends_on(a,b)
      then transitively_depends_on(a,b)
      confidence: "retain direct edge provenance"
    rule change_impact:
      if changed(b) and transitively_depends_on(a,b)
      then potentially_impacted(a,b)
      confidence: "impact is conditional on dependency semantics; not guaranteed failure"
    rule execution_order:
      if acyclic(g) and mandatory_edges_only(g)
      then topological_order(g, prerequisites_first)
      confidence: "deterministic for a specified graph snapshot and tie-break policy"

  SEMANTIC_EQUIVALENCE:
    - "Normalise identifiers only through verified, versioned alias mappings."
    - "Distinguish depends_on, derives_from, references, imports and blocks."
    - "Equivalent labels do not establish identical dependency semantics."

  CONFIDENCE:
    range: [0,1]
    factors: [source_reliability, edge_verification, temporal_validity, graph_completeness, independent_confirmation]
    policy: "Do not increase confidence solely through multi-hop chaining."

  VALIDATION:
    - "Validate graph membership, edge direction, node identity and type compatibility."
    - "Detect cycles using strongly connected components and report paths."
    - "Check missing prerequisites, stale versions, duplicate edges and unresolved references."
    - "Require a DAG before generating a topological execution order."
    - "Record whether impact analysis uses all edges or mandatory edges only."

  FLOW_HASH:
    algorithm: "SHA-256"
    input: "canonicalised ontology version, node and edge assertions, rules and provenance"
    note: "Compute at execution; no hash value is claimed here."

  UPDATE_MODEL:
    strategy: "versioned incremental graph update with dependency-aware invalidation"
    steps: [ingest, normalise, validate, detect_cycles, compare_versions, compute_impact, reconcile, publish]
    rollback: true

  AI_CONSUMPTION:
    representation: "typed directed dependency graph with evidence-backed edges"
    outputs: [dependency_triples, prerequisite_paths, cycle_reports, impact_sets, topological_orders, provenance_records]
    safeguards: [no_unverified_dependencies, no_unsupported_causal_claims, preserve_direction_and_versions, expose_uncertainty]
}

END FLOW ALGEBRA