2010 · 17 citations · 40 references
ComputingComputer ScienceAlgorithmsDatabasesLogicLogic ProgrammingPredicate LogicQuery OptimizationQuery ProcessingType SystemsCost-based Query OptimizationDecision ProblemsQuery MinimizationSemantic Query OptimizationState-space StructureType ConstraintsType Theory
Both semantic and type-based query optimization rely on the idea that queries often exhibit non-trivial rewritings if the state space of the database is restricted. Despite their close connection, these two problems to date have always been studied separately. We present a unifying, logic-based framework for query optimization in the presence of data dependencies and type information. It builds upon the classical chase algorithm and extends existing query minimization techniques to considerably larger classes of queries and dependencies. In particular, our setting requires chasing conjunctive queries (possibly with union and negation) in the presence of dependencies containing negation and disjunction. We study the applicability of the chase in this setting, develop novel conditions that guarantee its termination, identify fragments for which minimal query computation is always possible (w.r.t. a generic cost function), and investigate the complexity of related decision problems.
40
Maurizio Lenzerini · 2002 · 2.5K citations
Answering queries using views: A survey
Alon Halevy · The VLDB Journal · 2001 · 1.5K citations
Logical foundations of object-oriented and frame-based languages
Michael Kifer, Georg Lausen, James C. Wu · Journal of the ACM · 1995 · 1.5K citations · Full text
Computing, Computer Science, Logic +14
Larry J. Stockmeyer · Theoretical Computer Science · 1976 · 1.3K citations