Query Languages and Query Optimization: Overview and Trends

Introduction

In the Age of Information, making sense of all available resources has been likened to trying to drink from a fire hose. Innovations in geographic technologies have added to the flood of information, and making sense of it all in terms of the when, where, and what aspects of an event or issue requires specialized queries. Therefore, identifying the current level of technological development as well as recent trends can establish relevant benchmarks for researchers, as well as providing a snapshot of these issues as they currently exist. This snapshot can be used to extend recent trends in query language and optimization into the future, given the known increases in computer processing speeds. To this end, this study provides a review of the relevant peer-reviewed and scholarly literature, as well as reliable online resources, concerning query languages and query optimization, prefaced by a background and overview section, as well as a projection of recent trends into the future in the conclusion.

Background and Overview

Bidlack and Wellman (2010) recently observed that an increasingly wide array of information resources has driven the demand for more efficient ways to access the specific information that is needed [1]. Indeed, the efficient use of information resources has become an integral part of many business models today. According to Webster, "It is impressive to watch the rapid development of the online world, encompassing the World Wide Web, journal and reference databases, library catalogs, e-books, and other e-content. We have come to depend on this newer online world as it grows more powerful and more complex" [2].

Satisfying the need for accessing information systems in general and databases in particular involves developing and applying some type of query. Calvanese and de Giacomo report that "data sources have been considered simply as systems that provide data but make no further contribution to the query-answering process" [3]. With Internet browsers, this need can be satisfied by a simple and straightforward search using Google, for example, but accessing various types of databases requires specialized query techniques and languages. A database management system (DBMS) is a program that can input, edit, and retrieve information from a database. A database is a collection of information organized into records and fields, and stored as files on a computer. Sometimes the term "database" is used to include the DBMS as well. Relational, object-oriented, network, flat, and hierarchical are all types of DBMS. They differ in how they organize information for storage. Retrieval from a DBMS requires a query language—a structured way of expressing search requests. Relational DBMS alone have a standard query language called SQL (Structured Query Language) [4].

Structured Query Language (SQL) is a programming language designed to get information out of and put it into a relational database. Queries are constructed from a command language that allows one to select, insert, update, and locate data. SQL is a recognized standard [5]. Other query languages have more focused applications, while others are designed to provide searches in broader settings; these various languages are discussed further below.

Query Languages

In order to understand how query languages work, it is important to describe the environment in which they function. Although query languages differ in terms of purpose, functionality, and interface, they share a common feature: accessing data represented in a database in some fashion and returning the aggregated results to the user. A representational schema needs to anticipate all possible queries and analyses to be performed in an information system. Since relational database management systems were dominant, respective temporal languages were developed as extensions of standard query language (SQL) [6]. Query languages can be designed to allow query computation to be performed internally and to ease users from having to remember technical operations in a query process [7].

The when, where, and what — the so-called "spatio-temporal" — factors related to query languages are presented in Table 1 below.

Table 1: Query Language Spatio-Temporal Factors

Query Spatio-Temporal Information about When: This kind of query is used to obtain information on temporal objects. Answers can be obtained by referring semantic or spatial objects to temporal objects through a proper relation table. Life-oriented questions inquire when birth, death, splitting, merging, or reincarnation occur in a certain period of time, while motion-oriented questions ask when a move, jump, or spread takes place.

Query Spatio-Temporal Information about Where: This type of query aims at obtaining information about spatial objects for locations and spatial properties of a semantic object at a specific time. Where-questions can be static (asking whereabouts or states of entities or attributes) or dynamic (asking paths of an entity changing its location through time).

Query Spatio-Temporal Information about What: This type of query seeks information about changes in which the focal information is semantic objects, such as changes of supermarket services for a particular area. One first identifies the area of interest, then examines what has changed in that area by referring to its corresponding semantic objects at that time.

Source: Frank 2001, p. 226

