Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This work is aimed to show a concrete implementation of a deductive database system based on the scheme HH_(C) (Hereditary Harrop Formulas with Negation and Constraints) following a fixpoint semantics proposed in a previous work. We have developed a Prolog implementation for this scheme that is constraint system independent, therefore allowing to use it as a base for any instance of the formal scheme. We have developed several specific constraint systems: Real numbers, integers, Boolean and user-defined enumerated types. We have added types to the database so that relations become typed (as tables in relational databases) and each constraint is mapped to its corresponding constraint system. The predicates that compute the fixpoint giving the meaning to a database are described. In particular, we show the implementation of a forcing relation (for derivation steps) and highlight how the inherent difficulties have been overcome in a system allowing hypothetical queries, which make the database dynamically grow.

REFERENCES

• 1: Faiz Arni , Kayliang Ong , Shalom Tsur , Haixun Wang , Carlo Zaniolo, The deductive database system ℒ𝒟ℒ++, Theory and Practice of Logic Programming, v.3 n.1, p.61-94, January 2003 [doi>10.1017/S1471068402001515]
• 2: Moritz Becker , Cedric Fournet , Andrew Gordon, Design and Semantics of a Decentralized Authorization Language, Proceedings of the 20th IEEE Computer Security Foundations Symposium, p.3-15, July 06-08, 2007 [doi>10.1109/CSF.2007.18]
• 3: Catriel Beeri , Raghu Ramakrishnan, On the power of magic, Journal of Logic Programming, v.10 n.3-4, p.255-299, April/May 1991 [doi>10.1016/0743-1066(91)90038-Q]
• 4: Andrea Calì , Georg Gottlob , Thomas Lukasiewicz, Datalog^±: a unified approach to ontologies and integrity constraints, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia [doi>10.1145/1514894.1514897]
• 5: C. Castro and E. Monfroy. Designing hybrid cooperations with a component language for solving optimisation problems. In International Conference on Artificial Intelligence: Methodology, Systems and Applications 2004, volume 3192 of LNCS, pages 447--458. Springer, 2004.
• 6: R. Fikes, P.J. Hayes, and I. Horrocks. OWL-QL -- a language for deductive query answering on the Semantic Web. Journal of Web Semantics, 2 (1): 19--29, 2004. URL http://www.informatik.uni-trier.de/~ley/db/journals/ws/ws2.html#F%ikesHH04.
• 7: M. García-Díaz and S. Nieva. Solving Constraints for an Instance of an Extended CLP Language over a Domain based on Real Numbers and Herbrand Terms. Journal of Functional and Logic Programming, 2003 (2), September 2003.
• 8: L. Granvilliers, E. Monfroy, and F. Benhamou. Cooperative solvers in constraint programming: a short introduction. ALP Newsletter, 14 (2), 2001.
• 9: Petra Hofstedt , Peter Pepper, Integration of declarative and constraint programming, Theory and Practice of Logic Programming, v.7 n.1-2, p.93-121, January 2007 [doi>10.1017/S1471068406002833]
• 10: C. Holzbaur. Realization of forward checking in logic programming through extended unification. Report TR-90-11, Oesterreichisches Forschungsinstitut fuer. Artificial Intelligence, 1990.
• 11: M. Jarke, M. A. Jeusfeld, and C. Quix. ConceptBase V7.1 User Manual. Technical report, RWTH Aachen, April 2008.
• 12: Monica S. Lam , John Whaley , V. Benjamin Livshits , Michael C. Martin , Dzintars Avots , Michael Carbin , Christopher Unkel, Context-sensitive program analysis as database queries, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065169]
• 13: Javier Leach , Susana Nieva , Mario Rodríguez-Artalejo, Constraint Logic Programming with Hereditary Harrop formulas, Theory and Practice of Logic Programming, v.1 n.4, p.409-445, July 2001 [doi>10.1017/S1471068401001041]
• 14: Nicola Leone , Gerald Pfeifer , Wolfgang Faber , Thomas Eiter , Georg Gottlob , Simona Perri , Francesco Scarcello, The DLV system for knowledge representation and reasoning, ACM Transactions on Computational Logic (TOCL), v.7 n.3, p.499-562, July 2006 [doi>10.1145/1149114.1149117]
• 15: S. Nieva, F. Sáenz-Pérez, and J. Sánchez. Towards a constraint deductive database language based on hereditary harrop formulas. In P. Lucio and F. Orejas, editors, Sextas Jornadas de Programación y Lenguajes, PROLE, pages 171--182, 2006.
• 16: S. Nieva, F. Sáenz-Pérez, and J. Sánchez. Formalizing a Constraint Deductive Database Language based on Hereditary Harrop Formulas with Negation. In FLOPS'08, Proceedings, volume 4989 of Lecture Notes in Computer Science, pages 289--304, Ise, Japan, 2008. Springer-Verlag.
• 17: Proceedings of the 2007 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 2007
• 18: Royi Ronen , Oded Shmueli, Evaluating very large datalog queries on social networks, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia [doi>10.1145/1516360.1516427]
• 19: F. Sáenz-Pérez. Datalog Educational System. User's Manual version 1.6.2. Technical report, Faculty of Computer Science, UCM, march 2009. Available from http://des.sourceforge.net/.
• 20: Konstantinos Sagonas , Terrance Swift , David S. Warren, XSB as an efficient deductive database engine, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.442-453, May 24-27, 1994, Minneapolis, Minnesota, United States
• 21: Yi-Dong Shen , Li-Yan Yuan , Jia-Huai You, SLT-Resolution for the Well-Founded Semantics, Journal of Automated Reasoning, v.28 n.1, p.53-97, January 2002 [doi>10.1023/A:1020116927466]
• 22: Hisao Tamaki , Taisuke Sato, OLD resolution with tabulation, Proceedings on Third international conference on logic programming, p.84-98, September 1986, London, United Kingdom
• 23: Allen Van Gelder , Kenneth A. Ross , John S. Schlipf, The well-founded semantics for general logic programs, Journal of the ACM (JACM), v.38 n.3, p.619-649, July 1991 [doi>10.1145/116825.116838]
• 24: J. Wielemaker. SWI-Prolog. User's Manual version 5.6.64, 2009. Available from http://www.swi-prolog.org/.
• 25: Carlo Zaniolo , Stefano Ceri , Christos Faloutsos , Richard Thomas Snodgrass , V. S. Subrahmanian , Roberto Zicari, Advanced database systems, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics

General Terms:
Algorithms, Languages

Keywords:
constraints, deductive databases, fixpoint semantics, hereditary harrop formulas, prolog, stratification