Abstrakt. Vi studerar problemet med att besvara frågor över källor med begränsade tillträdesmönster. Problemet är att avgöra om en given fråga Q är möjlig, dvs. motsvarar en körbar fråga Q som observerar de begränsade åtkomstmönster som ges av källorna. Vi karakteriserar komplexiteten i att besluta genomförbarhet för klasserna CQ ¬ (konjunktiva frågor med negation) och UCQ ¬ (unioner av CQ ¬ frågor): Test genomförbarhet är lika svårt som testning inneslutning och därför Π P 2 -fullständig. Vi erbjuder också en enhetlig behandling för CQ, UCQ, CQ ¬, och UCQ ¬ genom att utforma en enda algoritm som är optimal för var och en av dessa klasser. Dessutom visar vi hur man ofta kan undvika det värsta-fall komplexitet genom vissa approximationer: Vid kompilering-tid, även om en fråga Q inte är möjlig, kan vi effektivt hitta minimal körbar fråga som innehåller Q. För frågesvar på runtime, vi utformar en algoritm som kan rapportera kompletta svar även i fallet med ogenomförbara planer och som kan indikera för användaren graden av fullständighet för vissa ofullständiga svar.
I REF utsträcker vi dessa resultat till konjunktiva frågor med negation (CQ ¬ ) och föreningar av konjunktiva frågor med negation (UCQ ¬ ) och visar att för båda klasserna är avgörande genomförbarhet D P 2 -fullständig.
Processing Unions of Conjunctive Queries with Negation under Limited Access Patterns
{'venue': 'EDBT', 'journal': None, 'mag_field_of_study': ['Computer Science']}