AN IMPROVED ALGORITHM FOR IMPLICATION TESTING INVOLVING ARITHMETIC INEQUALITIES

Wei Sun

doi:10.1109/69.334889

AN IMPROVED ALGORITHM FOR IMPLICATION TESTING INVOLVING ARITHMETIC INEQUALITIES

1994-01-01

2

PRE

AI

DOI：10.1109/69.334889

Original

Original request for help

Save

Abstract

En 中文

Implication testing of arithmetic inequalities has been widely used in different areas in database systems and has received extensive research as well. Klug and Ullman proposed an algorithm that determines whether S implies T, where T and S consist of inequalities of form (X op Y), X and Y are two variables, and op epsilon{=, <, less than or equal to, not equal, >, greater than or equal to}. The complexity of the algorithm is O(n(3)), where n is the number of inequalities in S. In this concise paper, we reduce the problem to matrix multiplication, thus improving the time bound to O(n(2.376)). We also demonstrate an O(n(2)) algorithm if the number of inequalities in T is bounded by O(n). Since matrix multiplication has been well studied, our reduction allows the possibility of directly adopting many practical results for managing matrices and their operations, such as parallel computation; and efficient representation of sparse matrices.

Keywords:

ARITHMETIC INEQUALITIES

DATABASE MANAGEMENT SYSTEMS

IMPLICATION TESTING

QUERY OPTIMIZATION

SATISFIABILITY

EQUIVALENCE

AN IMPROVED ALGORITHM FOR IMPLICATION TESTING INVOLVING ARITHMETIC INEQUALITIES

Abstract

AI Summary

Journal

Organization