Negatywna informacja w języku regułowym 4QL

• Autorzy: Małuszyński J. , Szałas A.

Warianty tytułu

EN

Negative information in a rule-based language 4QL

• Języki publikacji: PL

Abstrakty

EN

Problematyka negatywnej informacji w językach regułowych jest zasadnicza z punktu widzenia dużej liczby aplikacji. Była ona rozważana w rozszerzeniach języków zapytań w dedukcyjnych bazach danych, opartych na wnioskowaniach niemonotonicznych, początkowo wynikających z założenia o zamkniętym świecie CWA (Closed World Assumption). W wielu zastosowaniach, w tym związanych z Semantycznym Internetem i robotyką, założenie CWA nie jest właściwe i zwykle przyjmuje się w nich założenie o świecie otwartym OWA (Open World Assumption). W niniejszym artykule omawiamy nowe podejście do tego problemu, przedstawione w [2] [3] [4], gdzie zaproponowaliśmy język regułowy 4QL w stylu Datalogu, jednak bez ograniczeń na wystąpienie negacji. Język ma architekturę warstwową. Najniższe warstwy 4QL, oparte na OWA, są w pełni monotoniczne. W celu zmniejszenia stref niewiedzy/sprzeczności w [2] [3] wprowadzono proste konstrukcje pozwalające na wyrażanie mechanizmów wnioskowań niemonotonicznych, w tym umożliwiających rozwiązywanie sprzeczności, użycie lokalnych domknięć świata (a więc także CWA) oraz różnych form wnioskowań przez domniemania. Obliczanie zapytań w 4QL ma złożoność wielomianową ze względu na rozmiar bazy danych.

The problem of negative information in rule languages is crucial in many applications. It has been addressed in extensions of query languages in deductive databases, based on nonmonotonic logics initially derived from the Closed World Assumption (CWA). In many applications, including Semantic Web technologies and robotics systems, CWA is not necessarily applicable and developments in these fields usually follow the Open World Assumption (OWA). In this paper we summarize a novel approach to the problem reported in [2] [3] [4], where we proposed a DATALOG-like language 4QL with unrestricted negation. The language supports a layered architecture. The monotonic layer of 4QL, based on OWA, is fully monotonic. To reduce the unknown/inconsistent zones, in [2] [3] we have introduced simple constructs which allow one to express various mechanisms of nonmonotonic reasoning. In particular, this provides means for application-specific disambiguation of inconsistent information, the use of Local CWA (thus also CWA, if needed), and various forms of default reasoning. Query evaluation in 4QL is still tractable as regards its data complexity.

Słowa kluczowe

PL

regułowe języki zapytań; wnioskowanie niemonotoniczne; informacja negatywna; informacja sprzeczna; informacja niepełna

EN

rule-based query languages; nonmonotonic reasoning; negative information; inconsistent information; incomplete information

• Wydawca: Warszawska Wyższa Szkoła Informatyki
• Czasopismo: Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki
• Rocznik: 2013
• Tom: nr 9
• Strony: 7--14
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Małuszyński J.

• Uniwersytet w Linkopingu

autor

Szałas A.

• Uniwersytet w Linkopingu
• Uniwersytet Warszawski

Bibliografia

• [1] Abiteboul S., Hull R., Vianu V., Foundations of Databases, Addison-Wesley Pub. Co., Reading 1996
• [2] Małuszyński J., Szałas A., Living with inconsistency and taming nonmonotonicity, Datalog Reloaded, LNCS 6702, Springer-Verlag, 2011, s. 384-398, http://dx.doi.org/10.1007/978-3-642-24206-9_22
• [3] Małuszyński J., Szałas A., Logical foundations and complexity of 4QL, a query language with unrestricted negation, “Journal of Applied Non-Classical Logics” 2011, Vol. 21 (2), s. 211-232, http://dx.doi.org/10.3166/jancl.21.211-232
• [4] Małuszyński J., Szałas A., Partiality and Inconsistency in Agents’ Belief Bases, Proceedings of KES-AMSTA, Frontiers of Artificial Intelligence and Applications, IOS Press, 2013
• [5] Małuszyński J., Szałas A., Vitória A., Paraconsistent logic programs with four-valued rough sets, w: Rough Sets and Current Trends in Computing, (red.) Chan C.-C., Grzymala-Busse J., Ziarko, Proceedings of 6th International Conference, RSCTC 2008, LNAI 5306, Springer-Verlag, Berlin-Heidelberg 2008, s. 41-51, http://dx.doi.org/10.1007/978-3-540-88425-5_5
• [6] Szałas A., How an Agent Might Think, “Logic Journal of IGPL” 2013, http://dx.doi.org/ 10.1093/jigpal/jzs05