In recent years, database engineers have proposed the development of pure database models and query languages that can be used for representing and handling semi-structured data (SSD) in order to facilitate the processing of information exchanges and the efficiency of software systems in a broad array of applications, including genome databases, digital libraries, and electronic commerce platforms [8]. According to Stefanakis, "In a SSD set it is expected that there will be objects with missing attributes, objects with multiple occurrences of the same attribute, different data types associated with the same attribute in different objects, and/or semantically related information represented differently in various objects. All the above factors render traditional data models (such as the relational and the object-oriented model) inadequate to represent and handle SSD sets" [9].

Recent innovations in technological development have provided two basic alternatives for modeling semi-structured data sets: the first alternative was created by the database community and the second alternative by software engineers actively involved in the development of Web-based technologies to query semi-structured data [10]. Some of the most well-known examples of such languages include the Object Exchange Model (OEM) and the Lightweight Object REpository query Language (LOREL) [11].

Some other current examples of query languages and their applications are presented in Table 2 below.

Table 2: Query Language Types

eXtensible Markup Language (XML): Web-based technology offers the eXtensible Markup Language (XML) and its surrounding technologies, which are well suited for modeling and querying semi-structured data (SSD) sets [12]. XML is a flexible way to create standard information formats and share both the format and the data on the World Wide Web. It improves the functionality of the Web by letting you identify your information in a more accurate, flexible, and adaptable way [13]. Prior to the introduction of XML, there was SGML (Standard Generalized Markup Language), which was developed in the early 1980s and widely used for large documentation projects. The development of HTML (Hyper Text Markup Language) started in 1990. The designers of XML took the best parts of SGML, guided by experience with HTML, and produced something that is no less powerful than SGML, yet vastly more regular and simpler to use. SGML is mostly used for technical documentation; with XML, it is exactly the opposite. XML is a pared-down version of SGML, designed especially for Web documents. It allows designers to create customized tags, enabling the definition, transmission, validation, and interpretation of data between applications and organizations [14].

SPARQL: Relationship networks can be queried using Simple Protocol and RDF Query Language (SPARQL — pronounced "Sparkle"). SPARQL is a form of Structured Query Language (SQL) specifically used for querying within inference software [15].

Web Ontology Language (OWL-DL): These standards-based knowledge representation mechanisms provide computationally feasible knowledge representation (KR) for business processes. OWL is a W3C standard for semantic knowledge representation. Web Services and Web Services Architecture provide envelope and transport mechanisms for information and knowledge exchange [16]. Queries are posed in terms of a certain query language over the alphabet of the global ontology and are intended to extract a set of tuples of elements of the semantic domain. In accordance with what is typical in databases, each query is required to have an associated arity and to extract only tuples of that arity. Given a source database for the ontology, the tuples of interest are those guaranteed to be in the answer of the query for every model with respect to the source database — in other words, certain answers are of interest.

One of the most common ways to express knowledge on a domain of interest is to use class-based formalisms, in which knowledge is represented in terms of objects grouped into classes and relationships between classes. Examples are entity-relationship diagrams in databases, UML class diagrams in software engineering, and ontology languages for the semantic web such as OWL-DL. All such formalisms can be captured in a fragment of first-order logic in which one can express inclusions and equivalences between classes and possibly pose additional constraints on the relations between classes. Such fragments correspond to a class of logics called description logics [17]. The Web Ontology Language (OWL) is a World Wide Web Consortium standard and a leading approach to semantic Web ontologies. OWL-Description Logics (OWL-DL) uses DL as its fundamental knowledge representation mechanism. Ontology descriptions are presented formally through description logics for theoretical soundness, and in machine-readable format using OWL-DL to provide practicality. Software reasoners, such as Racer, support concept consistency checking, T-Box reasoning, and A-Box reasoning on models developed using SHIQ description logics translated into OWL-DL. These provide the basis for development of a knowledge base of machine-interpretable knowledge representation, in OWL-DL format, that can be used for developing computational ontologies for knowledge integration in inter-organizational eBusiness processes [18].

