Conflict resolution of rules assigning values to virtual attributes

ABSTRACT

In the majority of research work done on logic programming and deductive databases, it is assumed that the set of rules defined by the user is consistent, i.e., that no contradictory facts can be inferred by the rules. In this paper, we address the problem of resolving conflicts of rules that assign values to virtual attributes. We devise a general framework for the study of the problem, and we propose an approach that subsumes all previously suggested solutions. Moreover, it suggests several additional solutions, which very often capture the semantics of the data more accurately than the known approaches. Finally, we address the issue of how to index rules so that conflicts are resolved efficiently, i.e., only one of the applicable rules is processed at query time.

REFERENCES

• Aho79: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• Blai88: Blair, H. A., A. L. Brown, and V. $' Subtahmanian, "A Logic Programming Semantics Scheme, Part I", Tech. Report, LPRG-TR-88-8, School of Computer and Information Science, Syracuse University, April 1988.
• Borg85: Alexander Borgida, Language features for flexible handling of exceptions in information systems, ACM Transactions on Database Systems (TODS), v.10 n.4, p.565-603, Dec. 1985 [doi>10.1145/4879.4995]
• Borg88: A. Borgida, Modeling class hierarchies with contradictions, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.434-443, June 01-03, 1988, Chicago, Illinois, United States
• Forg79: Charles Lanny Forgy, On the efficient implementation of production systems., 1979
• Kife89: M. Kifer , E. Lozinskii, RI: A logic for reasoning with inconsistency, Proceedings of the Fourth Annual Symposium on Logic in computer science, p.253-262, June 1989, Pacific Grove, California, United States
• Kung86: R-M Kung , E Hanson , Y Ioannidis , T Sellis , L Shapiro , M Stonebraker, Heuristic search in database systems, Proceedings from the first international workshop on Expert database systems, p.537-548, January 1986, Kiawah Island, South Carolina, United States
• Nico78: Nicolas, J. M. and H. Gallaire, "Data Base: Theory vs. Interpretation", in Logic and Data Bases, edited by H. Gallake and J. Minker, Plenum Press, New York, N.Y., 1978, pp. 33-54.
• Sell87: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• Shor76: Shortliffe, E. H., Computer-based Medical Consultations: MYC/N, Elsevier, New York, NY, 1976.
• Ston86a: Stonebraker, M., T. SeUis, and E. Hanson, "An Analysis of Rule Indexing Implementations in Data Base Systems", in Proc. of the 1st International Conference on Expert Database Systems, Charleston, SC, April 1986, pp. 353-364.
• Ston86b: Michael Stonebraker , Lawrence A. Rowe, The design of POSTGRES, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.340-355, May 28-30, 1986, Washington, D.C., United States
• Ston88: Michael Stonebraker , Eric N. Hanson , Spyros Potamianos, The POSTGRES Rule Manager, IEEE Transactions on Software Engineering, v.14 n.7, p.897-907, July 1988 [doi>10.1109/32.42733 ]
• Tars55: Tarski, A., "A Lattice Theoretical Fixpoint Theorem and its Applications", Pacific Journal of Mathematics 5 (1955), pp. 285-309.
• VanE76: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Theory