💻 computer science

Using ASP(Q) to Handle Inconsistent Prioritized Data

Dit paper introduceert en implementeert voor het eerst een ASP(Q)-gebaseerde aanpak voor het afvragen van prioriteitsgegevens met inconsistenties door gebruik te maken van optimaal herstel en grondige semantiek, waarbij de rekencomplexiteit en haalbaarheid van verschillende semantische varianten experimenteel worden onderzocht.

Oorspronkelijke auteurs: Meghyn Bienvenu, Camille Bourgaux, Robin Jean, Giuseppe Mazzotta

Gepubliceerd 2026-04-24

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Meghyn Bienvenu, Camille Bourgaux, Robin Jean, Giuseppe Mazzotta

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme bibliotheek hebt met miljoenen boeken (de data). Maar er is een groot probleem: sommige boeken vertellen tegenstrijdige verhalen. In boek A staat dat "de koning een appel eet", terwijl in boek B staat dat "de koning een peer eet". Je kunt ze niet allebei waar hebben.

In de wereld van databases en kunstmatige intelligentie noemen we dit inconsistentie. Normaal gesproken zou een computer zeggen: "Ik snap het niet, ik geef geen antwoord." Maar in de echte wereld willen we toch een antwoord, zelfs als de informatie niet perfect is.

Dit artikel beschrijft hoe de auteurs een slimme manier hebben bedacht om met deze "verwarde bibliotheek" om te gaan, zodat we toch betrouwbare antwoorden kunnen krijgen. Ze gebruiken een wiskundig raamwerk genaamd ASP(Q).

Hier is een uitleg in alledaags taal, met een paar creatieve vergelijkingen:

1. Het Probleem: De Ruziënde Boekhouders

Stel je voor dat je een team hebt van boekhouders die elk een eigen versie van de cijfers hebben. Sommige versies kloppen niet met elkaar.

De Oplossing (Reparaties): Om de boel te redden, moet je een "reparatie" maken. Dat betekent dat je een selectie maakt van de boeken die je wel wilt houden en de rest weggooit, zodat er geen tegenstrijdigheden meer zijn.
De Keuze: Er zijn duizenden manieren om te kiezen welke boeken je weggooit. Welke selectie is de "beste"?

2. De Prioriteiten: De "Koning" van de Feiten

Om de beste selectie te kiezen, hebben we prioriteiten. Stel dat we weten dat boek A betrouwbaarder is dan boek B.

Als boek A en boek B tegenstrijdig zijn, houden we boek A en gooien we boek B weg.
De auteurs kijken naar drie manieren om de "beste" selectie te vinden:
1. Pareto-optimale: Je kunt niet één boek toevoegen zonder een "beter" boek te verliezen. (Een beetje zoals een evenwicht in een spel).
2. Voltooiings-optimale: Je vult de prioriteiten aan tot er geen twijfel meer is over welke boeken beter zijn, en kiest dan.
3. Globaal-optimale: Dit is de "heilige graal". Je zoekt naar de absolute beste selectie waarbij je op geen enkel moment een beter boek opoffert voor een slechter boek. Dit is echter extreem moeilijk te berekenen, alsof je in één keer elke mogelijke combinatie van boeken doorzoekt.

3. De Nieuwe Tool: ASP(Q) als de Super-Detective

Vroeger waren computers te traag om de "Globaal-optimale" oplossing te vinden. Het was als proberen elke mogelijke route door een labyrint te lopen om de kortste te vinden; het duurt te lang.

De auteurs gebruiken nu ASP(Q).

De Analogie: Stel je voor dat ASP een slimme detective is die één scenario tegelijk onderzoekt. ASP(Q) is diezelfde detective, maar dan met een tijdmachine of een magische bril.
Met deze bril kan de detective niet alleen kijken naar één scenario, maar kan hij vragen stellen als: "Bestaat er een scenario waarbij X waar is, en voor ALLE andere scenario's geldt dat Y waar is?"
Dit maakt het mogelijk om de extreem moeilijke "Globaal-optimale" berekeningen te doen, iets dat voorheen bijna onmogelijk was.

4. De Slimme Afkortingen: De "Grondslagen"

Omdat de "Globaal-optimale" methode zo zwaar is (het kost veel rekenkracht en tijd), gebruiken de auteurs ook slimme afkortingen.

De Grondslagen (Grounded Semantics): Stel je voor dat je in een ruzie zit. In plaats van alle mogelijke oplossingen te berekenen, kijk je eerst naar de feiten die niemand kan aanvallen. Die zijn veilig.
De auteurs ontdekten dat deze "veilige" feiten vaak al een heel goed antwoord geven. Het is alsof je eerst kijkt naar de feiten waar iedereen het over eens is, voordat je gaat twijfelen aan de moeilijke cases.
Het Resultaat: Hun experimenten tonen aan dat deze "veilige" methode vaak al 90% van de goede antwoorden geeft, maar dan in een fractie van de tijd. Het is een perfecte balans tussen snelheid en nauwkeurigheid.

5. Wat hebben ze ontdekt?

Het is mogelijk: Voor het eerst hebben ze een systeem gebouwd dat de allerbeste ("Globaal-optimale") antwoorden kan berekenen, zelfs bij grote datasets.
Het is zwaar: Het kost veel meer tijd dan de eenvoudigere methoden. Het is alsof je een Ferrari gebruikt om naar de supermarkt te gaan; het kan, maar het is niet altijd nodig.
De slimme truc werkt: De "Grondslagen"-methode (het kijken naar de veiligste feiten) is verrassend effectief. Voor veel vragen is dit al genoeg, en het bespaart enorm veel rekenkracht.

Conclusie

Dit artikel is een doorbraak in het omgaan met rommelige, tegenstrijdige data. Ze hebben een nieuwe, krachtige "rekenmachine" (ASP(Q)) gebouwd die de allerbeste oplossingen kan vinden, maar ze raden ook aan om eerst te kijken naar de "veilige" oplossingen.

Kort samengevat: Als je een rommelige bibliotheek hebt, kun je proberen elke mogelijke manier te vinden om de boeken netjes te ordenen (duur en moeilijk), of je kunt eerst kijken naar de boeken die niemand kan betwisten (snel en vaak goed genoeg). De auteurs hebben bewezen dat je met de juiste tools (ASP(Q)) zelfs de moeilijkste ordening kunt doen, maar dat de snelle weg vaak al het beste resultaat geeft.

Titel: Het gebruik van ASP(Q) voor het verwerken van inconsistente geprioriteerde data

Auteurs: Meghyn Bienvenu, Camille Bourgaux, Robin Jean, Giuseppe Mazzotta.

1. Probleemstelling

In veel applicaties, zoals relationele databases en semantische webtoepassingen (ontology-mediated query answering), is data vaak inconsistent met betrekking tot een logische theorie (bijvoorbeeld een beperking of een ontologie). Om zinvolle antwoorden op queries te geven, wordt vaak gebruikgemaakt van repair-based semantics. Een "repair" is een maximaal subset van de data die consistent is met de theorie.

De uitdaging in dit artikel is tweeledig:

Geprioriteerde data: Wanneer er conflicten zijn, wordt er vaak een voorkeursrelatie ( $\succ$ $≻$ ) tussen de feiten gebruikt om te bepalen welke feiten behouden moeten blijven. Dit leidt tot verschillende soorten "optimale repairs":
- Pareto-optimaal: Geen enkele verbetering mogelijk door feiten te vervangen door strikt betere feiten.
- Globaal optimaal: Geen enkele verbetering mogelijk door een willekeurige verzameling feiten te vervangen door een verzameling strikt betere feiten.
- Compleet optimaal: Globaal optimaal ten opzichte van een volledige uitbreiding van de voorkeursrelatie.
Complexiteit: Het beantwoorden van queries onder globaal optimale repairs (G-repairs) is computatievermogen-technisch zwaarder dan bij Pareto- of compleet optimale repairs. Voor een grote klasse van theorieën ligt de complexiteit van G-repair query answering op het tweede niveau van de polynoomhiërarchie ( $\Sigma_2^P$ en $\Pi_2^P$ ), terwijl Pareto- en compleet optimale repairs vaak op het eerste niveau ($NP$ en $coNP$) blijven. Bestaande systemen implementeren voornamelijk Pareto- en compleet optimale repairs, maar missen een implementatie voor de zwaardere G-repairs en de "grounded semantics".

2. Methodologie

De auteurs onderzoeken het gebruik van Answer Set Programming met kwantoren (ASP(Q)) om deze complexe semantiek te implementeren.

