×

zbMATH — the first resource for mathematics

Logic programming with sets. (English) Zbl 0694.68013
Summary: We propose an extension to logic programming called LPS (Logic Programming with Sets). The LPS language has two types of objects: individual objects, and sets whose elements are individual objects. We first consider only one level of set nesting in order to concentrate on the key problems that arise, in as simple a framework as possible. The rules in the LPS language are fairly similar to the Horn clauses of logic programming. The main difference between LPS rules and Horn clauses is that the right-hand side of a LPS rule may be preceded by restricted universal quantifiers. This means that a LPS rule has the form \[ A:- (\forall x_ 1\in X_ 1)...(\forall x_ n\in X_ n)(B_ 1\wedge...\wedge B_ m). \] This is a fairly conservative extension of Horn clause logic, since whenever the sets \(X_ 1,...,X_ n\) have known values, the body can be reduced to a normal Horn clause, i.e., the conjunction of the body (without the quantifiers) over all the elements of the sets. We shall see that our extension of Horn clause logic, unlike extensions that allow arbitrary quantification on the right-hand side, preserves the semantics of Horn clause logic.

MSC:
68N01 General topics in the theory of software
68T99 Artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Apt, K.R.; Blair, H.; Walker, A., Towards a theory of declarative logic, ()
[2] Aho, A.V.; Ullman, J.D., Universality of data retrieval languages, (), 110-120
[3] Bancilhon, F.; Khoshafian, S., A calculus for complex objects, (), 53-59
[4] Bancilhon, F.; Maier, D.; Sagiv, Y.; Ulmann, J.D., Magic sets and other strange ways to implement logic programs, (), 1-15
[5] Beeri, C.; Naqvi, S.; Ramakrishnan, R.; Shmueli, O.; Tsur, S., Sets and negation in a logic database language (LDLI), (), 21-37
[6] Gallaire, H.; Minker, J., Logic and databases, (1978), Plenum New York
[7] Henschen, L.J.; Naqvi, S.A., On compiling queries in recursive first-order databases, J. assoc. comput. Mach., 31, No. 1, 47-85, (1984) · Zbl 0629.68095
[8] Hull, R.; Yap, C.K., The format model: A theory of database organization, (), 205-211
[9] Jaeschke, G.; Schek, H.-J., Remarks on the algebra of non first normal form relations, (), 124-138
[10] Kowalski, R., Logic for problem solving, (1979), North-Holland Amsterdam · Zbl 0426.68002
[11] Kuper, G.M., An extension of LPS to arbitrary sets, ()
[12] Kuper, G.M., Logic programming with sets, () · Zbl 0694.68013
[13] Kuper, G.M., LPS: A logic programming language for nested relations, ()
[14] Kuper, G.M.; Vardi, M.Y., A new approach to database logic, (), 86-96
[15] Lloyd, J.W.; Topor, R.W., Making PROLOG more expressive, J. logic programm., 1, No. 3, 225-240, (1984) · Zbl 0584.68022
[16] Naish, L., Automatric generation of control for logic programs, ()
[17] Ozsoyoglu, Z.M.; Yuan, L.-Y., A normal form for nested relations, (), 251-260
[18] Reiter, R., Deductive question answering in relational databases, (), 147-177
[19] Rafanelli, M.; Ricci, F.L., A data definition language for a statistical database, Technical report TR-62, IASI-CNR, (July 1983)
[20] Shmueli, O.; Naqvi, S., Set grouping and layering in Horn clause programs, (), 152-177
[21] Scheck, H.-J.; Pistor, P., Data structures for an integrated data base management and information retrieval system, ()
[22] Smith, J.M.; Smith, D.C.P., Database abstractions: aggregation and generalization, ACM trans. database systems, 2, No. 2, 105-133, (1977)
[23] Tsur, S.; Zaniolo, C., LDL: A logic-based data-language, (), 33-41
[24] Ullman, J.D., Implementation of logical query languages for databases, () · Zbl 0573.68060
[25] Van Emden, M.H.; Kowalski, R.A., The semantics of predicate logic as a programming language, J. assoc. comput. Mach., 23, No. 4, 733-742, (1976) · Zbl 0339.68004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.