Vi studerar komplexiteten i att räkna upp svaren på konjunktiva frågor (CQs) i närvaro av funktionella beroenden (FDs). Vårt fokus ligger på förmågan att lista utdata tuples med en konstant fördröjning mellan, efter en linjär-tid förbehandling. En känd dikotomi klassificerar de acykliska själv-join-fria CQ:erna till dem som erkänner en sådan uppräkning, och de som inte gör det. Denna klassificering gäller dock inte längre i det vanliga fallet där databasen uppvisar beroenden mellan attribut. Det vill säga, en del frågor som klassificeras som svåra är i själva verket lättåtkomliga om man tar hänsyn till beroenden. Vi etablerar en generalisering av dikotomi för att rymma FDs; därför bestämmer vår klassificering vilken kombination av en CQ och en uppsättning FDs medger konstant-fördröjning uppräkning med en linjär-tid förbehandling. Dessutom generaliserar vi ett hårdhetsresultat för cykliska CQs för att rymma unary FDs, och ytterligare slutsatser av vår utveckling inkluderar en dikotomi för uppräkning med linjär fördröjning. Slutligen visar vi att alla våra resultat gäller även för CQ:er med ojämlikheter och i närvaro av kardinalitetsberoenden som generaliserar FD:er.
En generalisering av detta resultat tillgodoser funktionella beroenden REF.
Enumeration Complexity of Conjunctive Queries with Functional Dependencies
{'venue': 'Theory of Computing Systems', 'journal': 'Theory of Computing Systems', 'mag_field_of_study': ['Mathematics', 'Computer Science']}