This paper presents a powerful language for querying complex graphs and a method for generating efficient implementations that can answer queries with complexity guarantees. The graphs may have edge labels that may have parameters, and easily and naturally capture complex interrelated objects in object-oriented systems and XML data. The language is built on extended regular path expressions with variables and scoping, and can express queries more easily and clearly than previous query languages. The method for implementation first transforms queries into Datalog with limited extensions. It then extends a previous method to generate specialized algorithms and complexity formulas from Datalog with these extensions.