Abstract
Ontology-based data access is a powerful form of extending database technology, where a classical extensional database (EDB) is enhanced by an ontology that generates new intensional knowledge which may contribute to answer a query. The ontological integrity constraints for generating this intensional knowledge can be specified in description logics such as DL-Lite. It was recently shown that these formalisms allow for very efficient query-answering. They are, however, too weak to express simple and useful integrity constraints that involve joins. In this paper we introduce a more expressive formalism that takes joins into account, while still enjoying the same low query-answering complexity. In our framework, ontological constraints are expressed by sets of rules that are so-called tuple-generating dependencies (TGDs). We propose the language of sticky sets of TGDs, which are sets of TGDs with a restriction on multiple occurrences of variables (including joins) in the rule bodies. We establish complexity results for answering conjunctive queries under sticky sets of TGDs, showing, in particular, that ontological conjunctive queries can be compiled into first-order and thus SQL queries over the given EDB instance. We also show how sticky sets of TGDs can be combined with functional dependencies. In summary, we obtain a highly expressive and effective ontological modeling language that unifies and generalizes both classical database constraints and important features of the most widespread tractable description logics.
- Data grid inc. http://dt123.com/DataGrid/DataGridWebsiteV1a/.Google Scholar
- Oracle semantic technology center. http://www.oracle.com/technology/tech/semantic_technologies/.Google Scholar
- S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995. Google ScholarDigital Library
- A. Acciarri, D. Calvanese, G. D. Giacomo, D. Lembo, M. Lenzerini, M. Palmieri, and R. Rosati. QuOnto: Querying ontologies. In Proc. of AAAI, 2005. Google ScholarDigital Library
- J.-F. Baget, M. Leclère, M.-L. Mugnier, and E. Salvat. Extending decidable cases for rules with existential variables. In Proc. of IJCAI, 2009. Google ScholarDigital Library
- V. Barany, G. Gottlob, and M. Otto. Querying the guarded fragment. In Proc. of LICS, 2010. Google ScholarDigital Library
- C. Beeri and M. Y. Vardi. The implication problem for data dependencies. In Proc. of ICALP, 1981. Google ScholarDigital Library
- L. Cabibbo. The expressive power of stratified logic programs with value invention. Inf. Comput., 147(1), 1998. Google ScholarDigital Library
- A. Calì, G. Gottlob, and M. Kifer. Taming the infinite chase: Query answering under expressive relational constraints. In Proc. of KR, 2008.Google Scholar
- A. Calì, G. Gottlob, and T. Lukasiewicz. A general datalog-based framework for tractable query answering over ontologies. In Proc. of PODS, 2009. Google ScholarDigital Library
- A. Calì, G. Gottlob, and A. Pieris. Advanced processing for ontological queries. Unpublished manuscript. Available at: http://benner.dbai.tuwien.ac.at/staff/gottlob/CGP.pdf.Google Scholar
- A. Calì, G. Gottlob, and A. Pieris. Tractable query answering over conceptual schemata. In Proc. of ER, 2009. Google ScholarDigital Library
- A. Calì, G. Gottlob, and A. Pieris. Query answering under non-guarded rules in datalog+/-. In Proc. of RR, 2010. Google ScholarDigital Library
- A. Calì, D. Lembo, and R. Rosati. On the decidability and complexity of query answering over inconsistent and incomplete databases. In Proc. of PODS, 2003. Google ScholarDigital Library
- D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable reasoning and efficient query answering in description logics: The DL-lite family. J. Autom. Reasoning, 39(3), 2007. Google ScholarDigital Library
- D. Calvanese, G. D. Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Data complexity of query answering in description logics. In Proc. of KR, 2006.Google Scholar
- A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proc. of STOCS, 1977. Google ScholarDigital Library
- A. K. Chandra and M. Y. Vardi. The implication problem for functional and inclusion dependencies. SIAM Journal of Computing, 14, 1985.Google Scholar
- E. Dantsin, T. Eiter, G. Georg, and A. Voronkov. Complexity and expressive power of logic programming. ACM Comput. Surv., 33(3), 2001. Google ScholarDigital Library
- A. Deutsch, A. Nash, and J. B. Remmel. The chase revisisted. In Proc. of PODS, 2008. Google ScholarDigital Library
- A. Deutsch and V. Tannen. Reformulation of XML queries and constraints. In Proc. of ICDT, 2003. Google ScholarDigital Library
- R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data exchange: Semantics and query answering. Theor. Comput. Sci., 336(1), 2005. Google ScholarCross Ref
- I. Horrocks. Using an expressive description logic: FaCT or fiction? In Proc. of KR, 1998.Google Scholar
- D. S. Johnson and A. C. Klug. Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci., 28(1), 1984.Google ScholarCross Ref
- D. Maier, A. O. Mendelzon, and Y. Sagiv. Testing implications of data dependencies. ACM Trans. Database Syst., 4(4), 1979. Google ScholarDigital Library
- D. Mailharrow. A classification and constraint-based framework for configuration. Artif. Intell. for Engineering Design, Analysis and Manufacturing, 12(4), 1998. Google ScholarDigital Library
- A. Poggi, D. Lembo, D. Calvanese, G. De Giacomo, M. Lenzerini, and R. Rosati. Linking data to ontologies. J. Data Semantics, 10, 2008. Google ScholarDigital Library
- R. Rosati. On the decidability and finite controllability of query processing in databases with incomplete information. In Proc. of PODS, 2006. Google ScholarDigital Library
- S. Rudolph, M. Krötzsch, and P. Hitzler. All elephants are bigger than all mice. In Description Logics, 2008.Google Scholar
- M. Y. Vardi. On the complexity of bounded-variable queries. In Proc. of PODS, 1995. Google ScholarDigital Library
Index Terms
- Advanced processing for ontological queries
Recommendations
Ontological queries: Rewriting and optimization
ICDE '11: Proceedings of the 2011 IEEE 27th International Conference on Data EngineeringOntological queries are evaluated against an enterprise ontology rather than directly on a database. The evaluation and optimization of such queries is an intriguing new problem for database research. In this paper we discuss two important aspects of ...
Reformulating Ontological Queries Using Materialised Rewritings
WIMS '16: Proceedings of the 6th International Conference on Web Intelligence, Mining and SemanticsQuery rewriting is a prominent technique in ontology-based data access (OBDA) applications. Roughly speaking, a rewriting of a query Q w.r.t. an ontology is another query Q' that can be directly evaluated over the data without further reference to the ...
Efficient Ontological Query Answering by Rewriting into Graph Queries
Flexible Query Answering SystemsAbstractThe OWL 2 QL profile of the OWL 2 Web Ontology Language, based on the family of description logics called DL-Lite, allows for answering queries by rewriting, i.e. by reformulating a given query into another query that is then directly processed by ...
Comments