Description Logic ALCQI: ALCQI is a notable example of an expressive DL that features constructs typical of conceptual modeling formalisms and that allow ALCQI to capture the most important features of such formalisms. The ALCQI DL provides concept constructs for complement, intersection, union, existential restriction, universal quantification, and number restrictions. As for roles, it provides the construct for inverse roles [19].

Contextual Query Language (CQL): CQL is a formal language for representing queries to information retrieval systems such as web indexes, bibliographic catalogs, and museum collection information. The design objective is that queries be human-readable and writable, and that the language be intuitive while maintaining the expressiveness of more complex languages. Traditionally, query languages have fallen into two camps: powerful, expressive languages not easily readable or writable by non-experts (e.g., SQL, PQF, and XQuery), or simple and intuitive languages not powerful enough to express complex concepts (e.g., CCL and Google). CQL tries to combine simplicity and intuitiveness of expression for simple, everyday queries with the richness of more expressive languages to accommodate complex concepts when necessary [20]. CQL is so named because it is founded on the concept of searching by semantics or context, rather than by syntax. The same search may be performed in a different way on very different underlying data structures in different servers, but the important thing is that both servers understand the intent behind the query. In order for multiple communities to define their own semantics, CQL uses Context Sets to ensure cross-domain interoperability [21].

XPath: XPath is a node-addressing language used with XML documents [22]. This query language allows users to query for various index services, and results are gathered and returned to the user based on the following steps:

1. The client sends the search request to its nearest DDS with the XPath query.
2. The DDS contacts a FADA node to search all the Index Services (ISs) of the system.
3. The IS search request is broadcast to all the Federated Advanced Directory Architecture (FADA) nodes using the FADA internal protocol.
4. The FADA node returns to the DDS the list of ISs.
5. The DDS contacts each IS making the XPath query.
6. Finally, the results are gathered and returned to the client [23].

Z39.50 Search Standards for Cross-Search Capabilities for Library Catalogs: The Open Archives Initiative (OAI) has become another approach to integrated online searching. OAI is a protocol for the automated harvesting of descriptive and location metadata about content from diverse online sources. Metadata is stored in a common index database where it can be searched, and searchers can then be automatically routed to the source content for any retrieved search results. This is essentially the same technique employed by Web search engines, which use automated software to collect information about many websites and store it in a common index. The metadata harvesting approach differs considerably from the approach taken by Z39.50.

Z39.50 searches many silos by passing a query to each separate database in a common query language. Responses are then received back from each database in turn. The broadcast search method is similar to the approach used by many metasearch tools such as WebFeat and MuseGlobal. While Z39.50 searches rely on a common protocol and query language, metasearch tools may have to translate each separate query to suit the individual data source (information silo) being searched. While broadcast searching has had some success, as the number of different online resources grows, metadata harvesting seems to be the more promising approach to search integration [24].

ActivePrime: ActivePrime leverages AI-related techniques in three broad categories: lightweight ontologies, search-space reduction (SSR), and query optimization. Lightweight ontologies are deployed as modules and classes in the Python programming language, enabling rapid, iterative development of ontologies using a popular scripting language. The ontologies also benefit from the large repository of built-in Python operators, and sophisticated operations on ontologies can be performed with just a few lines of code. SSR techniques are utilized when performing inexact matching on larger volumes of data, when record counts grow into the many thousands and millions. Query optimization techniques allow for real-time detection of duplicate records when matching one record to a large remote database [25].

Conclusion

The research showed that various query languages provide the ability for users to search a database or set of databases in various ways that deliver the desired results. The research also showed that the search process can be facilitated through query optimization — an approach that varies in techniques but has a common focus on both streamlining the search process to focus on the desired material while concomitantly expanding it to include potentially valuable permutations of the information being sought. Finally, the research was consistent in emphasizing that recent trends point to a future where the query process is even more intuitive, seamless, and efficient.