ASP(Q): In tegenstelling tot standaard ASP (dat beperkt is tot het eerste niveau van de polynoomhiërarchie), maakt ASP(Q) het mogelijk om te kwantificeren over de antwoordsets van verschillende ASP-programma's. Dit biedt een natuurlijke en compacte manier om problemen op het tweede niveau van de polynoomhiërarchie te modelleren zonder complexe technieken zoals "saturation" die nodig zijn in disjunctief ASP.
Enkodering: De auteurs ontwikkelen ASP(Q)-programma's om de drie semantiekvarianten (AR, brave, IAR) voor de drie soorten repairs (Pareto, Globaal, Compleet) te berekenen.
- Ze gebruiken een naieve enkodering die alle feiten in overweging neemt.
- Ze introduceren localisatie: Door gebruik te maken van concepten van bereikbaarheid in een hypergraaf (sterke en zwakke bereikbaarheid), wordt de dataset beperkt tot alleen de feiten die relevant zijn voor de query en de conflicten. Dit vermindert de zoekruimte aanzienlijk.
- Voor binaire conflicten (conflicten van grootte 2) worden specifieke, vereenvoudigde enkoderingen ontwikkeld.
Benaderingen (Approximations): Om de rekentijd te beheersen, gebruiken ze tractable under-approximations:
- Grounded Semantics: Een berekenbare onderbenadering van alle optimale repairs, gebaseerd op abstracte argumentatie (het vinden van een fixpunt van een aanvalsrelatie).
- Triviale P-IAR: Antwoorden die gelden voor een subset van reparaties die makkelijk te berekenen zijn.
- De strategie is om eerst deze snelle benaderingen te gebruiken; alleen als het antwoord onzeker blijft, wordt de zwaardere ASP(Q)-enkodering voor G-repairs aangeroepen.

3. Belangrijkste Bijdragen

Eerste implementatie van Globaal-Optimale Repairs: Dit is het eerste systeem dat query answering onder G-repair semantiek daadwerkelijk implementeert, gebruikmakend van ASP(Q).
Eerste implementatie van Grounded Semantics: De auteurs implementeren de grounded semantics, een tractabele benadering die nog nooit eerder in een systeem was opgenomen.
Vergelijkende Analyse: Het biedt een uitgebreide experimentele vergelijking tussen Pareto-, Compleet- en Globaal-optimale repairs, zowel qua antwoordkwaliteit als qua prestaties.
Openbaar Beschikbaarheid: Alle code en experimentele data zijn beschikbaar gesteld via GitHub, wat reproduceerbaarheid garandeert.

4. Experimentele Resultaten

De auteurs hebben hun systeem geëvalueerd op het ORBITS/CQAPri benchmark (synthetische datasets met inconsistenties in DL-Lite ontologieën).

Complexiteit en Prestaties:
- Het gebruik van Globaal-optimale repairs is significant moeilijker dan Pareto- of Compleet-optimale repairs. De rekentijden zijn veel langer en er treden vaker time-outs op (binnen de limiet van 600 seconden).
- De Grounded Semantics blijkt een zeer effectieve benadering. In veel gevallen levert de grounded semantics hetzelfde antwoord als de zwaardere semantiek, maar dan veel sneller.
- Localisatie is cruciaal: zonder localisatie vielen bijna alle instanties uit op time-out. Met localisatie kon 99% van de gevallen worden opgelost.
Aantal Antwoorden:
- De grounded semantics dekt een groot deel van de antwoorden die onder de zwaardere semantiek gelden.
- Het verschil tussen Pareto-, Compleet- en Globaal-optimale repairs in termen van het aantal gevonden antwoorden is vaak klein, maar niet verwaarloosbaar.
Strategie: De beste aanpak is een gefaseerde strategie:
1. Bereken eerst de grounded repair (snelle, onderbenadering).
2. Als een antwoord hieruit volgt, is het geldig voor alle zwaardere semantiekvarianten.
3. Als een antwoord niet in de grounded repair zit, probeer dan eerst de snellere Pareto/C-AR semantiek.
4. Gebruik pas de zware G-AR/G-brave ASP(Q)-enkodering als de status nog onopgelost is.

5. Betekenis en Conclusie

Dit artikel is een mijlpaal in het onderzoek naar inconsistentie-tolerante query answering. Het bewijst dat het theoretisch complexe probleem van globaal optimale repairs praktisch oplosbaar is met behulp van ASP(Q), een formalisme dat specifiek is ontworpen voor problemen op het tweede niveau van de polynoomhiërarchie.

De belangrijkste inzichten zijn:

ASP(Q) is krachtig: Het stelt onderzoekers in staat om complexe kwantificering over antwoordsets direct en leesbaar te modelleren.
Grounded Semantics is nuttig: Het is geen slechts theoretisch concept, maar een zeer effectief praktisch hulpmiddel om de zoekruimte te beperken en snelle, betrouwbare antwoorden te geven.
Praktische toepasbaarheid: Hoewel G-repairs zwaar zijn, maakt de combinatie van localisatie, benaderingen en ASP(Q) het mogelijk om ze op redelijke datasets toe te passen. Dit opent de deur voor het gebruik van geavanceerde prioriteitslogica in real-world databases en ontologie-systemen.

De auteurs concluderen dat, hoewel het direct berekenen van G-repair antwoorden duur is, een hybride strategie die gebruikmaakt van de grounded semantics en snellere semantiek als filter, de meest haalbare route is voor schaalbare implementaties.