Skip to main content

Database query evaluation with the STARBASE method

Estrella Pulido, Database query evaluation with the STARBASE method. CSTR-95-022, Department of Computer Science, University of Bristol. October 1995. No electronic version available.

Abstract

This paper presents STARBASE, a new method for database query evaluation which compares favourably with existing methods in power, performance and applicability. STARBASE advances the state of the art in deductive database technology by providing an automatic method for reordering the literals in the body of a rule so that the next literal to be processed is guaranteed to be one of the most instantiated ones. Being graph-based, STARBASE demonstrates for the first time that graphical methods can compete with resolution-based methods in power and performance. he paper describes a prototype implementation of a STARBASE system consisting of (1) an optimising rule compiler which transforms rules into optimal path specifications, and (2) an evaluation algorithm which uses the path specifications relevant to a given query to find all matching subgraphs in the database. Performance is compared to XSB and CORAL for a range of examples. The prototype implementation is restricted to Datalog programs, but can be extended to stratified programs. The main features of STARBASE which guarantee high performance are (1) it focuses on data relevant to the query, (2) it avoids redundant computation and looping by storing partial results, and (3) it replaces subsumption checking (NP complete) with syntactic equality checking (logarithmic).

Bibtex entry.

Publication Admin