References

[1] C. Bidlack & M.P. Wellman. 2010, Spring. "Exceptional Data Quality Using Intelligent Matching and Retrieval." AI Magazine 31(1), pp. 65–66.

[2] P. Webster. 2004, November/December. "Breaking Down Information Silos: Integrating Online Information." Online 28(6), pp. 30–32.

[3] D. Calvanese & G. de Giacomo. 2005, Spring. "Data Integration: A Logic-based Perspective." AI Magazine 26(1), pp. 59–61.

[4] J. Feather & P. Sturges. 2003. International Encyclopedia of Information and Library Science. London: Routledge, p. 126.

[5] D. Britain. 2003. "My Database Will Call Your Database, but Can They Talk? A Primer on Data Reporting Compatibility." THE Journal 30(10), pp. 12–14.

[6] A.U. Frank, J. Raper & J-P. Cheylan. 2001. Life and Motion of Socio-Economic Units. London: Taylor & Francis, p. 225.

[7] Frank et al., p. 225.

[8] E. Stefanakis. 2003. "Representation of Generalized Map Series Using Semi-Structured Data Models." Cartography and Geographic Information Science 30(1), pp. 51–53.

[9] Stefanakis, p. 51.

[10] Stefanakis, p. 51.

[11] Stefanakis, p. 52.

[12] Stefanakis, p. 52.

[13] R.A. Kinney. 2006, May/June. "XML: A Vehicle to Update Army Doctrine." Infantry 95(3), pp. 6–7.

[14] Kinney, p. 7.

[15] B. Bitters. 2009. "Spatial Relationship Networks: Network Theory Applied to GIS Data." Cartography and Geographic Information Science 36(1), pp. 81–83.

[16] F. D'Aubeterre, R. Singh & L. Iyer. 2008. "A Semantic Approach to Secure Collaborative Inter-organizational Ebusiness Processes (SSCIOBP)." Journal of the Association for Information Systems 9(3/4), pp. 231–233.

[17] D'Aubeterre et al., p. 231.

[18] D'Aubeterre et al., p. 232.

[19] Calvanese & de Giacomo, p. 60.

[20] "CQL: Contextual Query Language (SRU Version 1.2 Specifications)." 2011. The Library of Congress. Available: p. 1.

[21] "CQL: Contextual Query Language (SRU Version 1.2 Specifications)," p. 2.

[22] D.M. Gabbay & J. Woods. 2006. Logic and the Modalities in the Twentieth Century. Amsterdam: Elsevier North Holland, p. 518.

[23] C. de Alfonso, M. Caballer, J.V. Carrion & V. Hernandez. 2007. "Gcitizen: A Grid Middleware for a Transparent Management of the Information about Citizens in the Public Administration." Journal of Theoretical and Applied Electronic Commerce Research 2(1), pp. 18–19.

[24] Webster, p. 31.

[25] Bidlack & Wellman, p. 66.

[26] Bidlack & Wellman, p. 66.

[27] Bidlack & Wellman, p. 67.

[28] Bidlack & Wellman, p. 67.

[29] R.J. Thierauf & J.J. Hoctor. 2003. Smart Business Systems for the Optimized Organization. Westport, CT: Praeger, p. 165.

[30] Thierauf & Hoctor, p. 165.

[31] J. Minker. 1997, Fall. "Logic and Databases." AI Magazine 18(3), pp. 21–23.

[32] Minker, p. 22.

[33] Minker, p. 22.

[34] Minker, p. 23.

[35] Bidlack & Wellman, p. 66.

[36] Calvanese & de Giacomo, p. 60.

[37] Calvanese & de Giacomo, p. 61.

[38] Webster, p. 31.

[39] Webster, p. 31.

[40] Webster, p. 32.

[41] Webster, p. 32.

[42] Webster, p. 32.

[43] Webster, p. 32.