Negation and Exclusionary Queries in Databases
Computer & Information Systems Department
Robert Morris University

Contacts: harvey@rmu.edu (Valerie J. Harvey, R.T.(R), Ph.D.), baugh@rmu.edu (Jeanne M. Baugh, Ed.D.)

INFS4240/4241/6240 - Please review these topics and query/condition/syntax examples.

Database Negation I: SQL and Negation,
Exclusionary Queries
Negation in Relational Databases

Types of queries/conditions/syntax to study:

  • where not A = B [note placement of not operator]
  • where A not null
  • where not (A between B and C)
  • where A not in (select <nested query>)
  • except (SQL standard), minus (Oracle)

Topics

  • Negation as opposite (Boolean) truth value
  • Negation in nested queries: set difference – see also: Rick Chow, Division of Math and Computer Science, University of South Carolina Spartanburg: http://www.uscs.edu/~rchow/sims421/Review/SQLReview.ppt (slides 20-22) and
    Andrew Pletch, Computer Science, SUNY New Paltz: http://www.mcs.newpaltz.edu/~pletch/libsqlnotes.pdf . Negation in SQL queries is also covered in Jalal Kawash, University of Calgary, in “Writing Complex SQL Queries that Require Universal Quantifiers” at: http://pages.cpsc.ucalgary.ca/~kawash/papers/wccce00.html
  • Negation in nested queries with composites.
  • Closed-World Assumption (CWA; please see [ULL1988:25]), “negation as failure,” [GRA1996:218] and two forms of negation: Gerd Wagner, Eindhoven University of Technology, Faculty of Technology Management. [WAG1991]
  • Formal specification of sets, relations, and functions (note: source vs. domain, target vs. range; domain and range restriction and subtraction, total vs. partial functions; see Potter et al.)
  • DeMorgan's Laws
  • Contrapositives
  • SQL operators: NOT, MINUS (Oracle), EXCEPT

References and Links:

[GRA1996] Winfried Karl Grassmann and Jean-Paul Temblay, Logic and Discrete Mathematics: A Computer Science Perspective (Prentice Hall, 1996)

[MEL2002] Jim Melton and Alan R. Simon, SQL:1999: Understanding Relational Language Components (Morgan Kaufman, 2002).

[POT1991] Ben Potter, Jane Sinclair, and David Till, An Introduction to Formal Specification and Z (Prentice Hall International, 1991).

[ULL1988] Jeffrey D. Ullman, Principals of Database and Knowledge-Base Systems, Vol. I (Computer Science Press, 1988).

[WAG2003] Gerd Wagner, “The Semantic Web Needs Two Kinds of Negation,” technical report at http://tmitwww.tm.tue.nl/staff/gwagner/myruleml/SemWebNeg.pdf.

 

[WAG1991] G. Wagner, “A database needs two kinds of negation.” In B. Thalheim and H.-D. Gerhardt, editors, Proc. of the 3rd. Symp. on Mathematical Fundamentals of Database and Knowledge Base Systems, volume 495 of Lecture Notes in Computer Science, pages 357–371. Springer-Verlag, 1991.

[HAR2003] Valerie J. Harvey, Jeanne M. Baugh, Bruce A. Johnston, Constance M. Ruzich, A. J. Grant, "The Challenge of Negation in Searches and Queries," 2003 International Applied Business Research Conference, Acapulco, Guerrero, Mexico, March, 2003. Published in conference proceedings.

[HAR2003c] Valerie J. Harvey, Jeanne M. Baugh, Bruce A. Johnston, Constance M. Ruzich, A. J. Grant, "The Challenge of Negation in Searches and Queries," The Review of Business Information Systems 7, 4 (Fall 2003): 63-75.

[HAR2003d] Valerie J. Harvey, Constance M. Ruzich, Jeanne M. Baugh, Bruce A. Johnston, and A. J. Grant, "The Challenge of Negation in Health Care Searches and Queries," Poster Session, November 11, 2003, at the 2003 Fall Symposium of the American Medical Informatics Association (AMIA), Washington, DC.

Database Negation II: VA FileMan and Negation,
Exclusionary Queries

From VA FileMan User Manual, Getting Started - for VA FileMan version 22:

See section on searches of multiple-valued fields.

When truth tests contain a negative (contains an apostrophe or single quote "'"), you can even specify that an entry with no subentries should automatically pass the test.

Note user prompt (p. 3-14) and particularly the third option:

IF: A&'B DATE OF BIRTH LESS THAN 1900 (1900)
and not PATIENT DIAGNOSIS CONTAINS ":ANGINA"
DO YOU WANT THIS SEARCH SPECIFICATION TO BE CONSIDERED TRUE FOR CONDITION -B-
1) WHEN AT LEAST ONE OF THE 'DIAGNOSIS' MULTIPLES SATISFIES IT
2) WHEN ALL OF THE 'DIAGNOSIS' MULTIPLES SATISFY IT
3) WHEN ALL OF THE 'DIAGNOSIS' MULTIPLES SATISFY IT,
OR WHEN THERE ARE NO 'DIAGNOSIS' MULTIPLES
CHOOSE 1-3: 1//

Contrast this example with those where no negation is used.

References and Links:

http://www.hardhats.org (VA FileMan documentation available at this site.)

http://www.worldvista.org

[HAR2003b] Valerie J. Harvey, Connie M. Ruzich, Jeanne M. Baugh, "Exclusionary Queries in Health Care," WorldVistA Community Event (conference on hospital information systems), Greenbelt, MD, March, 2003.

Database Negation III:
Negation in InterSystems Caché ObjectScript and M

Use of negation (' operator) and the $DATA function to check for the presence of paths in an (associative) array.

Example:

IF '$DATA(^INVENTORY(4361, "ONSALE"))...
which could mean "if inventory item 4361 is not on sale"

Note the Closed-World Assumption here and "negation as failure" as also used in SQL and in logic programming (Prolog).

Please consider database design strategies which take this use into account.

References and Links:

[KIR2000] Wolfgang Kirsten, Michael Ihringer, Bernhard Röhrig, and Peter Schulte, Object-Oriented Application Development Using the Caché Postrelational Database (Springer, 2001) German version: Objecktorientierte Andwendingsentwicklung mit der postrelationalen Datenbank Caché (Springer, 1999)

Database Negation IV:
Negation in Prolog

Note the Closed-World Assumption here and "negation as failure" as used in logic programming (Prolog).

Please consider database design strategies which take this use into account.

References and Links:

[GRA1996: Section 4.5, pp. 215-218] Winfried Karl Grassmann and Jean-Paul Temblay, Logic and Discrete Mathematics: A Computer Science Perspective (Prentice Hall, 1996)