liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Semantic query optimization in the presence of types
University of Freiburg, Germany.
University of Freiburg, Germany.
University of Freiburg, Germany.
University of Freiburg, Germany.
2013 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 79, no 6, 937-957 p.Article in journal (Refereed) Published
Abstract [en]

Both semantic and type-based query optimization rely on the idea that queries may exhibit non-trivial rewritings if the state space of the database is restricted. While these two problems have always been studied as separate problems in previous work, in this paper we present a unifying, logic-based query optimization framework that builds upon the classical chase algorithm and brings both problems together. As a major challenge, our novel setting requires chasing conjunctive queries with union and negation in the presence of dependencies containing negation and disjunction. Tackling this problem, we study the applicability of the chase in this setting, develop novel conditions that guarantee its termination, identify fragments for which minimal query computation (w.r.t. a generic cost function) is always possible, and investigate the complexity of related decision problems.

Place, publisher, year, edition, pages
Elsevier, 2013. Vol. 79, no 6, 937-957 p.
Keyword [en]
Systems – relational databases; Query processing; Query optimization; Types; Constraints; Chase
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:liu:diva-94572DOI: 10.1016/j.jcss.2013.01.010OAI: oai:DiVA.org:liu-94572DiVA: diva2:633278
Available from: 2013-06-26 Created: 2013-06-26 Last updated: 2017-12-06Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Wei, Fang

Search in DiVA

By author/editor
Wei, Fang
In the same journal
Journal of computer and system sciences (Print)
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 35 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf