Repository navigation
Description
Behavior report, not a feature request. This documents what 0.2.0 does so it can be marked as expected or unexpected.
Observed behavior
Every add_vertex, add_edge and add_face (outside deferred_verification()) runs pyshacl.validate on the whole instance graph. In KnowledgeComplex._validate the focus_node_id argument is used only in the error message. The closed-triangle constraint (an sh:sparql constraint on faces) costs about 1.1 s per face in my measurements, so adding the n-th face costs about 1.1 × n seconds, and building a complex of n faces one write at a time costs roughly 1.1 × n² / 2 seconds. verify() on a complex costs about 1.1 s per face too.
Minimal reproduction (kc only)
import time
from knowledgecomplex import SchemaBuilder, KnowledgeComplex
sb = SchemaBuilder(namespace="ex")
sb.add_vertex_type("node")
sb.add_edge_type("link")
sb.add_face_type("tri")
kc = KnowledgeComplex(schema=sb)
for i in range(1, 13): # add disjoint triangles one at a time
a, b, c = f"a{i}", f"b{i}", f"c{i}"
for v in (a, b, c):
kc.add_vertex(v, type="node")
kc.add_edge(f"ab{i}", type="link", vertices={a, b})
kc.add_edge(f"bc{i}", type="link", vertices={b, c})
kc.add_edge(f"ca{i}", type="link", vertices={c, a})
t = time.time()
kc.add_face(f"f{i}", type="tri", boundary=[f"ab{i}", f"bc{i}", f"ca{i}"])
print(f"face {i:2d} ({len(kc.element_ids()):3d} elements): add_face took {time.time() - t:.2f}s")
t = time.time(); kc.verify()
print(f"kc.verify() on {len(kc.element_ids())} elements, 12 faces: {time.time() - t:.1f}s")
Output (knowledgecomplex 0.2.0, Python 3.14.3, an Apple-silicon Mac)
face 1 ( 7 elements): add_face took 1.11s
face 2 ( 14 elements): add_face took 2.22s
face 3 ( 21 elements): add_face took 3.30s
...
face 11 ( 77 elements): add_face took 12.04s
face 12 ( 84 elements): add_face took 13.47s
kc.verify() on 84 elements, 12 faces: 13.5s
At larger sizes I measured verify() on a complex of mostly faces at 25, 50, 100 and 200 faces: 27, 54, 109 and 220 seconds. A complex of 8,862 elements with 2,309 faces did not finish verifying within the 29 minutes I let it run (1.1 s per face extrapolates to about 42 minutes).
What I checked
- Vertices and edges alone are cheap: 2,001 elements (1,000 uses edges, no faces) took 8.6 s including one verification, and it scaled linearly.
- Inside
deferred_verification(), writes are fast, and the cost moves to the single verification on exit. - Profiling points at
pyshacl's evaluation of thesh:sparqlconstraints (sparql_based_constraints._validate_sparql_queryandgraph_abstraction.query).
An observation that may help: conformance is local
Every rule I found in ARCHITECTURE.md is local to an element and its boundary: types, attributes and vocabularies on one element; the two vertices of an edge are distinct; the three edges of a face close into a triangle; boundary elements are members of the complex. A change can therefore be checked on the changed element and its closure, and a complex whose every element passes in its own neighborhood conforms as a whole, so no global pass is needed for a global guarantee.
I tried this with only public API and pyshacl:
- The cost is per face and does not depend on graph size. Validating one face and its closure alone (23 triples) with kc's own shapes took 1.17 s, the same as the per-face cost in the whole graph. Vertices and edges took about 0.03 s. So the closed-triangle
sh:sparqlquery is what costs about a second, even on a tiny graph. - A native check of the same rule is fast. Replacing that query with set operations on the face's boundary (three distinct edges, two vertices each, three distinct vertices in all, each vertex in exactly two edges) gave the same verdict as kc's SHACL on four cases (a valid triangle, a path that does not close, a star that does not close, and a repeated edge). A face with two edges is rejected by
add_face's length check before any validation. With the query left out of the shapes and the native check in its place, a 1,400-element complex with 200 faces checked in 8.4 s (kc'sverify(): about 220 s), a single face's closure in 0.7 s, and a deliberately invalid face was caught on its own closure. A complex of 8,862 elements with 2,309 faces checked in 78 s.
The question
Is whole-graph validation on every write intended, given that the rules are local? Is there a size at which kc is meant to be used, beyond which a different workflow is expected (for example deferred_verification() and a single check)? If this is expected, a note in the documentation about the cost would help people who plan to build complexes with thousands of faces.
Workaround in use
Build inside deferred_verification() and leave the block with an exception, which skips the verification on exit (__exit__ only verifies when no exception occurred). Then check each element's closure with kc's shapes minus the closed-triangle query, plus the native triangle check above.
Activity