Evaluation of Recursive Queries with Extended Rules in Deductive Databases

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

In order to extend the expressive power of deductive databases, a formula that can have existential quantifiers in prenex normal form in a restricted way is defined as an extended rule. With the extended rule, we can easily define a virtual view that requires a division operation of relational algebra to evaluate. This paper addresses a recursive query evaluation where at least one formula in a recursive rule set is of an extended rule. We investigate transformable recursions as well as four cases of non-transformable recursions of transitive-closure-like and linear type. This work reveals that occurrence of an existentially quantified variable in the extended recursive body predicate might dramatically limit the level of recursive search. In particular, the number of iterations to answer extended queries can be determined, independently of database contents.

Original languageEnglish (US)
Pages (from-to)328-331
Number of pages4
JournalIEEE Transactions on Knowledge and Data Engineering
Volume7
Issue number2
DOIs
StatePublished - Jan 1 1995

Keywords

  • DBMS
  • Deductive databases
  • automated reasoning
  • extended rules
  • query processing
  • recursive queries

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Evaluation of Recursive Queries with Extended Rules in Deductive Databases'. Together they form a unique fingerprint.

  • Cite this