Abstrakt. Vi anser att frågesvar med hjälp av vyer på grafdatabaser, dvs.. databaser som är strukturerade som kantmärkta grafer. Vi överväger huvudsakligen vyer och frågor som specificeras av Regular Path Queries (RPQ). Dessa är frågor välja par av noder i en graf databas som är anslutna via en sökväg vars sekvens av kant etiketter tillhör vissa vanliga språk. Vi säger att en vy V bestämmer en fråga Q om för alla grafdatabaser D, visar bilden V(D) alltid innehåller tillräckligt med information för att svara Q på D. Med andra ord, det finns en väl definierad funktion från V(D) till Q(D). Vårt huvudresultat visar att när denna funktion är monoton, det finns en omskrivning av Q som en Datalog fråga över vyn instans V(D). I synnerhet kan omskrivningsfrågan utvärderas i tid polynom i storleken på V(D). Dessutom innebär detta att det går att avgöra om en RPQ-fråga kan skrivas om i Datalog med hjälp av RPQ-vyer.
För det andra bevisade REF att regelbundna sökvägar alltid kan skrivas om som Datalog frågor med hjälp av regelbundna sökvägar vyer, antar monotona determinacy.
Datalog Rewritings of Regular Path Queries using Views
{'venue': 'Logical Methods in Computer Science, Volume 11, Issue 4 (December 22, 2015) lmcs:1615', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}