Abhängigkeitsanalyse und Zykluserkennung
Diese Seite erklärt, wie Askalot ermittelt, welche Items eines Fragebogens von welchen anderen abhängen, damit die Items in einer konsistenten Reihenfolge ausgewertet werden, und wie es zirkuläre Abhängigkeiten erkennt, die eine Auswertung unmöglich machen würden. Die hier berechnete Reihenfolge ist auch die, die die pfadbasierten Prüfungen unter Umfassende Validierung durchlaufen. Die formale Behandlung der Verifikation, die darauf aufbaut, steht im begutachteten Beitrag, der auf der ICAI 2026 (13th International Conference on Applied Informatics) vorgestellt wurde, Tagungsband S. 227–243, doi:10.17048/icai.2026.227.
Überblick
Abschnitt betitelt „Überblick“Zu wissen, welche Items von welchen abhängen, ist für drei Dinge nötig:
- Auswertungsreihenfolge: Ein Item wird nach den Items ausgewertet, von denen es abhängt
- Zykluserkennung: Zirkuläre Abhängigkeiten machen die Navigation während der Befragung unmöglich
- Abdeckungsanalyse: Wissen, welche Antworten welche späteren Items beeinflussen
Pfad im Abhängigkeitsgraphen
Abschnitt betitelt „Pfad im Abhängigkeitsgraphen“Die Abhängigkeiten bilden einen gerichteten Graphen, dessen Knoten die Items sind: Ein Pfeil von einem Item zu einem anderen bedeutet, dass das zweite vom ersten abhängt. Ein Pfad in diesem Graphen ist eine Kette verschiedener Items, von denen jedes durch einen Pfeil mit dem nächsten verbunden ist. Ein einzelnes Item für sich zählt als Pfad der Länge null.
Aufbau des Abhängigkeitsgraphen
Abschnitt betitelt „Aufbau des Abhängigkeitsgraphen“Der Abhängigkeitsgraph hält fest, wie Daten von der Antwort eines Items zu den Bedingungen eines anderen Items fließen, sowohl direkt als auch über Zwischenvariablen, die in Codeblöcken berechnet werden. Er entsteht in drei Stufen.
Stufe 1: Datenflussgraph aufbauen
Abschnitt betitelt „Stufe 1: Datenflussgraph aufbauen“Eine statische Analyse der Vorbedingungen, Nachbedingungen und Codeblöcke erzeugt einen Zwischengraphen, dessen Knoten sowohl Items als auch Variablen sind (Antworten der Items und Zwischenvariablen). Seine Pfeile sind:
- Das Beantworten eines Items weist dessen Antwort zu: Item → Antwort
- Code, der einer Variablen eine Antwort zuweist oder eine Variable anhand einer Antwort aktualisiert: Antwort → Variable
- Eine Variable, die in der Vor- oder Nachbedingung eines Items verwendet wird: Variable → Item
- Eine Antwort, die direkt in der Vor- oder Nachbedingung eines Items verwendet wird: Antwort → Item
Stufe 2: Abhängigkeiten zwischen Items berechnen
Abschnitt betitelt „Stufe 2: Abhängigkeiten zwischen Items berechnen“Aus dem Datenflussgraphen behält der Item-Abhängigkeitsgraph nur die Items. Ein Item hängt genau dann von einem anderen ab, wenn der Datenflussgraph einen Pfad vom zweiten zum ersten Item enthält, über beliebig viele Variablen hinweg. Abhängigkeiten über Zwischenvariablen werden also erfasst: Fließt die Antwort eines Items durch mehrere Variablen, bevor sie die Bedingung eines anderen Items erreicht, hängt das zweite Item vom ersten ab.
Allgemeines Beispiel: Code, der eine Variable aus der Antwort eines Items setzt, dann die Antwort eines zweiten Items addiert und die Variable schließlich in den Vorbedingungen zweier weiterer Items liest, macht diese beiden Items von beiden ersten Items abhängig.
Stufe 3: Topologische Sortierung (Kahn-Algorithmus)
Abschnitt betitelt „Stufe 3: Topologische Sortierung (Kahn-Algorithmus)“Eine gültige Auswertungsreihenfolge ist eine topologische Sortierung des Abhängigkeitsgraphen: Jedes Item steht nach allen Items, von denen es abhängt. Askalot berechnet sie mit dem Kahn-Algorithmus:
- Beginnen Sie mit den Items, die von nichts abhängen.
- Nehmen Sie wiederholt ein solches Item, hängen Sie es an die Reihenfolge an und entfernen Sie seine ausgehenden Pfeile. Jedes Item, das danach keinen eingehenden Pfeil mehr hat, wird seinerseits verfügbar.
- Bleiben Pfeile übrig, wenn kein Item mehr verfügbar ist, enthält der Graph einen Zyklus; andernfalls ist die Reihenfolge vollständig.
In der resultierenden Reihenfolge ist beim Erreichen eines Items jede Variable, die seine Vorbedingung liest, bereits zugewiesen.
Zykluserkennung
Abschnitt betitelt „Zykluserkennung“Ein Fragebogen ist zyklenfrei, wenn sein Abhängigkeitsgraph ein gerichteter azyklischer Graph ist: Es gibt keine Kette aus zwei oder mehr verschiedenen Items, in der jedes vom nächsten abhängt und das letzte vom ersten.
Alle Zyklen melden, nicht nur den ersten
Abschnitt betitelt „Alle Zyklen melden, nicht nur den ersten“Statt beim ersten Zirkelbezug anzuhalten, arbeitet der Validator weiter, damit Sie pro Durchlauf mehr als ein Problem sehen. Jedes Mal, wenn der Kahn-Algorithmus stockt, isoliert er einen Zyklus unter den blockierten Items, meldet ihn, entfernt eine einzelne Kante, um ihn aufzubrechen, und fährt fort. So zeigt er für jede unabhängige Blockade im Graphen einen repräsentativen Zyklus an – nicht nur für die erste.
Überlappen sich mehrere Zyklen über eine gemeinsame Kante, kann das Entfernen dieser Kante mehrere Blockaden auf einmal auflösen. Der Bericht listet deshalb so viele Zyklen auf, dass jedes Stocken erklärt ist, statt jede einzelne Schleife aufzuzählen.
Bleibt der Kahn-Algorithmus stecken (alle verbleibenden Items haben einen Eingangsgrad ungleich null), wiederholt sich der folgende Ablauf, bis alle Items verarbeitet sind:
- Einen Zyklus finden unter den blockierten Items, per Tiefensuche
- Den Zyklus melden, mit der vollständigen Kette der Items
- Die Rückwärtskante entfernen (die Kante vom letzten zum ersten Item in Dateireihenfolge), damit der Algorithmus fortfahren kann
- Fortfahren mit dem Kahn-Algorithmus für die verbleibenden Items
Das ergibt auch dann eine vollständige Auswertungsreihenfolge, wenn Zyklen existieren – die Items eines Zyklus werden in ihrer ursprünglichen Dateireihenfolge linearisiert. Die Reihenfolge ist zwar nur näherungsweise richtig (die entfernten Abhängigkeiten sind echte Entwurfsfehler), aber der Validator kann so den Rest des Fragebogens weiter analysieren, statt beim ersten Zyklus abzubrechen.
Zähler werden in Dateireihenfolge gelesen, nicht als Zyklen
Abschnitt betitelt „Zähler werden in Dateireihenfolge gelesen, nicht als Zyklen“Ein Zähler, den mehrere Items aktualisieren und zugleich in ihren Vorbedingungen (oder in denen ihres Blocks) lesen, wirkt zirkulär, wenn man eine Variable als einen einzigen Wert behandelt: Jedes Item würde auf alle anderen warten. Askalot liest einen solchen Zähler, einen Akkumulator, stattdessen in Dateireihenfolge: Eine Vorbedingung sieht die Aktualisierungen der Items, die in der Datei vor ihr stehen, und der eigene Codeblock eines Items läuft nach dessen eigenen Bedingungen. Die Kante von einem lesenden Item zu einem später schreibenden ist daher keine Abhängigkeit. Das Ausgangsbeispiel (nach dem dritten „Nein“ den Rest des Blocks überspringen) hat also keinen Zyklus, und der Validator prüft seine Bedingung an jeder Position.
Eine Variable gilt nur dort als Akkumulator, wo ein Item sie sowohl liest als auch schreibt und dieses Lesen sonst zirkulär wäre. Ist eine Variable einmal ein Akkumulator, sieht jedes lesende Item die schreibenden Items vor ihm in der Datei, sodass ihre Reihenfolge im Interview der Datei folgt. Ein Fragebogen ohne solchen Akkumulator behält seine Abhängigkeitsreihenfolge unverändert, und zwei Items, deren Bedingung jeweils von dem abhängt, was nur das andere schreibt, oder von den Antworten des jeweils anderen, bleiben ein gemeldeter Zyklus.
Abhängigkeitsanalyse bei komplexen Typen
Abschnitt betitelt „Abhängigkeitsanalyse bei komplexen Typen“Für Fragegruppen und Matrizen gilt derselbe Aufbau. Details finden Sie unter Komplexe Typen.
- Ein Item hängt von einer Fragegruppe oder Matrix ab, wenn seine Vorbedingung irgendeine Komponente der Antwort dieses Items liest
- Bei einer Fragegruppe erzeugt ein Bezug auf eine beliebige ihrer Antworten die Abhängigkeit
- Bei einer Matrix erzeugt ein Bezug auf eine beliebige ihrer Zellen die Abhängigkeit
Die Abhängigkeitsanalyse stellt sicher, dass Fragebögen in einer konsistenten Reihenfolge ausgewertet werden können, und erkennt Entwurfsfehler, bei denen zirkuläre Abhängigkeiten die Navigation unmöglich machen würden.
Weiterführende Informationen
Abschnitt betitelt „Weiterführende Informationen“- Grundlagen der Fragebogenanalyse – Zentrale Definitionen und Notation
- Vorbedingungen und Nachbedingungen – Erreichbarkeit und Klassifizierung der Bedingungen
- Komplexe Typen – Erweiterungen für Vektor- und Matrix-Items mit Abhängigkeiten auf Komponentenebene
- Umfassende Fragebogenvalidierung – Zusammenhang zwischen Prüfungen pro Item und globalen Prüfungen