Abstrakt. Svar på frågor över en ofullständig databas w.r.t. En uppsättning begränsningar är en viktig beräkningsuppgift med tillämpningar inom så olika områden som informationsintegration och metadatahantering i den semantiska webben. Beskrivning Logik (DLs) är begränsande språk som har studerats i stor utsträckning med målet att tillhandahålla användbara modellering konstruktioner samtidigt som frågesvaret problem decidable. För många DLs, frågesvar under begränsningar kan lösas via frågeskrivning: med tanke på en konjunktiv fråga Q och en uppsättning DL begränsningar T, kan frågan Q omvandlas till en datalogg fråga QT som tar hänsyn till de semantiska konsekvenserna av T ; sedan, för att få svar på Q w.r.t. T och vissa (arbiträra) databas instans A, man kan helt enkelt utvärdera QT över A med hjälp av befintlig (deduktiva) databasteknik, utan att ta T i beaktande. I detta dokument presenterar vi en ny frågeskrivningsalgoritm som hanterar begränsningar modellerade i DL ELHIO ¬ och använder den för att visa att svara konjunktiva frågor i denna inställning är PTimecomplete w.r.t. Uppgifternas komplexitet. Vår algoritm behandlar olika beskrivningslogik av EL- och DL-lite-familjerna och är i värsta fall optimal w.r.t. data komplexitet för alla av dem.
Sedan, Pérez-Urbina et al. REF presenterade en upplösningsbaserad omskrivningsalgoritm för DL-lite.
I.: Tractable query answering and rewriting under description logic constraints
{'venue': 'Journal of Applied Logic', 'journal': None, 'mag_field_of_study': ['Computer Science']}