Dyadic TGDs - A new paradigm for ontological query answering - Marte, Cinzia; Greco, Gianluigi; Manna, Marco; Guerriero, Francesca; Leone, Nicola (Università della Calabria, 2022)
Ontology-BasedQueryAnswering(OBQA)consistsinqueryingdata– bases bytakingontologicalknowledgeintoaccount.Wefocusona logical frameworkbasedonexistentialrulesor tuple generatingdepen- dencies (TGDs), alsoknownasDatalog±, whichcollectsthebasicde- cidable classesofTGDs,andgeneralizesseveralontologyspecification languages. While thereexistlotsofdifferentclassesintheliterature,inmost cases eachofthemrequiresthedevelopmentofaspecificsolverand, only rarely,thedefinitionofanewclassallowstheuseofexisting systems. Thisgapbetweenthenumberofexistentparadigmsandthe numberofdevelopedtools,promptedustodefineacombinationof Shy and Ward (twowell-knownclassesthatenjoygoodcomputational properties)withtheaimofexploitingthetooldevelopedfor Shy. Nevertheless,studyinghowtomergethesetwoclasses,wehavereal- ized thatitwouldbepossibletodefine,inamoregeneralway,the combinationofexistingclasses,inordertomakethemostofexisting systems. Hence, inthiswork,startingfromtheanalysisofthetwoaforemen- tioned existingclasses,wedefineamoregeneralclass,named Dyadic TGDs, thatallowstoextendinauniformandelegantwayallthede- cidable classes,whileusingtheexistentrelatedsystems.Atthesame time, wedefinealsoacombinationof Shy and Ward, named Ward+, and weshowthatitcanbeseenasaDyadicsetofTGDs. Finally,tosupportthetheoreticalpartofthethesis,weimplementa BCQ evaluationalgorithmfortheclass Ward+, thattakesadvantage of anexistingsolverdevelopedfor Shy.
Dottorato di Ricerca in Matematica e Informatica . Ciclo XXXIII
Keywords: Ontological Query Answering; Database query languages; Datalog; Tuple Generating Dependencies; Complexity