Implementing a fixed point semantics for a constraint deductive database based on hereditary harrop formulas

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Implementing a fixed point semantics for a constraint deductive database based on hereditary harrop formulas

Full text

Pdf (245 KB)

Source

International Conference on Principles and Practice of Declarative Programming archive
Proceedings of the 11th ACM SIGPLAN conference on Principles and practice of declarative programming table of contents

Coimbra, Portugal

SESSION: Expressive logics table of contents

Pages 117-128

Year of Publication: 2009

ISBN:978-1-60558-568-0

Authors

Gabriel Aranda-López	Universidad Complutense, Madrid, Spain
Susana Nieva	Universidad Complutense, Madrid, Spain
Fernando Sáenz-Pérez	Universidad Complutense, Madrid, Spain
Jaime Sánchez-Hernández	Universidad Complutense, Madrid, Spain

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 7, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1599410.1599426 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	F. Arni, K. Ong, S. Tsur, Haixun Wang, and C. Zaniolo. The Deductive Database System LDL. Theory and Practice of Logic Programming, 3 (1): 61--94, 2003.
	2	M. Becker, C. Fournet, and A. Gordon. Design and Semantics of a Decentralized Authorization Language. In CSF '07: Proceedings of the 20th IEEE Computer Security Foundations Symposium, pages 3--15, Washington Francesco, DC, USA, 2007. IEEE Computer Society. ISBN 0-7695-2819-8. http://dx.doi.org/10.1109/CSF.2007.18.
	3	C. Beeri and R. Ramakrishnan. On the power of magic. Journal of Logic Programming, 10 (3-4): 255--299, 1991. ISSN 0743-1066. http://dx.doi.org/10.1016/0743-1066(91)90038-Q.
	4	A. Calí, G Gottlob, and T. Lukasiewicz. Datalog±: a unified approach to ontologies and integrity constraints. In ICDT '09: Proceedings of the 12th International Conference on Database Theory, pages 14--30, New York, NY, USA, 2009. ACM. ISBN 978-1-60558-423-2. http://doi.acm.org/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	P. Hofstedt and P. Pepper. Integration of declarative and constraint programming. Theory and Practice of Logic Programming, 7 (1-2): 93--121, 2007. ISSN 1471-0684. http://dx.doi.org/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	M.S. Lam, S. Whaley, B.V. Livshits, M.C. Martin, D. Avots, M. Carbin, and C. Unkel. Context-sensitive program analysis as database queries. In Chen Li, editor, Symposium on Principles of Database Systems (PODS), pages 1--12. ACM, 2005. ISBN 1-59593-062-0.
	13	J. Leach, S. Nieva, and M. Rodríguez-Artalejo. Constraint Logic Programming with Hereditary Harrop Formulas. Theory and Practice of Logic Programming, 1 (4): 409--445, 2001.
	14	N. Leone, G. Pfeifer, W. Faber, T. Eiter, G. Gottlob, S. Perri, and F. Scarcello. The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic, 7 (3): 499--562, 2006.
	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	G. Ramalingam and Eelco Visser, editors. Proceedings of the 2007 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-based Program Manipulation, 2007, Nice, France, January 15-16, 2007, 2007. ACM. ISBN 978-1-59593-620-2.
	18	R. Ronen and O. Shmueli. Evaluating very large datalog queries on social networks. In EDBT '09: Proceedings of the 12th International Conference on Extending Database Technology, pages 577--587, New York, NY, USA, 2009. ACM. ISBN 978-1-60558-422-5. http://doi.acm.org/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	K. Sagonas, T. Swift, and D.S. Warren. XSB as an efficient deductive database engine. In SIGMOD '94: Proceedings of the 1994 ACM SIGMOD international conference on Management of data, pages 442--453, New York, NY, USA, 1994. ACM. ISBN 0-89791-639-5. http://doi.acm.org/10.1145/191839.191927.
	21	Y. Shen, L. Yuan, and J. You. Slt-resolution for the well-founded semantics. Journal of Automated Reasoning, 28: 53--97, 2002.
	22	H. Tamaki and T. Sato. Old resolution with tabulation. In Proceedings on Third international conference on logic programming, pages 84--98, New York, NY, USA, 1986. Springer-Verlag New York, Inc. ISBN 0-387-16492-8.
	23	A. Van Gelder, K.A. Ross, and J.S. Schlipf. The well-founded semantics for general logic programs. J. ACM, 38 (3): 619--649, 1991. ISSN 0004-5411. http://doi.acm.org/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	C. Zaniolo, S. Ceri, C. Faloutsos, R.T. Snodgrass, V.S. Subrahmanian, and R. Zicari. Advanced Database Systems. Pages 180--183, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1997. ISBN 1-55860-443-X.