2026-09-08 La Bibbia

La Novitade

time-agnostic-library

arcangelo7Aug 7, 2026 · opencitations/time-agnostic-library

feat(query): support merge-aware entity histories

6a96568

arcangelo7Aug 26, 2026 · opencitations/time-agnostic-library

perf(query): filter quads before isolated version reconstruction

f3c430c

arcangelo7Sep 3, 2026 · opencitations/time-agnostic-library

feat!: compare delta query solution mappings across versions

BREAKING CHANGE: DeltaQuery removes changed_properties and returns additions, deletions, changes, and merges as solution mappings instead of per-entity quad records.

a14f83d

Complessità algoritmica

Obiettivo: capire come cresce il lavoro al crescere dell’input. Trovare un limite superiore, un peggio di così non può andare.

Mattone di cui ho letto solo 40 pagine https://cs.ucf.edu/~sharma/Algorithms_notes.pdf chiedendo a ChatGPT di spiegarmi ogni riga salvo poi scoprire che quello è un libro di appunti di un prof, non il vero manuale

Partiamo da una roba facile.

Pasted image 20260819214739.png

Qui l’input è formato da due cose: una query di update, cioè un elenco di quadruple, e lo stato corrente dell’entità, cioè il set da modificare. Chiamiamo u il numero di quadruple dell’update.

Il parsing costa u passi, perché DELETE DATA e INSERT DATA sono liste piatte di quadruple, senza strutture annidate, quindi basta una sola lettura. Il parsing restituisce k blocchi di update, con k al massimo u, perché ogni blocco contiene almeno una quadrupla.

Poi ogni quadrupla richiede una sola operazione, aggiungerla o toglierla dal set, operazione che costa un passo in media (perché da quando ho implementato un hashmap in C so che O(1) esiste solo nelle fiabe).

Quindi T <= 3k + 5u <= 8u (caso 1 quadrupla per blocco), quindi O(u)

Pasted image 20260903233700.png

QuerySnapshots è una richiesta al triplestore: prima chiamata. Torna h snapshot. SortDesc li ordina per data. Lato codice uso la funzione sorted di Python, che usa Timsort, che ha performance nel caso peggiore O(n log n), come il merge sort. Ma in realtà vedo che non c’è nessun algoritmo di ordinamento che può fare meglio di così nel libro di Cormen.

Pasted image 20260819214808.png