research-article

On Armstrong-compliant logical query languages

Authors:

Christine Froidevaux,

Jean-Marc Petit,

Jef WijsenAuthors Info & Claims

LID '11: Proceedings of the 4th International Workshop on Logic in Databases

Pages 33 - 40

https://doi.org/10.1145/1966357.1966365

Published: 25 March 2011 Publication History

Abstract

We present a simple logical query language called R£ for expressing different kinds of rules and we study how this language behaves with respect to the well-known Armstrong's axioms. We point out some negative results, e.g. it is undecidable to know whether or not a query from this language is "Armstrong compliant". The main contribution of this paper is to exhibit a restricted form of R£-queries -- yet with a good expressive power -- for which Armstrong's axioms are sound. From this result, this sublanguage turns out to have structural and computational properties which have been shown to be very useful in data mining, databases and formal concept analysis.

References

[1]

S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison Wesley, 1995.

Digital Library

[2]

M. Agier, J.-M. Petit, and E. Suzuki. Unifying framework for rule semantics: Application to gene expression data. Fundam. Inform., 78(4):543--559, 2007.

Digital Library

[3]

R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. In ACM SIGMOD International Conference on Management of Data, Washington D.C., pages 207--216. ACM Press, 1993.

Digital Library

[4]

W. W. Armstrong. Dependency structures of data base relationships. In Proc. of IFIP Congress, pages 580--583, 1974.

[5]

C. Beeri and P. Berstein. Computational problems related to the design of normal form relation schemes. ACM Trans. Database Syst., 4(1):30--59, 1979.

Digital Library

[6]

T. Calders and J. Wijsen. On monotone data mining languages. In G. Ghelli and G. Grahne, editors, DBPL, volume 2397 of Lecture Notes in Computer Science, pages 119--132. Springer, 2001.

Digital Library

[7]

A. Church. A note on the entscheidungsproblem. J. Symb. Log., 1(1):40--41, 1936.

[8]

L. Fang and K. LeFevre. Splash: ad-hoc querying of data and statistical models. In EDBT, pages 275--286, 2010.

Digital Library

[9]

B. Ganter and R. Wille. Formal Concept Analysis. SPRINGER, 1999.

[10]

F. Giannotti, G. Manco, and F. Turini. Towards a logic query language for data mining. In Database Support for Data Mining Applications, LNCS 2682, pages 76--94, 2004.

[11]

G. Gottlob and L. Libkin. Investigations on Armstrong relations, dependency inference, and excluded functional dependencies. Acta Cybernetica, 9(4):385--402, 1990.

[12]

J.-L. Guigues and V. Duquenne. Familles minimales d'implications informatives r&#233;sultant d'un tableau de donn&#233;es binaires. Math. Sci. Humaines, 24(95):5--18, 1986.

[13]

T. Imielinski and H. Mannila. A database perspective on knowledge discovery. Commun. ACM, 39(11):58--64, 1996.

Digital Library

[14]

M. Lacroix and A. Pirotte. Domain-oriented relational languages. In Proceedings of the third international conference on Very large data bases, volume 3, pages 370--378. VLDB Endowment, 1977.

Digital Library

[15]

H.-C. Liu, A. Ghose, and J. Zeleznikow. Towards an algebraic framework for querying inductive databases. In DASFAA (2), pages 306--312, 2010.

Digital Library

[16]

D. Maier. Minimum covers in the relational database model. J. ACM, 27(4):664--674, 1980.

Digital Library

[17]

H. Mannila and H. Toivonen. Levelwise search and borders of theories in knowledge discovery. Data Min. Knowl. Discov., 1(3):241--258, 1997.

Digital Library

[18]

R. Meo, G. Psaila, and S. Ceri. An extension to sql for mining association rules. Data Min. Knowl. Discov., 2(2):195--224, 1998.

Digital Library

[19]

A. Netz, S. Chaudhuri, J. Bernhardt, and U. M. Fayyad. Integration of data mining with database technology. In VLDB, pages 719--722, 2000.

Digital Library

[20]

L. D. Raedt. An inductive logic programming query language for database mining. In AISC, pages 1--13, 1998.

Digital Library

[21]

L. D. Raedt, T. Guns, and S. Nijssen. Constraint programming for itemset mining. In KDD, pages 204--212, 2008.

Digital Library

Cited By

Chardin BCoquery EPailloux MPetit J(2017)RQLTheoretical Computer Science10.1016/j.tcs.2016.11.004658:PB(357-374)Online publication date: 7-Jan-2017
https://dl.acm.org/doi/10.1016/j.tcs.2016.11.004
Chardin BCoquery EPailloux MPetit J(2014)RQL: A SQL-Like Query Language for Discovering Meaningful Rules2014 IEEE International Conference on Data Mining Workshop10.1109/ICDMW.2014.50(1203-1206)Online publication date: Dec-2014
https://doi.org/10.1109/ICDMW.2014.50

Index Terms

On Armstrong-compliant logical query languages
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
    2. Query languages
2. Theory of computation

Recommendations

Logical foundations for more expressive declarative temporal logic programming languages

In this article, we present a declarative propositional temporal logic programming language called TeDiLog that is a combination of the temporal and disjunctive paradigms in logic programming. TeDiLog is, syntactically, a sublanguage of the well-known ...
A logical framework for reasoning about logical specifications
On the expressive power of query languages

Two main topics are addressed. First, an algebraic approach is presented to define a general notion of expressive power. Heterogeneous algebras represent information systems and morphisms represent the correspondences between the instances of databases, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

LID '11: Proceedings of the 4th International Workshop on Logic in Databases

March 2011

63 pages

ISBN:9781450306096

DOI:10.1145/1966357

Program Chairs:
George Fletcher
TU Eindhoven,The Netherlands
,
Sławek Staworko
University of Lille, France

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 March 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Agence Nationale de la Recherche

Conference

EDBT/ICDT '11

EDBT/ICDT '11: EDBT/ICDT '11 joint conference

March 25, 2011

Uppsala, Sweden

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
49
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chardin BCoquery EPailloux MPetit J(2017)RQLTheoretical Computer Science10.1016/j.tcs.2016.11.004658:PB(357-374)Online publication date: 7-Jan-2017
https://dl.acm.org/doi/10.1016/j.tcs.2016.11.004
Chardin BCoquery EPailloux MPetit J(2014)RQL: A SQL-Like Query Language for Discovering Meaningful Rules2014 IEEE International Conference on Data Mining Workshop10.1109/ICDMW.2014.50(1203-1206)Online publication date: Dec-2014
https://doi.org/10.1109/ICDMW.2014.50

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten