Abstract
After explaining some of the benefits of capturing uniqueness constraints, such as keys and functional dependencies, in any object-centered data model, we consider a number of alternative semantics for concept constructors that could be introduced for this purpose in Description Logics. Most significantly, we show that Classic—the hitherto most expressive DL for which reasoning is tractable, can be extended with a version of constructors capturing functional dependencies (including keys) while still possessing subsumption and consistency checking algorithms that are sound, complete, and run in low-order polynomial time. The results continue to hold even when we introduce cycles in the part-of hierarchy.
This work was supported by NSF contract IRI-9619979 and by grants from NSERC, Government of Ontario ITRC and Nortel Ltd.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
H.W. Beck, S.K. Gala, and S.B. Navathe. Classification as a query processing technique in the CANDIDE semantic data model. In Proc. 5 th IEEE Int. Data Eng. Conf., pp. 572–581, 1989.
C. Beeri. A formal approach to object-oriented databases. Data and Knowledge Engineering, 5(4), pp. 335–382, 1990.
S. Bergamaschi and B. Nebel. Acquisition and validation of complex object database schemata supporting multiple inheritance. Applied Intelligence, Vol 4(2), pp. 185–204, 1994.
A. Borgida and P.F. Patel-Schneider. A semantics and complete algorithm for subsumption in the CLASSIC description logic. J. of AI Research, pp. 277–308, 1994.
S. Bergamaschi and C. Sartori. On taxonomic reasoning in conceptual design. ACM TODS 17(3), pp. 385–442, 1992.
M.F. van Bommel and G.E. Weddell. Reasoning about equations and functional dependencies on complex objects. IEEE TKDE, 6(3), pp. 455–469, 1994.
J.P. Ballerini, D. Beneventano, S. Bergamaschi, C. Sartori, and M. Vincini. A semantics-driven query optimizer for OODBs. In Proc. DL-95, pp. 59–62, Roma, Italy, 1995.
A.Borgida. Description logics in data management, IEEE TKDE, 7(5), pp.671–682, 1995.
R. Brachman, P. Selfridge, L. Terveen, B. Altman, A. Borgida, F. Halper, T. Kirk, A. Lazar, D. McGuinness and L. Resnick. Knowledge representation support for data archaeology, Int. J. of Intelligent and Cooperative Inf. Sys., 2(2), pp. 159–186, 1993.
M. Buchheit, M. Jeusfeld, W. Nutt, and M. Staudt. Subsumption between queries in object-oriented databases. Inf. Sys., 19(1), pp. 33–54, 1994.
M. Buchheit, F. Donini, W. Nutt and A. Schaerf. Refining the structure of terminological systems: terminology = schema + view. In Proc. AAAI-94, pp. 199–204, 1994.
D. Calvanese, G. de Giacomo and M. Lenzerini. Structured objects: modeling and reasoning. In Proc. DOOD'95, pp. 229–246, 1995.
T.Catarci and M.Lenzerini. Representing and using interschema knowledge in cooperative information systems. Int. J. of Int. and Coop. Inf. Sys., 2(4), pp. 375–398, 1993.
L. Delcambre and K. Davis. Automatic validation of object-oriented database structures. In Proc. IEEE Data Engineering Conf., pp. 2–9, 1989.
G. de Giacomo and M. Lenzerini. What's in an aggregate: foundations for description logics with tuples and sets. In Proc. IJCAI-95, pp. 801–807, 1995.
M. Ito and G. E. Weddell. Implication problems for functional constraints on databases supporting complex objects. JCSS, 50(1), pp. 165–187, 1995.
Knowledge representation meets databases. Proc. KRDB'96, Budapest, Hungary, August, 1996. F. Baader, M. Buchheit, M. A. Jeusfeld and W. Nutt (editors), 1996.
A. Y. Levy, D. Srivastava and T. Kirk. Data model and query evaluation in global information systems. J. of Intelligent Inf. Sys., 5(2), pp. 121–143, 1995.
D. McGuinness and A. Borgida. Explaining subsumption in description logics. In Proc. IJCAI-95, pp. 816–821, 1995.
B. Nebel. Computational complexity of terminological reasoning in BACK. Artificial Intelligence, 34(3), pp. 371–383, 1988.
J. Wright, E. Weixelbaum, K. Brown, G. Vesonder, S. Palmer, J. Berman, and H. Moore. A knowledge-based configurator that supports sales, engineering and manufacturing at AT&T Network Systems. In Proc. Conf on Industrial Applications of AI(IAAI93), pp.183–193, 1992.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Borgida, A., Weddell, G. (1997). Adding uniqueness constraints to description logics. In: Bry, F., Ramakrishnan, R., Ramamohanarao, K. (eds) Deductive and Object-Oriented Databases. DOOD 1997. Lecture Notes in Computer Science, vol 1341. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63792-3_10
Download citation
DOI: https://doi.org/10.1007/3-540-63792-3_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63792-9
Online ISBN: 978-3-540-69647-6
eBook Packages: Springer Book Archive