Ekstensi Horn dari DL-Lite dengan kompleksitas data NL

Penjawaban kueri bermediasi ontologi (OMQA) telah didominasi oleh dua hasil kunci: keterulisan ulang orde pertama untuk DL-Lite, dan kekerasan PTime dari kompleksitas data untuk hampir setiap logika deskripsi di luar itu. Dikotomi AC0 vs. PTime ini menempatkan DL-Lite sebagai satu-satunya pilihan praktis untuk penulisan ulang kueri, membatasi solusi OMQA pada kueri orde pertama dan ontologi yang dapat ditulis ulang ke dalamnya. Namun, OMQA semakin menyasar data terstruktur graf, dan bahasa kueri graf standar—termasuk standar ISO terbaru GQL dan SQL/PGQ—umumnya NL-lengkap. Ketidaksesuaian ini memotivasi kebutuhan akan DL Horn yang lebih kaya yang dapat ditulis ulang menjadi bahasa kueri graf sekaligus tetap mengekspresikan banyak ontologi ELI dan DL-Lite. Para penulis mengatasi celah ini dengan memperkenalkan mekanisme stratifikasi untuk ELI yang mengendalikan interaksi antara konjungsi dan rekursi, menghasilkan ELbotpreceq, logika deskripsi yang secara ketat memperluas DL-Lite inti, mendukung aksioma keterjangkauan dan konjungsi terbatas, serta memungkinkan penalaran dalam NL.

Hasil utamanya adalah ELbotpreceq menikmati kompleksitas data NL untuk penjawaban kueri. Hal ini ditetapkan melalui penulisan ulang menjadi nested two-way regular path queries, yang dievaluasi dalam NL. Para penulis menunjukkan bahwa ELbotpreceq secara ketat memperluas DL-Lite, artinya setiap ontologi DL-Lite dapat diekspresikan dalam ELbotpreceq, tetapi tidak sebaliknya. Lebih lanjut, ELbotpreceq mendukung aksioma keterjangkauan dan konjungsi terbatas, yang tidak dapat diekspresikan dalam DL-Lite. Penulisan ulang bersifat konstruktif dan dapat diimplementasikan menggunakan mesin kueri graf standar. Makalah ini juga menunjukkan bahwa ELbotpreceq dapat mengekspresikan banyak ontologi ELI, sehingga menyediakan formalisme kaya yang menjembatani celah antara DL-Lite dan DL yang lebih ekspresif. Batas atas NL dibuktikan melalui reduksi dari penjawaban kueri dalam ELbotpreceq ke evaluasi n2RPQs, yang berada di NL. Para penulis juga menunjukkan bahwa batas bawahnya NL-keras, sehingga kompleksitasnya ketat.