Ordering and Path Constraints over Semistructured Data

Authors: Bertino E.¹; Elmagarmid A.K.²; Hacid M-S.³

Source: Journal of Intelligent Information Systems, Volume 20, Number 2, March 2003 , pp. 181-206(26)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

Constraints are a valuable tool for managing information. Feature constraints have been used for describing records in constraint programming (Aït-Kaci and Podelski, 1993; Smolka and Treinen, 1994) and record like structures in computational linguistics (Kaplan and Bresnan, 1982; Shieber, 1986). In this paper, we consider how constraint-based technology can be used to query and reason about semistructured data. The constraint system FT (Müller et al., 1997) provides information ordering constraints interpreted over feature trees. Here, we show how a generalization of FT combined with path constraints can be used to formally represent, state constraints, and reason about semistructured data. The constraint languages we propose provide possibilities to straightforwardly capture, for example, what it means for a tree to be a subtree or subsumed by another, or what it means for two paths to be divergent. We establish a logical semantics for our constraints thanks to axiom schemes presenting our first-order theory constraint system. We propose using the constraint systems for querying semistructured data.

Keywords: semistructured data; constraints; satisfiability; rule languages

Language: English

Document Type: Research article

Affiliations: 1: Dipartimento di Scienze dell'Informazione, University of Milano, Via Comelico, 39/41 20135 Milano, Italy. bertino@dsi.unimi.it 2: Department of Computer Sciences, Purdue University, West Lafayette, IN 47907, USA. ake@cs.purdue.edu 3: LISI-UFR d'Informatique, University Claude Bernard Lyon 1, 8, blvd Niels Bohr, 69622 Villeurbanne, France. mshacid@bat710.univ-lyon1.fr

Publication date: 2003-03-01